Match Editorial

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

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 Div-II.

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 middle-most values. All rounding should be upward.

This problem appears to have been approached as a speed-typing test. Unfortunately, the result was a car-wreck. 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:

1. Failing to sort the array. Such a solution would not have passed two of the examples.
2. Failing to deal with negative numbers correctly. Problem is that -(2n + 1)/2 = -n so any solution that relied on adding 1 failed. This problem appears to have been the main cause of failure.
3. Incorrect calculation of the mean (by using the input[n/2] and input[n/2+1] instead of input[n/2-1].
4. Having two variables with similar names, and working with one in one loop branch, and another in a second.
5. Not rounding at all.

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:

1. Not making any attempt to generate the possible solutions.
2. Not checking that you aren't using the same entry/employee more than once
3. Not rounding correctly.
4. Concentrating on rounding the average, then actually returning the sum.
5. Looping over the possible solutions correctly, but then returning then first one found.

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 Div-II coders submitted. As with most simulation problems, the complexity of the solution was the main problem.

Problems:

1. Failing to deal with the fact that (for straights), and Ace is both high and low.
2. Typos in lookup tables.
3. Not looping over possible hands correctly.