|
Match Editorial |
Thursday, December 21, 2006
Match summary
With 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 Christmas-themed 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 Problems
SantaGifts
Used 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 0-based index of the kid that gets the k-th gift can be computed as k%N.
Value 250 Submission Rate 472 / 538 (87.73%) Success Rate 398 / 472 (84.32%) High Score chadnov for 245.55 points (3 mins 50 secs) Average Score 191.15 (for 398 correct submissions)
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:
Value 500 Submission Rate 217 / 538 (40.33%) Success Rate 124 / 217 (57.14%) High Score batterlife for 490.56 points (3 mins 57 secs) Average Score 304.01 (for 124 correct submissions)
Dashing through the snow
Value 250 Submission Rate 378 / 397 (95.21%) Success Rate 351 / 378 (92.86%) High Score marek.cygan for 247.82 points (2 mins 40 secs) Average Score 210.06 (for 351 correct submissions)
On a one-horse 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.
Value 1000 Submission Rate 52 / 538 (9.67%) Success Rate 29 / 52 (55.77%) High Score gislan for 796.65 points (15 mins 11 secs) Average Score 544.59 (for 29 correct submissions)
On each level we have three options to consider:
- Covering the whole level with the same color.
- Using two bauble colors on the level - this can be done only for the levels with even numbers.
- Using all three colors - the level number must be dividable by 3.
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.
Value 500 Submission Rate 255 / 397 (64.23%) Success Rate 151 / 255 (59.22%) High Score haha for 485.31 points (4 mins 58 secs) Average Score 332.84 (for 151 correct submissions)
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.length-1 && 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 upper-left corner of a square. Now since the upper-right 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:
Value 1000 Submission Rate 95 / 397 (23.93%) Success Rate 82 / 95 (86.32%) High Score Petr for 838.84 points (12 mins 58 secs) Average Score 585.39 (for 82 correct submissions)
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.
