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.

Indeed, the challenge phase brought 117 failures and the cutoff fell to 251.80. Chief among the challengers was dzetkulict whose 8 challenges put him above the cutoff by themselves. HardCoder was next with 6, followed by the reliable natori at 4. Yet these were far from all the failures, and during system tests, the cutoff dropped all the way to 235.40 meaning that a good score on the easy problem was all you needed to advance. However, this was too high for as many as 6 reds, including reid and mathijs (who would have made it but for a failed challenge).

The Problems

FloorTiling

Used as: Division One - Level One:

Value 250

Submission Rate 345 / 361 (95.57%)

Success Rate 311 / 345 (90.14%)

High Score nullspace for 248.58 points (2 mins 9 secs)

Average Score 219.96 (for 311 correct submissions)

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 + (width-off)%size;
            off+=offset;
            off = off % size;
        }
        return ret;
    }

PartyGame

Used as: Division One - Level Two:

Value 500

Submission Rate 221 / 361 (61.22%)

Success Rate 121 / 221 (54.75%)

High Score Eryx for 481.84 points (5 mins 33 secs)

Average Score 324.68 (for 121 correct submissions)

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.

The first step to solving this problem is dynamic programming. If we know the expected number of moves required for all positions k > j, then we can calculate the number of moves required for position j. First count the number of positions that are red and that we could reach (with moves of size 1 to N). Next add up the expected values for all the reachable positions that are green. Lets say that there are R reachable red positions, and G reachable green position. In this case, the expected number of moves, assuming that we get to one of the green squares is going to be sum/G where sum is the sum from the expected values of the green squares. Now, G/(R+G) percent of the time we will end up on one of the green squares in one roll, while the rest of the time, we will have to reroll. If we reroll, the situation is the same, since we haven't moved. Eventually, we will get a roll that lets us move though, so we will always have to add in the sum/G part.

This is where the math comes in. R/(R+G) times we will have to roll again. This means that (R/(R+G))² times we will have to roll two more times, and so on. This gives us a sequence, the sum of which is the expected number of times we must roll before we hit a green square:

    1 + (R/(R+G))¹ + (R/(R+G))² + (R/(R+G))³ + ...

This sequence if of the form 1 + x + x² + ... and it adds up to 1/(1-x), 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:

Value 1000

Submission Rate 111 / 361 (30.75%)

Success Rate 27 / 111 (24.32%)

High Score bladerunner for 778.25 points (16 mins 9 secs)

Average Score 592.18 (for 27 correct submissions)

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₂, 00100₂ and 11000₂. 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 & (mask-1)) == 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;
}

By lbackstrom
TopCoder Member