Match Editorial

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

Div. 1 - Easy: LarvaRace
This problem was slightly more difficult than the typical easy problem, though the solution was still fairly straightforward. Generally there are two approaches: one can either iterate through the time steps until a worm has reached the destination, or one can determine how many time steps it will take for each worm to reach the destination. In my opinion the former approach was easiest, as there were no special cases to worry about. The problem specification guaranteed that at least one worm would eventually reach the destination, so all one had to do was move the worms in the proper manner. For the second approach, there was more room for error, as there may have been worms that never moved. These worms would never reach the destination, and this would have to be detected. Many people that used this approach failed to note that worms that never move do reach the destination if the destination is zero. It was this test case in particular that broke three solutions in Room 1 during the Challenge Phase. Most people submitted this problem very quickly, but many of those people missed it for some reason or another. I think this was the trickiest problem in Div. 1 this match.

Div. 2 - Easy: Evil
This problem wasn't evil at all. It just consisted of computing the parity of each of a set of numbers. The parity of a number is simply the sum of its bits modulo 2, although there are many equivalent definitions. The only difficult aspect of the problem then is extracting the bits of a number. While the problem statement went into great detail explaining one way of doing this, here are a few alternative methods that are much quicker to implement:

• In Java: Integer.toBinaryString(v) returns a String containing the binary representation of v. Thus the ith bit of a number v (where bit 0 is the least significant bit) can be obtained byString tmp = Integer.toBinaryString(v); bit = tmp.charAt(tmp.length() - i - 1);
• In C++ or Java: The expression (v & (1 << i)) will be non-zero only if the ith bit of v is 1

Div. 1 - Medium / Div. 2 - Hard: RPSVari
Like many medium problems, this was a case of reading the specification of a simulation carefully and properly implementing it. There were no real tricks to the problem, as long as one managed not to confuse array dimensions, etc., during implementation. Very few people missed this problem in Div. 1, and most people that submitted this problem in Div. 2 got it correct as well.

Div. 2 - Medium: TripleCode
As with the RPSVari problem, this problem mostly consisted of following instructions.

Div. 1 - Hard: PrizeAward
For those that were able to quickly formulate a combinatorical solution, this problem was nearly trivial. For others, however, it took a lot of time or effort to discover the solution (if at all). Once the solution is correctly formulated, the implementation is actually quite simple.

The solution can be drived by expressing the problem as a recurrence relation. Let S(p, c) be the solution to the problem for p prizes and c coders. First we will formulate the base cases. We know that if there are no coders, there is only one way to distribute the prizes (that being no distribution at all), so S(0, c) = 1. We also know that if there is no prize, then there is only one way to distribute it, so S(p, 0) = 1. With these base cases in place, we can now apply some basic combinatorics to solve S(p, c) for any values of p and c.

For i = 1 to c, we count how many ways i out of c coders can tie for a particular place. The solution to this is given by the choose function, C(c, i) = c! / (i! * (c-i)!). For each value of i, we then multiply C(c, i) by a reduced version of the problem, where i prizes are split among i coders and the number of ways of distributing the remaining p - i prizes (if any) among the remaining c - i coders are counted. This is given by S(max(p - i, 0), c - i).

Thus our solution is S(0, c) = S(p, 0) = 1, S(p, c) = sum {1 <= i <= c} C(c, i) * S(max(p - i, 0), c - i). This is trivial to implement, and one can optimize by applying memoization techniques to both the C and S functions to avoid unnecessarily recomputing values (as done by derkuci). To see how to iterate through the values of C(c, i) for some fixed c without computing factorials, see derkuci's solution.

One can go even further and simply precompute all the possible answers, since the input constraints only permit 256 possible inputs. However, the straight-forward solution should be plenty quick enough for this problem (as evidenced by ambrose's solution). Although there were few submissions for this problem, most of them were correct.