Google codejam round 1A

My objective for this match was to be in the first 333. Let us see how it goes. At this moment there are 5 minutes left for the match. But In fact it was 30 minutes ago that I decided to do other things other than paying attention to the contest. C seemed like unapproachable to me under the duration of the contest.

Problem A - Password problem

Statement

It seems google are aware that this contest makes programming contests mainstream, as this problem included even a tutorial to explain the common trope that is to calculate the minimum expected number of moves.

My solution involves simply devising a function f(x) that returns the probability at least one of the first x keystrokes is wrong. After we make this function, it is possible to see for example that the expected amount of keystrokes you type after deciding to erase 5 keys is: 5 + (B-A+5) + 1 * f(A - 5)*(B+1). Because we erase 5 characters, then type the remaining (B-A+5) characters, press enter and there is a f(A - 5) probability that it is all wrong.

f(x) can be calculated using dynamic programming. Let p(x-1) be the probability (x-1)-th is right. Then either the key is correct or not: f(x) = (1 - p(x-1)) + p(x-1) * f(x-1). - If it is correct, then we need to multiply the probability that the other (x-1) keys are wrong.

double solve(int A, int B, double* p) {
    // dp[A]: probability you mistyped at least one of the first A characters.
    double dp[A+1];
    dp[0] = 0.0;
    for (int i=1; i<=A; i++) {
        dp[i] = (1 - p[i-1]) + p[i-1] * dp[i-1];
    }
    
    // give up typing, just press enter, it will be wrong all the time
    double giveup = 2 + B;
    // finish it, type the rest, press enter
    double finish = (B - A) + 1 + dp[A]*(1 + B);
    double backspace = finish;
    // press backspace X times (including 0, which is the same as finish).
    for (int back = 1; back <= A; back++) {
        backspace = std::min(backspace, back + (B - A + back) + 1 + dp[A-back]*(1 + B) );
    }
    return std::min(giveup, backspace );
    
    
}

Problem B - Kingdom Rush

Statement

At first I was unsure I could solve B-large. Decided that it was best to first do B-small, then use its results to verify B-large should I think of it. Maybe this was a bad idea, because B-large turned to be far easier than I thought, and the delay caused by solving two problems instead of one was the difference between top 100 and pathetic top 200 :).

The idea in B-large is to always pick the level that gives more stars. Let us say you have a list of amounts of stars you already acquired from each level and the current number of stars. According to your current state, some levels can give you 2 stars, some 1 stars and some can't be solved yet - So, pick one that gives you 2 stars. This should be correct, because all 2-stars levels give you the same benefit and will not make you unable to take other levels (the opposite, in fact).

But do not rush into things, what to do if all levels can give you at most one star? Not all the levels are the same here. One of those levels may be better to take later because with more stars you would take 2 stars from that level in one game. It is better to pick the 1-star level with the largest b_i, this way it is less likely that picking another set of games before this game will allow you to take this level and win 2 stars in one try.

#define make_triple(a,b,c) make_pair(a, make_pair(b,c))
int solve(int N, int* a, int* b) {
    int stars = 0, games = 0;
    int got[N];
    fill(got, got+N, 0);
    const int INF = 3*N;
    while (stars < 2*N) {
        // We use STL pairs for tie breaking purposes.
        pair<int, pair<int,int> > best = make_triple(0,0,-1);
        for (int i=0; i<N; i++) {
            if (got[i] == 1) {
                if (b[i] <= stars) {
                    //can do...
                    best = std::max(best, make_triple(1, INF, i) );
                }
            } else if (got[i] == 0) {
                if (b[i] <= stars) {
                    best = std::max(best, make_triple(2, INF, i) );
                } else if (a[i] <= stars) {
                    best = std::max(best, make_triple(1, b[i], i) );
                }
            }
        }
        int p = best.second.second;
        if (p == -1) {
            return -1;
        }
        games++;
        //cout << "game "<<games<<" : "<<p<<endl;
        if (got[p] == 1) {
            got[p] = 2;
            stars++;
        } else if (got[p] == 0) {
            got[p] = best.first;
            stars += got[p];
        }
        
    }
    return games;
}

B-small is harder to explain, but its main advantage is that you do not need to prove anything and there is no risk that the solution is wrong. The maximum number of levels is 10. And the list has for each game, 3 different values (the number of stars you got from it, 0, 1, 2). There are only at most 3¹⁰ possibilities for a state. And , let us say that for each possible state, you tried all possible level choices and picked the best one. This dynamic programming would solve the problem.