Saturday, April 12, 2008 Match summary
This prime numbered SRM gathered together 1352 coders that were faced with a rather hard problem set. However, ACRush rushed
through the set achieving his new highest rating. Congratulations! The ProblemsBreakingTheCodeUsed as: Division Two  Level One:
This problem was just a simple simulation of the algorithm described in the statement. If there are only letters in the message, we replace each letter with its assigned number. And if there are only digits, we take every two consecutive ones and replace them with a letter that's assigned the given code. This should be clear enough, but you can see the fastest submission by brosmike for reference. SortingGameUsed as: Division Two  Level Two: Used as: Division One  Level One:
Low constraints guaranteed that there were no more than 8! = 40320 possible states. So, how can we find the shortest path from the initial state to a final one? By BFS, of course. We only need to map the states that can be represented by vectors, numbers or strings to their values, that are lengths of the respective shortest paths. It is easy to generate the permutations that we can achieve from the given one in one move. Please see the fastest and extremely clear implementation of the above by kia. This code shows, that in C++, the STL could solve the problem for us. CollectingMarblesUsed as: Division Two  Level Three:
This problem was rather standard. With at most 13 marbles we can represent the state as a set of marbles that we already have, the number of bags left, and the space left in the bag we are trying to fill now. So we start with an empty set, numberOfBags bags and bagCapacity space left in the bag we're filling. In each state we can either put to the current bag any marble we don't have yet or put the current bag aside and start to fill the next one. Representing sets as bit masks gives us approximately 2^{13} * 20 * 10 = 1638400 possible states. That's ok to use memoization on them and with a simple recursion compute the answer. Sample Java implementation follows: public class CollectingMarbles { int[][][] dp; int[] w; int c; public int recur (int mask, int left, int cur) { if (left == 0) return 0; if (dp[mask][left][cur] == 1) { dp[mask][left][cur] = 0; for (int i = 0; i < w.length; i++) if ((mask & (1 << i)) == 0 && w[i] <= cur) dp[mask][left][cur] = Math.max( dp[mask][left][cur], 1 + recur(mask  (1 << i), left, cur  w[i])); dp[mask][left][cur] = Math.max( dp[mask][left][cur], recur(mask, left  1, c)); } return dp[mask][left][cur]; } public int mostMarbles (int[] mW, int bC, int nOB) { w = mW; c = bG; dp = new int[1 << w.length][nOB + 1][c + 1]; Arrays.fill(dp, 1); return recur(0, nOB, c); } }SumOfPowers Used as: Division One  Level Two:
Well, this problem was an interesting one. The idea, with its simplicity and mathematical
background, caused many coders to search the internet for the formula. It could end with a
success, but not necessarily. Many coders, after reading all these formulas with Bernoulli
numbers were angry at the problem as they thought that you have to be a genius to come up with them.
Well, maybe you have to be, and maybe Bernoulli was. But what if he had Google? Maybe
he wouldn't even bother to invent all this stuff. Ok, so suppose that we don't have Google.
What do we have here? We are given the sum 1^{k} + 2^{k} + ... +
n^{k}. Ok, let a_{i} = 1^{k} + ... + i^{k}.
Everyone who finished high school knows that Pascal showed us some day how we can effectively compute binomial coefficients, so let's suppose that we know their values and forget about them. So it looks like we have some number of recursively defined sequences. Now, the second thing that every top coder should know. The most obvious way to find the nth term of a recursive sequence is to use a matrix multiplication. Again, we don't have to be very bright to see that: That looks nice. But let's get our a_{i} sequence into play: Now, because matrix multiplication is associative, we can compute the nth power of our magic matrix in time O(k^{3} * log n) and then multiply it by the vector for a_{1} (it will contain only ones) to get a_{n}. Well, that definitely didn't hurt us. There were of course many different approaches. We could for example use Lagrange's polynomial interpolation (as the given sum is of course a polynomial) or use a different recursion then the one described here (please see the klopyrev's solution for a reference). There was also a solution based on Bernoulli numbers  use Google to find it! HouseProtection Used as: Division One  Level Three:
Let's think for a moment about an easier version of the problem  let's think how we can find the biggest
number of radars we're able to place for some given range. To begin, we'll place radars in all possible
points. Now, we want to remove the smallest number of radars in such way, that in the remaining set there
won't be any pair of intersecting radars that have different colors. That starts to sound like a vertex cover
problem  let's build a graph out of our radars and let's connect two radars of different colors with an edge if
their areas intersect. The general vertex cover problem is a wellknown NPcomplete problem. But, luckily, we have
a bipartite graph here, so according to
Konig's theorem we know that the minimal vertex cover is equivalent to maximal matching. We know how to find
the latter, so let's return to the original problem. 
