Match Editorial

The abnormal point values on the problems in this match tipped people off that it would be slightly bizarre, but division 1 coders were surprised to be greeted by an easy problem that was possibly harder than the medium problem (if it wasn't harder, it was at least trickier). Especially because of the division 1 easy/division 2 medium problem, the challenge phase became very important, as some people bagged challenge after challenge by noticing other people's oversights.

In the end, the winner in Division 1 was the only coder to successfully solve all three problems, John Dethridge. tomek was next with a failed easy submission and jshute was third without submitting the first problem. In division 2, not one person solved the medium problem correctly. IvanRomanov took the crown with solid submissions on the easy and hard problems, followed closely by Pisky who had a more interesting challenge phase. Newcomer MichaelN rounded out the top 3 in division 2 with just slightly slower times on the easy and hard problems.

The Problems

Value	250
Submission Rate	207 / 228 (90.79%)
Success Rate	186 / 207 (89.86%)
High Score	irritate for 249.38 points (1 mins 25 secs)
Average Score	201.18 (for 186 correct submissions)

This problem was pretty straightforward without being overly trivial - possibly the hardest part was just getting the data out of the strings. In the end, all you had to do is add up the total price and total cost and return (totalPrice-totalCost)/totalPrice as a percentage, rounded down. In order to dodge floating point precision errors, it was beneficial to try to use integers (you knew you got exactly two digits after the decimal place, so it was a matter of either taking out the decimal points or just multiplying the values by 100. I preferred the former hack:

int totalPrice = 0, totalCost = 0;
for (int i=0; i<items.length; i++)
{
   items[i] = items[i].replaceAll("\\.", "");   //eliminate '.' from the string!
   totalPrice += Integer.parseInt(items[i].substring(0, 5));
   totalCost += Integer.parseInt(items[i].substring(6));
}
return 100*(totalPrice-totalCost)/totalPrice;

Note that the format of the string is very specific, which makes it easy to extract the data.

Value	700
Submission Rate	18 / 228 (7.89%)
Success Rate	0 / 18 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

Value	375
Submission Rate	82 / 180 (45.56%)
Success Rate	19 / 82 (23.17%)
High Score	athenachu71 for 249.15 points (22 mins 46 secs)
Average Score	185.95 (for 19 correct submissions)

This was the sort of tricky problem labeled "easy" that you expect to dread in later tournament rounds. No one in division 2 successfully solved it, and only one blue coder in division 1 did.

In spite of its apparent trickiness, this wasn't conceptually too hard of a problem. It was useful to do this problem in two waves.

First, you go through and figure out who is eliminated before they start - If you figure out who finishes the first lap first and when, you can check every starting time and anyone who starts after that is eliminated simultaneously at the time the first person finishes their first lap.

Once those are out of the way, you compare each pair of runners i and j, where i started before j. If i runs slower than j, then j will eventually catch up, and i is eliminated no later than the point in time j catches up. If i runs faster than j, then i will eventually lap j, and j is eliminated no later than the time when i laps j.

Finally, you want to just remember the earliest time that each biker was eliminated and sort the bikers' names primarily in order of elimination time and secondarily in alphabetical order of name. Note that the elimination times may not be integers - you need to store them as doubles to consistently tell which elimination came first.

Value	900
Submission Rate	64 / 228 (28.07%)
Success Rate	6 / 64 (9.38%)
High Score	IvanRomanov for 599.07 points (22 mins 41 secs)
Average Score	499.54 (for 6 correct submissions)

In this problem, you had to determine how much of the given "code" was unreachable by a terminating code path. My approach to this problem was simple; it just requires two distinct algorithms.

First you find out which parts of the code are reachable. Some people just adapted their favorite shortest-path algorithm to do this (like Pisky), others used a depth-first search bounded when they hit a line they've already reached.

Next, you have to figure out what parts of the code are on terminating paths (i.e. - there is a path from them to a return statement). This is a little more awkward, because you would have to trace backwards from the return statements, which don't point back at the statements that go to it. One clever implementation of this part was RedSpikeyThing's, which used memoization to make it easy to search forward for a return statement starting anywhere.

Once you know which lines can be reached and which can terminate, you count how many either aren't reachable or can't terminate, and return the number.

Value	400
Submission Rate	138 / 180 (76.67%)
Success Rate	108 / 138 (78.26%)
High Score	dgarthur for 396.60 points (2 mins 38 secs)
Average Score	337.38 (for 108 correct submissions)

This problem is drenched in AI and game theory, but not so deep that it couldn't be done by someone who isn't familiar with such topics couldn't figure it out. The hard thing to figure out is what exactly it means for both players to play optimally. If you play optimally assuming that your opponent will also play optimally, then playing optimally is picking the path with the lowest potential loss, assuming that your opponent does the same.

The game consists of repeatedly taking either the last or the first bag of gold, so if you had the idea to figure out the optimal answer by trying every possible path of the game and figuring out which is best, you'll have to forget that when you remember that there are 2ⁿ possible game paths where n is up to 50. The second difficult part of this problem was realizing that the loads of subproblems overlap, and the 2ⁿ possible game states are effectively reduced to n² possible game states. While the actual scores at each overlapping game state may not be the same, the future strategy, which decides the next move, is.

   public int netGain(int[] bags)
   {
      int[][] memo = new int[bags.length][bags.length];
      for (int i=0; i<bags.length; i++)
         for (int j=0; j<bags.length; j++)
            memo[i][j] = -1;   //initialize the cheat sheet
      int first = 0, last = bags.length-1;   //this is where we are
      return best(memo, first, last, bags);
   }
   
   public int best(int[][] memo, int first, int last, int[] bags)
   {
      if (memo[first][last] != -1)   //use the memo if we've already solved this subproblem
         return memo[first][last];
      else if (first == last)   //basis case for one bag
         return bags[first];
      //take the best of:
      //   The first bag minus the best the other player can do on the rest
      //   The second bag minus the best the other player can do on the rest
      memo[first][last] = Math.max(bags[first]-best(memo, first+1, last, bags), bags[last]-best(memo, first, last-1, bags));
      return memo[first][last];
   }

A convenient way to take advantage of the overlapping subproblems is to memoize an answer into a 2-dimensional array where the indexes are the numbers of the first and last bags left.

Value	1000
Submission Rate	12 / 180 (6.67%)
Success Rate	4 / 12 (33.33%)
High Score	jshute for 548.55 points (31 mins 58 secs)
Average Score	489.99 (for 4 correct submissions)

This problem is related to the DeadCode problem, and in fact, starts with basically doing the DeadCode problem, because you need to know which lines are on valid code paths.

After that, you can just try every edge AB and treat A as the exit and B as the entrance. You need to search backwards from A until you get back to B and count how many nodes are in valid code paths on the way back from A to B. You also need to make sure that the only paths into the loop that aren't from inside the loop are to the start, and keep in mind that there's always an entry from outside the loop to line 0.