Thursday, January 27, 2005 Match summary 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 ProblemsProfitCalculatorUsed as: Division Two  Level One:
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 (totalPricetotalCost)/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*(totalPricetotalCost)/totalPrice; Note that the format of the string is very specific, which makes it easy to extract the data. BikeRaceUsed as: Division Two  Level Two: Used as: Division One  Level One:
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. DeadCodeUsed as: Division Two  Level Three:
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 shortestpath algorithm to do this (like Pisky), others used a depthfirst 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. BagsOfGoldUsed as: Division One  Level Two:
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^{n} 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^{n} possible game states are effectively reduced to n^{2} 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.length1; //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, last1, bags)); return memo[first][last]; } A convenient way to take advantage of the overlapping subproblems is to memoize an answer into a 2dimensional array where the indexes are the numbers of the first and last bags left. LoopyUsed as: Division One  Level Three:
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. 
