 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
|
||||||||
| ||||||||||
|
||||||||||
| ||||||||||
|
||||||||||
|
Petr wins Room 3
The challenge phase proved very exciting as Petr extended his already substantial lead with six successful challenges. As long as his hard submission held up, he was ensured a spot in the finals. While the system tests managed to take down two of the remaining hard submissions, neither of them was Petr's and so he coasted into the finals. In second, bmerry was the the only other coder to solve the hard problem successfully. Eryx, Abednego, KOTEHOK, and pparys will all get a second chanced later today. CodeSetby lbackstromCompetitors should have been familiar with many of the concepts in this problem. Prefix-free encodings can be represented as a binary tree, where the leaves are the codes. Thus, the number of valid codes of size k is just the number of binary trees with labeled leaves. Coders with a strong math background will immediately recognize that this value can be computed in closed form using Catalan numbers. However, the fact that we must include our favorite bit string throws a wrench in this simple elegant solution, and now we need to do a bit of dynamic programming to get the answer. First, we note that the number of binary trees with k leaves, Ck can be computed as the sum from i=1 to k-1 of Ci*Ck-i. This works because we can think of installing a split at the root dividing the leaves into groups of size i and k-i. Now, to figure things out including the favorite, we can think of our favorite sequence as just being a sequence of zeros. Then, when we compute the sum mentioned above, we need to add another parameter, the length of the sequence of zeros that must be included. This value will either be an integer, or null, where null indicates that the sequence of zeros has gone down another path, so it doesn't apply. So, in the case where this parameter is not null, our recurrence changes to compute Ck,j, where j is the length of the sequence of zeros that must be included, by taking the sum over i of Ci,j-1*Ck-i,null. In other words, we send the sequence of zeros down the left branch, which trims off the leading zero, hence reducing j by 1. The computation of Ck,null is as discussed for the case where we don't need to worry about the favorite. The last thing to think about are the base cases, but these are straightforward, and can be seen in the code below.
int[][] a = new int[100][100];
int go(int n, int k){
if(n == 1) return k <= 0 ? 1 : 0;
else if(n<1 || k == 0)return 0;
if(a[n][k+1]>0)return a[n][k+1];
int ret = 0;
for(int i= 1; i<n; i++){
ret += go(i,k==-1?-1:k-1)*go(n-i,-1);
}
return a[n][k+1]=ret;
}
public int numSets(int n, String favorite){
return go(n,favorite.length());
}
CCWTurningby lbackstromIt turns out that a brute force solution will solve this problem with plenty of time to spare. In other words, for each segment in the path, branch on all possible point we could put the next point. It's not hard to convince yourself that there will be at most 2 points. However, 230 is too big, and so we need to work a bit harder to convince ourselves that the brute force method will indeed run fast enough. Consider two adjacent segment lengths, pi and pi+1. If pi+1 %le; pi, then there is only one place we can put the end point of pi+1 (try drawing a circle with a directed chord and you'll quickly convince yourself). This leaves the case where pi+1 > pi. In this case, there are indeed two places we could potentially put the endpoint of pi+1. However, if pi+2 > pi+1, then one of these two placements will lead to a dead end. Furthermore, if pi+2 ≤ pi+1, there is only one choice. In other words, when we branch two ways, only one of those two ways can branch again. Once you convince yourself that things will be fast enough, its just a bit of geometry to implement everything. Repeated Additionby lovroStart off by aligning the rightmost (least significant) digits of the number we're adding to and X. Let N be the number written on paper. Observe that, when doing long addition, the carry-over between digits is either 0 or 1. Consider how Ni (digit i of N, with digit 0 being the least significant) changes when X is added once, depending on Xi (the corresponding digit in X):
Knowing that we will be doing exactly (B-A)/X additions, the only unknowns in the list above are the amounts of carry-over between digits. If we knew carryi, the total amount of carry-over coming out of position i when doing all the additions, we could calculate the exact number of times each of the digits changes:
For a single position, carry-over is generated when the digit in that position passes the boundary between 9 and 0. If we write the total amount that is added to a position, the amount of carry-over is obtained by dropping the least significant digit of that total. For example, if we start off at 0 and add 7 sixteen times, we will have totalled 112; the digit itself will be 2 and will have will generated carry-over 11 (of 16) times. We also have to account for carry-over from the previous digit. The final formula for the total amount of carry-over generated in position i is carryi = floor((Ai + (B-A)/X*Xi + carryi-1) / 10). The final quirk in the problem was to handle newly appearing digits as not changing. |
    |
