Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?   Lessons Learned

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 Division-II, 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:

1. Only checking up to sqrt(n), without adding the second of a pair of divisors.
2. Using (sum < n) as a loop guard.
3. Including sqrt of n twice when counting factors.

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:

1. Assuming that the scores table was sorted. (All the examples were sorted)
2. In a solution which created three ArrayLists to contain the scores in each case, adding the "success" score, to the "fail" List.
3. Divide by zero exception.
4. Errors in indexing into the array. This cropped up in a solution which counted how many results were less than a particular score. Had the coder counted the number greater, it is likely the error would not have occurred.

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:

1. Trying to use if-then-else to handle the logic. Since some steps output state depended on their input state, this could not work.
2. Mis-understanding the problem description. This was definitely a problem worth reading more than once. Some people simply coded the wrong rules.
3. Not realising that input state was inportant for some steps.

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.