|
Match Editorial |
Wednesday, December 13, 2006
Match summary
Registration for this match closed with 786 registrants, a relatively low number compared to recent SRMs, but excitement was high nonetheless thanks to the participation of 5 targets, including the top 4 highest-rated coders in TopCoder's algorithm standings. After the room assignments were done, we were thrilled to see the ultimate challenge in room 1 with both Petr and tomek together.In Division 1 Petr got the lead in the coding phase thanks to fast solid submissions in all problems, including the fastest submission in the hard. kalinov was near the victory thanks to his challenges, but a successful one by Petr left him in second place. To complete the podium was ACRush , who had a good problem-solving night but lost a couple of points in the challenge phase.
Division 2 was a similar story, with wongiseng taking the lead thanks to a strong peformance in the coding phase. quanchi, in second place, and IYI_Blade, in third, were both within a successful challenge of the win.
The Problems
Sortness
Used as: Division Two - Level One:
The easiest approach was to iterate every number, calculating its sortness and then adding up all results, divide by the length of the input sequence, and that's it. This could be done with 2 simple loops as illustrated by wongiseng's code.
Value 250 Submission Rate 349 / 372 (93.82%) Success Rate 344 / 349 (98.57%) High Score chouxiaowen for 248.17 points (2 mins 26 secs) Average Score 220.14 (for 344 correct submissions)
Thinking a little leads to a somewhat simpler implementation. If you realized the fact that each pair of numbers was accounted only if they were disordered, and it was accounted twice in the total, you could just add 2 to a running total for each pair that was disordered and then divide by the length.
Arrows
Used as: Division Two - Level Two:
Used as: Division One - Level One:
Value 450 Submission Rate 303 / 372 (81.45%) Success Rate 157 / 303 (51.82%) High Score leiz for 440.19 points (4 mins 15 secs) Average Score 332.91 (for 157 correct submissions)
This problem was pretty straightforward, but required a careful implementation in order to work with every detail. There are several ways to do it. You could iterate over all substrings and then check if each of them was an arrow and, if it was, record its length. You could also try extending every > or < as much as possible. The easiest way I've seen was to produce every possible arrow (there are 4*50=200 of them, taking into account every type and length) and then check if the arrow is present (since every language has an embedded function to look for substrings in a string, this was a trivial task) and record the maximum length of a found arrow. C++ code for this approach follows:
Value 250 Submission Rate 362 / 367 (98.64%) Success Rate 266 / 362 (73.48%) High Score Petr for 247.98 points (2 mins 34 secs) Average Score 220.98 (for 266 correct submissions)
int r=-1; string a,b;
for(int l=1;l<=50;l++) {
if ( s.find(a+">") != -1 ) r=l;
if ( s.find(a+"<") != -1 ) r=l;
if ( s.find(b+">") != -1 ) r=l;
if ( s.find(b+"<") != -1 ) r=l;
a+="-"; b+="=";
}
return r;
NextPalindromicNumber
Used as: Division Two - Level Three:
Noting the possible sizes of the input, its pretty clear that thinking on numbers was not the way to go. Even if you have big integer arithmetic already coded (or use Java), adding 1 to the lower bound until a palindromic number is found was too slow (a simple input of 25 9s followed by 25 0s lead to 1025 iterations).
Value 1000 Submission Rate 169 / 372 (45.43%) Success Rate 43 / 169 (25.44%) High Score wongiseng for 916.12 points (8 mins 45 secs) Average Score 556.48 (for 43 correct submissions)
The approach that's left is to think on the form of the palindromic numbers. First we can see that the biggest number of a given length (all nines) is a palindromic number. This means that, if we treat that case separately (which is pretty easy, because in those cases the answer is 100...001 with as little zeroes as needed to have greater length) we are left with a case in which the return has exactly the same length as the input.
Now, let's suppose we have both the input number and the answer, and we seek, from left to right, the first position at which they differ. Of course, the digit in that position in the result must be strictly greater than the digit in the input. We also want that position to be as far to the right as possible, to keep the result low. The lowest palindromic number that has the first half equal to the input is the result of taking that half and appending its reversed form (if the number of characters in the input n is odd), then taking the first (n-1)/2 characters, then the middle character, and then the first (n-1)/2 again, but reversed. If this number is greater than the input, we are done. If not, we have to add 1 to the middle or both middle (in case n is even) digits and we are done (you can see this will surely result in a number greater than the input).
Wait! What if the middle or both middle digits are 9? Well, in that case, we turn them to zero and add 1 to the first character to the left and the first to the right. If those are also zero, we turn them to zero and move again to the left and right.
An example of the behavior as explained so far:
Input: 123999456
First result: 123999321
Since this is not greater than the input, we continue.
123999321 -> 123909321 -> 123000321 -> 12400421
^ ^ ^ ^ ^
middle digit move to the
right and left
Note that eventually you'll reach a non-9 number because the input is not all 9s, so
if the first result IS all 9s, it will be greater than the input and you'll return
that without reaching the "increase the middle" part. For a clear solution, see
antkar's
implementation.
PrefixFreeSubsets
Used as: Division One - Level Two:
This problem had a pretty simple theoretical solution that lead to a lot of different implementations. The basic idea was to insert every word into a trie. Then you would simply have a tree in which some nodes are marked (the ones in which a word ends). For those, you need to find the number of subsets S such that no node in S has a predecessor in S (note that in a trie predecessor nodes represent prefixes).
Value 500 Submission Rate 227 / 367 (61.85%) Success Rate 176 / 227 (77.53%) High Score Triple_M for 496.59 points (2 mins 21 secs) Average Score 332.21 (for 176 correct submissions)
This can be done recursively. For a node, the number of subsets on the subtree that starts on it is simply the product of the same function on all its childs, because they are all prefix independent. If a node is marked (i.e., represents a word in words) then add 1 to that product to represent the subset that contains that word (since the word represented is a prefix of all its childs, there is no way to combine those).
The actual implementation varied a lot from one coder to the other. As a trick, it was good to notice that in a sorted (in lexicographic order) array, all prefixes appear before their predecessors. Also, if the subsets are seen as subsequences of the sorted sequence, each subset only needs to check consecutive elements to see if it is prefix-free (think for a while on why this happens). This leads to a really short dynammic programming solution. You can see Triple_M's submission for a clear example of this refined approach.
LongLongNim
Used as: Division One - Level Three:
This problem was inspired, of course, in the old good Nim with some simplified rules, but also with a really really really long duration.
Value 1000 Submission Rate 103 / 367 (28.07%) Success Rate 46 / 103 (44.66%) High Score Petr for 864.48 points (11 mins 37 secs) Average Score 563.37 (for 46 correct submissions)
The way to solve the game is pretty easy. Since there are no ties and the game is always finite, we know that for each n either there is a winning strategy for the first player or there is a winning strategy for the second player. We'll call n a winning (W) state if the player in turn wins when n coins are left and losing (L) otherwise. Of course all n that are less than the minimum element in moves are L. Then, each n is W if and only if there exists an element m in moves that is less than or equal to n and such that n-m is L (this means, there is a valid play that leaves a losing state to your rival). This leads to a straightforward implementation which gets the fact calculated for every n in O(maxN*k) where k is the number of elements on moves (the k factor could even be eliminated by doing bit tricks). Since maxN is insanely big, we need something even better.
The first thing to notice in the constraints is the 22 as the maximum move. This was a big clue to the solution. As you can see from the previous paragraph, each n only depends on the previous states n-m with m in moves. Since the maximum m is 22, we can say n depends in the state of n-1, ...,n-22. This can be represented as a 22 character long string of W's and L's (or as a binary number). Not only n depend only on that 22 character long string, the entire behavior from that moment on depends only on those 22 characters, because the string in which n+1 depends is simply appending the state of n at the end and removing the first character (that becomes unnecessary, because is more than 22 away from n>+1). Altogether, this means that after at most 222 numbers there's an indentifiable cycle, which can be used to calculate the rest of the moves without doing all the process. See Petr's code for a clear implementation.
