Yesterday I was part of CMC’s first ever entry into the ACM ICPC, an international programming competition. Last year solving three problems would have been good enough for 5th place, but this year solving three problems was only good enough for 29th out of 75 or so.
The easiest three problems were easy to pick out and we started work on them. The first problem was, given an expected distribution of T-shirt sizes and a number of participants, write some code to determine how many T-shirts to order. The code for this problem was more or less written in the problem description and I was able to solve it in the first twenty minutes or so.
While I was doing that my teammates were working on a cipher problem – given a codeword, create a simple code alphabet and use it to decrypt a message.
While they were doing that going on I started working on the third problem, which was a map labeling algorithm. It was like a Rand McNally map where if you go off the top of the map you have to go to another page on the map. You were given a ‘map’ divided up into a series of blocks, and had to number each block, and then for each block label the block’s neighbors. I solved this one pretty quickly too, however I forgot to remove a print statement from my code, so it was printing an empty line before the output, which cost two incorrect submissions and 40 penalty minutes.
The cipher problem turned out to be fairly difficult. There was a problem with the program that took about an hour to solve, partly because we kept printing out code that we thought was showing one thing when in fact it was showing something else. Also, we had an array of characters that was supposed to hold all of the letters of the alphabet from A to Z, but in fact was missing W. Once we solved those we submitted the code and got the correct answer on the first submission, but by this point we had an hour and a half left.
I started working on the fifth problem, which I thought was the next easiest. The problem was, given a triangle and a thousand points inside that triangle, split the points into three even groups by finding another point inside the triangle.
I found the algorithm right away, which was to do a binary search and always move toward the region that contained the most points. However, this turned out to be tricky to implement in practice. Ultimately this problem was really difficult and only a few groups solved it correctly (the winning Harvey Mudd team solved seven of eight problems and this was the one problem they didn’t solve). Trying it was a tactical mistake on my part, and we might have been able to solve a fourth if we’d attempted a different problem.
Ultimately it was a long day and as my teammate Jacob noted, “the nerdiest thing I’ve ever done.” It was good I guess, considering I was the only person on our team who’d practiced before the contest and we were the first team ever from CMC to go to the competition. I’d wanted to join the competition because I show my resume to people and they say “Great you’re an economics major, so, marketing?” and I wanted to show that I could code a little bit. It would have been great to do better in the competition but them’s the breaks.
Among other things this shows how wide the differences between programmers can be; it’s estimated that the best programmers are 10 times as efficient as average programmers, and looking at the times to completion it’s easy to see how this is true. By the time I solved Problem 1 the Harvey Mudd team had already solved three problems, and there were some teams there that didn’t even solve a single problem. These are hard to measure, which is why it’s so important to actually look at someone’s code to see how they do things, or ask them to write sample code.
All of my practice code can be found here; unfortunately you can’t keep the code you wrote during the competition.
