May 18, 2002 Lessons Learned the Hard Way SRM89 was a Saturday afternoon contest, starting at 1pm. The unusually early start time saw a couple of people griping in the lobby. The entry of 500 coders (low compared to many recent contests) may have been related to this. In division 2, this resulted in 33 room, of which 5 were rookies. The problem slate was challenging enough to be interesting, but doable. For instance, in all rooms except one room of the rooky section, someone got the level 3 problem. Challenge phase appears to have been pretty quiet. 200 (Average): Some care is needed to ensure that scores equalling the average don't get returned. Most submission for this problem were successful. The easiest test for below average is: Problems: I'd be surprised if some of the failing solutions could have been tested much. I know it's often hard while others are submitting 500 (Powerful): A simple brute force search is possible. Sqrt(2,000,000,000) is roughly 45,000. Since 2 billion is close to 2^31, the time complexity on linear brute force (worst case) is way less than 1.4 million iterations. At first sight, it looks like a floating point problem. I'd actually recommend avoiding floating point math like the plague. Something like the following is much more likely to work: maxBase = maxPow = 0 // Quite important for the loop to allow square roots. for (int base = 2; base < Math.sqrt(number+1); base++) { int result = 1; for (int pow = 2; pow < 32; pow++) { result *= base; } if (pow > maxPow) { maxPow = pow; maxBase = base; } } if (maxPow > 0) { return ""+maxBase+"^"+maxPow; } else { return "NOT A PERFECT POWER"; } It is interesting that many solutions to this problem failed, but relatively few successful challenges were made. In particular, the first 2 test cases, 2,000,000,000 and 1,000,000,000, seem to have tripped up many coders. Problem: The pass rate for this problem was low, and the errors quite diverse, so I've probably not covered quite a few problems, I'm afraid. 900 (Filter): This problem was straightforward (there were probably more correct solutions than for the 600. Two basic approaches seem to have been used: one was to check all possible crosses containing the current element. The other was to check each possible cross, and store the result of the check, then compare the input to the data. Problems: boolean inCross(int x, int y, char[][] data) { if (centre(x+!, y, data)) return true; if (centre(x1!, y, data)) return true; if (centre(x, y+1, data)) return true; if (centre(x, y+1, data)) return true; if (centre(x, y, data)) return true; return false; } boolean centre(int x, int y, char[] data) { if (x>=0  y>=0  x<=maxX  yx<=maxY) return false; if (data[x1][y] != '1') return false; if (data[x+1][y] != '1') return false; if (data[x][y1] != '1') return false; if (data[x][y+1] != '1') return false; // Note: no check on the centre return true; } This would fail on: 111 101 1112. Exceeding time limits. 3. ArrayIndexOutOfBoundsException thrown. 4. Overwriting intermediate results. Some solutions kept arrays of previously calculated results. They didn't check the contents and lost data, ending with the wrong answer. Finally, a response to Pochmann's comment on my column on SRM88: I was referring to a problem solution technique as "flood and fill", which I hadn't found in textbooks. He correctly pointed out that the search technique used is depth first search, which is _every_ textbook, pretty much. My comment was based on the idiom used. I've seen the same type of problem a couple of times in room 1. Looking over some of the solutions, spotting the differences can be like spotting differences between two peoples' "for" loops. The level 3 problem in SRM88 was generally attacked by rather adhoc and difficulttoread code, and privately, a couple of people have asked that I cover algorithms in a little more depth. But pochmann is right :) 
