Match Editorial

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

SRM89 was a Saturday afternoon contest, starting at 1pm. The unusually early start time saw a couple of people griping in the lobby. The entry of 500 coders (low compared to many recent contests) may have been related to this. In division 2, this resulted in 33 room, of which 5 were rookies.

The problem slate was challenging enough to be interesting, but doable. For instance, in all rooms except one room of the rooky section, someone got the level 3 problem. Challenge phase appears to have been pretty quiet.

200 (Average):

Given 2 int arrays, count the number combined socre (score[i] = a[i] + b[i]) which are below average.

Some care is needed to ensure that scores equalling the average don't get returned. Most submission for this problem were successful.

The easiest test for below average is:
if (total[i] * length < totalSum)

Problems:

1. Using integer division, which rounds down the average number.
2. Some solutions appear to fail because of lack of precision in floating point maths.
3. Counting entries which are above average instead of below.
4. Testing whether individual scores were less than average.
5. Returning the average.
6. Calculating the average based on math.length-1

I'd be surprised if some of the failing solutions could have been tested much. I know it's often hard while others are submitting

500 (Powerful):

This problem also saw service as the div1 200. The goal of the problem was check whether the input, an integer (1 <= n <= 2,000,000,000), was an exact power, and return either an error message or an expression of the number as the highest possible power (ie 81=3^4 and not 9^2). Subtleties included the fact that 1 was not considered to be a power.

A simple brute force search is possible. Sqrt(2,000,000,000) is roughly 45,000. Since 2 billion is close to 2^31, the time complexity on linear brute force (worst case) is way less than 1.4 million iterations.

At first sight, it looks like a floating point problem. I'd actually recommend avoiding floating point math like the plague. Something like the following is much more likely to work:

maxBase = maxPow = 0
// Quite important for the loop to allow square roots.
for (int base = 2; base < Math.sqrt(number+1); base++) {
   int result = 1;
   for (int pow = 2; pow < 32; pow++) {
      result *= base;
   }
   if (pow > maxPow) {
      maxPow = pow;
      maxBase = base;
   }
}
if (maxPow > 0) {
   return ""+maxBase+"^"+maxPow;
} else {
   return "NOT A PERFECT POWER";
}

It is interesting that many solutions to this problem failed, but relatively few successful challenges were made. In particular, the first 2 test cases, 2,000,000,000 and 1,000,000,000, seem to have tripped up many coders.

Problem:

1. Uncaught C++ exceptions felled some people (I don't understand C++ sufficiently to find the cause.
2. Failing to return the highest power.
3. One solution checked whether the current power was even, and returned false if this was the case.
4. Incorrect looping bounds. Some solutions looped to j < Math.sqrt(number). Others looped to "klimit = sqrt(number) / 1000"
5. Misreading the problem: one coder returned "2^1" on input of 2.
6. Over-complicating the algorithm. Some coders tried to do a binary search, and left fence-post errors.

The pass rate for this problem was low, and the errors quite diverse, so I've probably not covered quite a few problems, I'm afraid.

900 (Filter):
Given a field of '1's and '0's, remove all '1's which do not form a cross pattern, then count the number removed.

This problem was straightforward (there were probably more correct solutions than for the 600. Two basic approaches seem to have been used: one was to check all possible crosses containing the current element. The other was to check each possible cross, and store the result of the check, then compare the input to the data.

Problems:

1. One technique used was to check around a particular element:

boolean inCross(int x, int y, char[][] data) {
   if (centre(x+!, y, data)) return true;
   if (centre(x-1!, y, data)) return true;
   if (centre(x, y+1, data)) return true;
   if (centre(x, y+1, data)) return true;
   if (centre(x, y, data)) return true;
   return false;
}

boolean centre(int x, int y, char[] data) {
   if (x>=0 || y>=0 || x<=maxX || yx<=maxY) return false;
   if (data[x-1][y] != '1') return false;
   if (data[x+1][y] != '1') return false;
   if (data[x][y-1] != '1') return false;
   if (data[x][y+1] != '1') return false;
   // Note: no check on the centre
   return true;
}

This would fail on:

111
101
111

Finally, a response to Pochmann's comment on my column on SRM88: I was referring to a problem solution technique as "flood and fill", which I hadn't found in textbooks. He correctly pointed out that the search technique used is depth first search, which is _every_ textbook, pretty much.

My comment was based on the idiom used. I've seen the same type of problem a couple of times in room 1. Looking over some of the solutions, spotting the differences can be like spotting differences between two peoples' "for" loops. The level 3 problem in SRM88 was generally attacked by rather adhoc and difficult-to-read code, and privately, a couple of people have asked that I cover algorithms in a little more depth.

But pochmann is right :)