May 22, 2002 Lessons Learned the Hard Way SRM 91 was a wednesday night contest. As a landmark, it was the first challenge sponsored by Citrix. In all, 654 coders took part. There were 43 rooms in DivisionII, of which 4 rooms were in the rookie section. The first two problems appear to have been quite easy: both had solution rates above 70%. In contrast, the level 3 problem caused a lot of problems: the solution rate was 31.9%, and approximately 14% of the coders solved it successfully. 250 (Perfect): Take an integer, sum its divisors (not including the number, and check whether the result is equal to, less than, or greater than the initial number. The solution is quite simple. Code based on the following should be quite sufficient:
sum = 1; for (i=2; i<sqrt(n+1); i++) { if (n % i == 0) { sum+= i; if (i < n/i) { sum+= n/i; } } } Problems:
500 (ChallengePhase): In challenge phase of an SRM, a problem is submitted which uses a random number generator. The result is that it is likely to be correct 50% of the time. Given the scores within the room, the prize for the first three places, and the assumption that all submissions are correct, return the difference between the gain from a successful challenge (ie ev(success)  ev(current) and the loss from an unsuccessful challenge. Problems:
1000 (Rumba): The task is to simulate a Rumba dance, and check that each of 5 steps are included. There are 3 different positions allowed, and some steps are not allowed to begin from some positions. Each step ends in a particular position. The return is an int array, the first element of which is the number of steps not included in the dance steps list. The second element is either 1 if the dance is legal, or else the index of the first step which cannot be danced. The problem is might effectively tackled as a State Transition Machine. Internal to the program, the coder needs to write a function which takes the current state and next step, and returns the new state or invalid. The submission would then loop over the steps input. As an additional complication, the "BASIC" step could have more than one output, and the BACKWARD WALK step output depended on its input to determine its output. Problems:
As in most simulation problems, it's hard to point to a general problem. The difficulty is in translating the problem into code, and that's where the errors crop up. 
