Saying competitive programming is just trivial and self contained makes me laugh. You've never tried, have you?
Try out this year's Advent of Code, check the time for the first 1000 entries. Can you do better than 50% of them? (I am generous with top 1000, as probably not all of them would actually enter a competition.)
I haven't done Advent of Code or TopCoder or the ACM student contest.
What I *have* done:
1) ICFP Programming Contest.
Annual 72 hour online contest, usually to solve a single task. Often there is a "Lightning" Prize for the best solution (to the full problem) submitted in the first 24 hours. I was captain of teams (sometimes just me and one other, sometimes up to three others) called usually "Dylan Hackers". I/we won the following prizes:
2001: 2nd place -- rewrite documents in an HTML-like markup language to minimise their size i.e. find the shortest markup that gives each element the same properties as the original. Programs were submitted in executable form and the judges ran them on previously-unseen inputs. Execution time is a tie-breaker in the event of same output size. Any crash or failure to finish within a time limit disqualifies. (Always be ready to output the current best version, even if it's unchanged from the original!)
2003: Judge's prize -- given a known set of race tracks and a car with certain acceleration, braking, and cornering physics properties, submit the driver control inputs that minimise the 1st lap time from a standing start. The judges did *not* run your program. We used a hybrid approach, writing a simulator which I then drove manually, and an optimiser to incrementally improve the solution. The winner used several hundred Pentium 4 PCs at a university to brute-force a slightly restricted solution space. Our solutions were significantly better on about a 1/3 of the tracks, very very similar on almost all the rest, but we were absolutely slaughtered on one (not a normal race track, but a half-toned photo of Phil Wadler's face)
2005: 2nd place AND also Judge's prize -- given a map of part of Chicago with a number of banks, there is a robber trying to visit banks and steal money from them and a set of police trying to catch the robber. Write AI for the robber, and AI for the police, and compete in a double round-robin against other entrants, sometimes being the robber and sometimes the cops. The 2nd place was for the initial competition, and then a few weeks later they had a surprise 24 hour competition based on the main one but with significantly changed specs. The Judge's prize was given as the entry that was easiest to update for the changed specs.
Samsung internal programmer testing. You need basically a Masters'-level CS education to get hired in the first place, but then they have internal competitions in a series of 3-hour exams at four graded levels. Each exam consists of solving a single problem in C or Java (restricted to basic libraries e.g. in C stdio and stdlib). As I reverse-engineered by looking at historical tests the stages were roughly 1) you can use a direct, greedy, algorithm; 2) there is a search space but it's small-enough to brute-force it; 3) like for the second stage but the search space is too large without pruning it, "dynamic programming" is needed; 4) wild-card ... just super-challenging. I passed at the 4th level. In the Moscow office about 1% of programmers did that. World-wide the percentage was quite a bit lower.
I'll describe the level 4 exam task I passed. You have to write two functions. The first function takes a grayscale bitmap image (I think maybe it was 1024x1024, 4 bpp) and a larger bitmap (4096x4096?) that you should somehow recode the grayscale image into. The driver program then takes your bitmap image, applies a random series of 90º rotations and mirror image operations around the horizontal and vertical and two diagonal axes. And then it randomly corrupts up to N bit values in each 4x4 cell. And then calls your second function. The job of your 2nd function is to recover the original image from the corrupted bitmap.
Here is a level 3 one. There is a set of some thousands of nodes and arcs in a fully-connected graph with no cycles. Each arc is a resistor, each with different values. You may take any one resistor, disconnect it, and reconnect it between any two new points. Which choice minimises the maximum resistance between two points in the graph. (Remarkably, you can do this one in O(N) time and space)
So ... yeah ... I'd like to see an AI tackle any of these, purely from the English text description of the problem.
Other than by saying "Oh, this problem was already given in X competition in Y year, and here's the winning entry..."
Home
Help
Search
Login
Register
