May 30, 2002 Lessons Learned the Hard Way SRM 93 was a Thursday night contest. As a landmark, it was the night before the 2002 Soccer World Cup kicked off. There were 653 coders for the match, with 392 coders and 42 rooms in DivII. The problem slate appeared relatively simple, but each of the problems tripped up at least 40% of submissions. One thing that springs out is that the problem slate was not as diverse as usual: the 250 and 500 both required rounding calculations, and the 500 and 1050 both required looping on r objects selected from a pool of n objects. 250 (Median): This problem was to return the middle value(s) of an array of ints. In the case of even length, return the mean of the two middlemost values. All rounding should be upward. This problem appears to have been approached as a speedtyping test. Unfortunately, the result was a carwreck. Of the submitted solutions, less than 50% passed systest. This was consistent in all three groupings (greens, greys and rookies.) The solution to this problem is extremely simple: Sort the array, then either return the mid value if length is odd, or take the two inner values and combine them. The following should work. Arrays.sort(input); if (input.length % 2 ==1) { return input[input.length/2]; } else { int sum = input[input.length/2] + input[input.length 1]; int av = sum/2; if (2*av < sum) return av+1; return av; } Problems:
What I find fascinating about this problem was that only 25% of problems which failed were actually successfully challenged. Since most solutions required less than 15 lines of code.... 500 (Hiring): Given an array containing the exam results and salary requirements of prospective employees, along with a salary cap, calculate the best 3 candidates whose total salaries do not exceed the cap. Because the average is taken of three values, rounding is to the nearest integer. This problem is best tackled as an exhaustive search, using fixed loops. Notable was the fact that the pass rate varied from 58% among the greens to 47% in the grey rooms. Problems:
1050 (Big2): This was a simulation problem based on the card game poker. Given 13 cards, count the number of poker hands which can be made with these cards, which contain a straight or better. The solution requires the generation of the hands, and then their analysis. For hand generation, fixed loops is the easiest way to go. The key to the problem, of course is the hand evaluator. The number of submissions for this problem was tiny: only 15% of the DivII coders submitted. As with most simulation problems, the complexity of the solution was the main problem. Problems:

