Match Editorial

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

SRM 87 had 623 registrants, and this resulted in 41 rooms in Division-II, of which 5 rooms were in the non-rated competition.

The problem slate in Division-II formed a good test: the 250 had a sting in its tail which led to an exciting challenge round, the 550 was a reasonable problem which tested knowledge of data structures, and the 1050 was a more complex challenge which involved navigating a graph.

For the green section, the result appears to have been an excellent contest. In the grey rooms, however, no-one in the bottom 10 rooms managed a successful 1050. In a discussion in the lobby, the idea of deliberately varying the difficulty of the Division-II slate (one relatively easy, one more challenging each week) was put forward. This may be worth trying, either officially or unofficially in the future. Certainly, SRM 87 was more than a "typing contest" in most rooms.

250 (Eenie):
This problem was a simple token counting problem based on childrens' counting games like "Eenie meenie miney mo". Input was a string representing the rhyme, and the number of children in the circle. The problem was to return the number of the child selected. The twist was that the counting was 1-based.

I got a feeling from many of the failed solutions, that the coder felt it was merely a typing speed test. In java, the solution is simple, using a StringTokenizer and the countTokens() method. It is interesting that many Java coders among those whose problems I surveyed did not think of this method in the heat of battle.

Problems identified:

1. A surprising number of people failed this by unthinking use of the mod function. This failed because mod returns a value in [0, n-1] rather that [1, n]
2. Counting the children against the words, rather than vice versa.
3. Correctly identifying the problem case of where count = n, but returning 1 or the number of words instead of n.
4. Use of regular instead of modular division.

This problem led to a very eventful first minute or so of challenge phase in some rooms, as a lucky coder challenged several problems successfully one after another.

550 (losers):
This problem involved scoring a mythical game, where points are awarded for the first 3 positions in each round. Given a list of round results, the goal was to return an alphabetically sorted String[] of the lowest scorer or scorers. The points awarded were 6 for 1st, 3 for 2nd and 2 for 3rd.

This problem was simplified by a knowledge of standard data structures such as java.util.HashSet or c++ map, for example.

Problems:

1. Failure to return more than one name when a tie occured, resulting from using a constant, where a loop index was required.
2. Failing to add elements outside the top 3 to the data structure. This never registered contestants who never placed.
3. Failing to deduce the scoring mechanism correctly from the problem description. In this category, one finds people giving points beyond third.
4. Code path failure using combined conditions. One example of this involved checking that this was a scoring entry and that a HashTable included the key. In the false part of the condition, the coder didn't check the Hashtable again, and instead reset the accumulated score for that key to zero.

1050 (AuntUncle):
The goal was to take a series of triples, representing 2 parents and a child, and return the set of siblings of the parents of a specified target. Including the parents or the target was forbidden.

The problem proved quite tricky, with a large number of submissions failing. Among the errors found were:

1. Use of String.endsWith() rather than tokenizing first, resulting in spurious errors
2. Returning parents as uncles or aunts.
3. Segfaulting.
4. Returning the target.
5. The case including an incestuous family tree caused some problems.
6. Nullpointer Exception traversing HashMaps in java when there were no links between the families specified.