Thursday, December 21, 2006 Match summaryWith SRM 331 happening only a few days before Christmas, it was the perfect excuse to escape from the rush of cleaning, cooking and shopping for couple of hours and relax in front of some relatively easy Christmasthemed problems.In Division I we didn't have to wait long for the first submissions, as many coders scored more than 240 points on the easy problem. The remaining two problems also didn't stop the top competitors for long  one could have found himself outside the top 50, even after solving all the problems in less than forty minutes. After the end of the coding phase, ACRush was on the top with the impressive score of 1527.24 points, with krijgertje and Petr not far behind. Petr had the fastest solution on the hard problem, and would have had a better score if not for his resubmission of the medium. In the challenge phase the 500 pointer was the most popular target of attacks. ACRush gained 50 points, and hohosky, who was until now better known from his development performance, grabbed 150 challenge points and climbed to the second spot. Maybe it was the TopCoder College Tour together with wyy visiting Wuhan university that motivated him. In Division II we had another two Chinese coders at the top. chenll won with 1427.33 points, and second place went to newcomer batterlife. The ProblemsSantaGiftsUsed as: Division Two  Level One: All we need to do is to simulate the process described in the problem statement. We begin with the array filled with empty strings and than loop through all the gifts, appending each to the corresponding string. The 0based index of the kid that gets the kth gift can be computed as k%N. public String[] distribute(String[] gifts, int N) { String[] res = new String[N]; Arrays.fill(res, ""); for(int i=0;i<gifts.length && i<4*N;i++)res[i%N]+=gifts[i]+" "; for(int i=0;i<res.length;i++)res[i]=res[i].trim(); return res; }Two things to remember is not processing more than 4*N gifts, and not leaving trailing spaces. CarolsSinging Used as: Division Two  Level Two: Used as: Division One  Level One: Dashing through the snow On a onehorse open sleigh, Over the fields we go, Laughing all the way... Once we notice that there are at most 10 carols, it becomes obvious that a simple brute force solution is enough to solve this problem. We are going to loop through all the possible subsets of carols (not more than 1023) and choose the smallest one that satisfies the problem condition. Looping through all the subsets of a set is a technique commonly used in TopCoder problems, which explains the very fast submissions made by the experienced coders. The easiest way to do it is to use bitmasks to represent subsets. If you need more information on what a bitmask is, or how it applies here, check the excellent article by bmerry on that topic. public int choose(String[] lyrics) { int res = 1000; int[] masks = new int[lyrics.length]; int carols = lyrics[0].length(); for (int i = 0; i < lyrics.length; i++) masks[i] = Integer.parseInt(lyrics[i].replace('Y', '1').replace('N', '0'), 2); for (int m = 0; m < 1 << carols; m++) { boolean ok = true; for (int i = 0; i < masks.length; i++) if ((masks[i] & m) == 0) ok = false; if (ok && Integer.bitCount(m) < res) res = Integer.bitCount(m); } return res; }The solution above shows a nice Java trick to convert a string of 'Y' and 'N' into an integer and use it as a bitmask. It can be seen in the fastest Java submission, written by cep21. ChristmasTree Used as: Division Two  Level Three: To count all the ways to decorate a tree we can write a recursive function which processes one level of the tree at the time. Please note that result for subsequent levels depends only on what baubles we choose to use, not how we place them on the level. On each level we have three options to consider:
As often happens we can improve performance of a recursive solution by adding a memoization, though in this problem it's not necessary, since we have no more than 10 levels and it easily runs under the time limits. Shopping Used as: Division One  Level Two: At the first sight it looks like a knapsack problem, with the difference that we don't want to fill it up to the exact size but want to be able to fill all the sizes not exceeding X. The funny thing about this difference, though, is that it actually makes the problem easier to solve because a greedy solution exists. Let's analyze the coins in ascending order. We always have to start with a coin of value 1. If we don't have such a coin we simply return 1, and that's the only case when we do that. The second coin must be either 1 or 2  any higher value won't allow us to pay the amount of 2 dollars. Now consider the general case, when we have already taken some coins that sum up to S (and allow to pay all the amounts from 1 to S at the same time). We cannot take a next coin with value greater then S+1, because that won't allow us to pay S+1 dollars. If we take any coin with value x <= S+1 it will allow us to pay every amount from 1 to S + x, so the best choice is to pick as high x as we can. That translates into short code: int numCoins(int[] values, int X){ sort(values); int sum =0; int res =0; if(values[0]!=1)return 1; for(int p=0;sum<X;res++){ sum+=values[p]; while(p<values.length1 && sum +1 >=values[p+1])p++; } return res; }If you are still not convinced by the above explanation, it can be easily proven that any solution with an optimal number of coins, can be converted to a solution generated according to the above paragraph only by exchanging coins. HiddenSquares Used as: Division One  Level Three: Every corner of every square we can get must have an X coordinate existing in x1 or x2 arrays (similarly for the Y coordinate). That makes at most 10,000 possible points to consider. We can loop through all such points, assuming it is, for example, in the upperleft corner of a square. Now since the upperright corner also must be in the set of possible points we have not more than 100 points to check (the Y coordinate is set). The pseudocode of a solution can look like this: int res =0; foreach point (x,y) foreach x2 > x { int L = x2  x; //length of the square's edge if( maxDown[x][y] >= L && maxDown[x+L][y] >= L && maxRight[x][y] >= L && maxRight[x][y+L] >= L) res++; }maxDown and maxRight are precomputed arrays, containing the length of the longest line segment reaching down/right from a given point. Note that line segment is not necessarily the edge of a single rectangle, but can build from a few overlapping edges. 
