Match Editorial

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

Srm 101 was the last paying Single Round Match, and as such, marked the end of an era. In the real world, it was in the day of the WorldCom accounting scandal, and that Brazil won through to the Soccer World Cup final. The turnout of 594 was respectable. I had anticipated a record turnout for the last paying match, but was clearly wrong. Another interesting stat is that there were only 21 debut coders.

The problem slate, in my opinion, was one of the easier slates we've seen. The level 3 problem was a calculation problem, the level 2 was required a powerset enumeration, but was small enough to be hard coded, and the level one required the ability of looping downwards rather than upwards.

On challenge phase, performance was patchy. Of failing problems, 25%, 26% and 41% were taken out in challenge phase. As seems to be the pattern, the grey coders took out the highest percentage of failing problems in challenge phase.

225 (AutoMorphic):

Take an integer, calculate its square, count the number of digit in the input which are not part of the longest suffix of the input which is also a suffix of the square.

This is a straightforward problem, solvable in a few lines of code. Two approaches are obvious:

1. Compare characters or digits starting with the least significant/ end of String.
2. Convert to Strings, and check for substrings.

Problems:

1. Working with prefixes instead of suffixes.
2. Counting common digits after the first difference has occurred.
3. Counting common digits instead of different digits.

475 (SRM):

A prescient coder knows in advance how long and how many points they'll get for each problem. Return the highest total which can be attained within 75 minutes.

This problem is best tackled as an exhaustive search problem. C++ coders who know std_algorithm.h have a definite advantage here.

I have library code:

   boolean makePerm(boolean[] bs) {
      int i,j,len = bs.length;
      for (i = 0; i < len && bs[i];i++);
      if (i == len) return false;
      for (j = 0; j < i; j++) {
         bs[j] = false;
      }
      bs[i] = true;
      return true;
   }

It's horribly inefficient (O^n in an inner loop: you can enumerate far better by bitmasking an int between 0 and 2^n-1, but I've never had a problem with timing. It's used as follows:

boolean[] bs = new boolean[3];
while (makePerm(bs)) {
   current = count(bs, problemScores, times);
   best = (best >= current) ? best : current;
}
return best;

Of course, this is overkill: it is perfectly possible to simply check each of the eight cases individually.

Problems:

1. Checking cases individually, but not checking all of them.
2. Overly complex code.
3. Fencepost errors when the total time taken is exactly 75 minutes.

1000 (Speeding):

For each driving offence, penalty points are added to a driver's licence. For each complete year of being offence-free, 3 points are removed. Given a list of offence dates and penalty values, calculate the number of points on a driver's licence at a particular date.

This problem seems simple to me. My approach to this was to count days since 12/31/1900, and compare based on this. The only challenge of the problem is to test effectively.

Problems:

1. ArrayIndexOutOfBoundsExceptions on empty input.
2. Not dealing with offences exactly a year apart correctly.
3. My initial solution assumed European "dd/mm/yy" style dates.