Random video! Although I feel that I’ve heard it earlier, my first conscious memory of getting linked to it is from this post. At first I thought it would be the right background music for this post, but upon further reflection I think it mainly suited me while I was writing this post. Well, it’s topical if you mentally replace “day” with “year”.
Anyway. Around this time a year ago, I paused my participation in big high-school competitions, for a variety of reasons.
Firstly, I stopped attempting to make IMO both because I wouldn’t get that much from the training and because other people ought to have the opportunity. I was concerned that I might condition myself to only be able to do math with the short-term motivation of contests. Better to focus on college math and maybe some original research, I thought. During the year, I did lots of the former and very little of the latter. Meh.
As for the IOI, my obvious next target: I was tired of training and going abroad while paranoid about whether my immune system would hold up. I didn’t feel that the IOI was worth that. To some degree, I also felt burned out about programming. Long story short, my treatment should end soon, and learning Haskell completely resolved the burnout problem.
But the most important reason, I think, was that “high school was too short”. I started math competitions ridiculously early and didn’t spend much time exploring other interests. I thought I knew myself well enough that I could say I didn’t have many more interests at all, but I was completely wrong (psych nerds will reflexively note this to be the Dunning-Kruger effect). I coded lots in weird languages — Haskell, as mentioned previously, plus Scala, plus all manner of other magical command line tools. I wrote my first math problem and submitted it officially, picked up a new instrument, went to a debate competition, served as an unimportant tech guy for MUN, discovered and became hooked on Pentatonix, participated in three puzzle hunts in Australia and one in Massachusetts, figured out my rough political stance, rode a boat, got retweeted by @eevee and @Kyrgyzstan_News, increased my Neopets™ fortune by over 3400%, and lurked on FurAffinity a little too much.
But now, dear competition world, I’m back.
Not ready to declare IOI contestant status, but it’s very probable. To a prosperous 2014! raises glass
The rest of this post will be an increasingly technical rambling rundown of programming competitions in an attempt to preserve the competitions in the period of over a year since my last competitions post. If you aren’t familiar with programming or at least math, you can probably stop reading.
The last programming competition I entered last year was the national round of the competition whose name roughly translates as “Academic Ability Contest,” which I’ll call the AAC for the sake of convenience below.
The hardest problem on the regional AAC, which I briefly mentioned in that last competitions post, involved combining math operators (as in the four 4s game). However, it only required you to find solutions with at most two operators, so an ugly, unstructured brute-force sufficed, and I got full score. Oops.
The hardest problem on the national AAC was a barely-disguised assignment problem, which apparently ought to be solved with the Hungarian algorithm, neither of which I had heard of before. (The backstory of that problem was easily the most pathetic I’ve ever seen. “Bob entered a math competition where one of the problems went like this. Help Bob out!”) I also very stupidly misread another problem and got a confusing “Second prize”, which actually meant somewhere between fourth to tenth place.
2013 rolled around. I took two quick math competitions, the silly APMO (on which three countries got ten perfect scores each) and the Tournament of Towns, since they didn’t require any extra training.
As for programming competitions, I competed in IPSC 2013 with Yoshi(ap), something I actually forgot about until I wrote this post. IPSC had a highly diverse and interesting selection of problems — some algorithmic, some mathematical, some puzzle-like (think rankk; some skills I learned there came in handy for Problem H.) Other small things later in the year: I qualified for round 1 of the Facebook Hacker Cup but was too lazy and/or forgetful to compete further; I survived Brilliant.org’s Hunger Games thing with a far-too-simple program; and, of course, I got a few miscellaneous victories on CodeForces and TopCoder (very few because time zones). All from the comfort of my home.
Back to classical algorithmic competition programming. During the summer, I attended a NTHU camp, learned a few algorithms, and solved many problems, most notably Problem E of the 2006 ACM-ICPC Shanghai Regionals, which is Dijkstra on a complicatedly transformed graph.
By “solved” I mean “spent hours on this problem and submitted fifteen wrong solutions, even while reading another person’s carefully documented solution at the same time.” That’s how hard it was. Chekhov’s Skill in 3… 2… 1…
Fast-forward to the new school year, 2013’s local AAC: the hardest problem was… Dijkstra on a not-so-complicatedly transformed graph. Guess how I did.
In-between, I participated in the National Problem-Solving Contest (NPSC) with a classmate. This contest is structured like ACM-ICPC, except that it’s for high-school students. We came alarmingly close to solving all the problems; the only one we didn’t get was the last one, which was essentially “write an interpreter of this primitive dialect of Lisp”. I say “primitive”, but just having to implement define and lambda sent the complexity out the window. To drive this point home, the organizers wrote a solution to Problem A in the Lisp dialect. Problem A, by the way, was a troll shortest-path problem that tricked me into thinking it was a maximum-flow problem for troublingly long.
Speaking of troll problems, this gem appeared in the previously mentioned summer camp, as a diversion of sorts during a weird game session (translated):
Problem B
?
Input Specification: Each line contains an integer n with 1 ≤ n ≤ 26.
Output Specification: Output the answer to each line.
Sample Input:
5
6
9
Sample Output:
B
C
FAlso, around this time, I finally remembered to do USACO, and (as expected) got promoted to gold. It would be nice if they sent reminder emails, although I should blame myself for not writing it down. The time limit was so wide that I spent half the time eating dinner, washing dishes, and coding a dumb client-tester in Perl to simplify redirecting input and output.
Later in December 2013, National AAC — the hardest problem was a geometric DP thing that I still don’t know how to solve. However, I managed to get four out of five test cases through repeatedly submitting unproved modifications of my brute-force solution with a pruned search space. There was instant grading with no submission penalty for this one because the powers that be were trying out our IOI system. The judging part went well.
On the other hand, compared to the posted previous competition environments, the work environment was much less convenient. The I/O spec was more annoying than USACO: all the problems had to read to and write from the same filenames, input.txt and output.txt (though of course you could do separate problems in separate subdirectories). The computers ran Windows XP with only basic Cygwin installations. But luckily, they had a reasonable version of Vim and a sufferable high-level language — Perl.
So I dashed out a client-side tester program in Perl.
Chekhov’s Skill is really an overused trope in my life.
Also came in handy: perl -de 0 is a REPL (thanks, HyperPolyglot). Or maybe a REL (read-eval-loop) because it doesn’t print anything unless you tell it to. But it’s still helpful for quick tests.
In hindsight, my Perl was redundant and would still be longer than a shell script if I fixed it, so that was pretty silly.
That’s my final lesson of the year: pick the right language for the job.
This is something I occasionally wish more fellow programming contestants realized. Yes, C++ is fast, but Java has many more portable goodies like its GUI and image-manipulation systems, Python has nice features for mathematical exploration like built-in arbitrary-size integers and itertools, and Perl has unreadable but quick magic variables and file tests. Learning extra languages is not very hard and lots of fun.
It is also something I am learning again for an ongoing competition that will end in just over a day — dear future self, no matter how much you love Haskell, please don’t expect normal people to be able to collaborate with you if you use it.
Until next year!