Online Round 2 August 24, 2005 Match summary
The competition heated up with round 2 of the TCO. Out of 400 excellent coders,
only 200 could advance. Most coders were able to solve
the easy problem without too much trouble, and many coders moved on to the medium
within a few minutes. In fact, some of the fastest coders had submitted all three
problems within half an hour of the start. As the seconds ticked away, however, a number of big
names had yet to submit anything but the easy problem. Yarin, mathijs and
natori were still working on a second problem after one hour. Yarin managed to
get his 1000 pointer submitted with about 10 minutes left though, and no one was
worried about natori with his reputation for getting challenges (though he
submitted the medium in the final seconds just in case). But at the end of the
coding phase, the cutoff stood at 433.96  a tad above natori's 431.24, and far
above mathijs' 242.22. But, all the resubmissions of the medium and hard boded
well for a rash of failures. The ProblemsFloorTilingUsed as: Division One  Level One:
The best way to do this problem is to just iterate over the rows. The first row has an offset of 0, the next an offset of offset, the next 2*offset and so on. For each row, the leftmost tile starts at the offset of that row, modulo the size of the tile. Once you've figured this out, its just a bit of simple math to figure out the gap to the left and right of the tiles: public int tile(int size, int offset, int width, int height){ int off = 0; int ret = 0; for(int i = 0; i<height; i++){ ret += off + (widthoff)%size; off+=offset; off = off % size; } return ret; }PartyGame Used as: Division One  Level Two:
This problem may have seemed awfully similar to the ChutesAndLadders problem
from a few weeks ago. However, the solution turns out to be quite different.
While that problem only required a simulation of the game, this one required
that you do a bit of math to figure things out. 1 + (R/(R+G))^{1} + (R/(R+G))^{2} + (R/(R+G))^{3} + ...This sequence if of the form 1 + x + x^{2} + ... and it adds up to 1/(1x), which is 1/(1(R/(R+G))) in this case. With a little manipulation, we can actually reduce the equation to (R+G)/G. Of course we can combine this with the expected value from the reachable green squares and substitute N in for R+G to get (sum+N)/G The only other thing you need to think about a bit are the cases when you roll to or off the end of the field, but this is easily dealt with by considering those positions as green ones with an expected number of rolls of 0. Answer Used as: Division One  Level Three:
A lot of the solutions to this problem timed out. One sure way to avoid that is to do a bit of preprocessing on the input. Build a set of bitmasks for each letter, where each bitmask represents a set of words that might be left after that letter is revealed by a single guess. This can be done by considering each word and letter pair. For each such pair, look at all the other words, and if they have the same letter in all the same places (and nowhere else), then both words would result in the same letters being revealed from the same guess. For instance, when the words are {"FOG", "DOG", "ANT", "CAT", "RAT"} there are three bitmasks corresponding to the three sets of letters that might be revealed by an initial guess of 'A': 00011_{2}, 00100_{2} and 11000_{2}. These correspond to having no 'A', an 'A' in the first position, and an 'A' in the second position, respectively. Here is some code to find all the masks. m = new int[26][18];//masks go in here c = new int[26];//says how many masks for a particular letter for(int i = 0; i<26; i++){ boolean[] u = new boolean[words.length]; for(int j = 0; j<words.length; j++){ //if a word is already in some mask, don't consider it again if(u[j])continue; int mask = 1<<j; for(int k = j+1; k<words.length; k++){ boolean ok = true; for(int l = 0; ok && l<words[j].length(); l++){ if((words[j].charAt(l) == i+'A') ^ (words[k].charAt(l) == i+'A')){ ok = false; } } if(ok){ //here we've found that word k has letter i //in the same positions as word j u[k] = true; mask = 1<<k; } } m[i][c[i]++] = mask; } }Once we've done this, the rest of the solution is fairly simple. We write a recursive method (memoized of course) that computes how long it takes to differentiate between some subset of words. Note that once some letters are revealed and the final word has been narrowed down to some subset, we don't actually need to know exactly which letters have been revealed. Now, we do the natural thing to figure out many guesses it will take: consider guessing each letter. When we guess some letter, some of the letters in the word may be revealed. The revealed letters will correspond to one of the bitmasks we precomputed (we don't actually have to think about which letters get revealed, just use the bitmasks). We now have the subset of words that were possible from our previous guesses (the input to the recursive method) and the subset of words possible from the letters revealed. A simple logical AND operation on the two bitmasks gives us the subset of words to consider after this guess. We repeat this process for each possible set of letters revealed by our guess (these correspond to the bitmasks computed) and take the worst case of those. That gives us the number of guesses we need for a particular letter. By repeating for each letter, we find the best letter to guess. //the recursive method int go(int mask){ if((mask & (mask1)) == 0){ //a tricky way to find out if there are //only 0 or 1 things in the bitmask return 0; } //the memoization if(dp[mask]!=0)return dp[mask]; int ret = 1000; a: for(int i = 0; i<26; i++){ //considering guessing letter i int it = 0; for(int j = 0; j<c[i]; j++){ //m[i][j] is a bitmask corresponding to some //set of revealed letters for letter i. int m2 = mask & m[i][j]; //if m2 == mask, it means that guessing letter i will //not give us any new information, so we shouldn't do that if(m2 == mask)continue a; it = Math.max(it,go(m2)+1); } ret = Math.min(ret,it); } return dp[mask] = ret; } 
