Google Code Jam 2014 Qualification Round

===

In the [Google Code Jam Qualifiers](https://code.google.com/codejam/contest/2974486/dashboard), I placed in [20th position](https://code.google.com/codejam/contest/2974486/scoreboard#vf=1), which is one of my best performances in a coding contest. Here, I shall attempt to present an analysis of the problems in an intuitive way.

# Problem A: Magic Trick

In this [problem](https://code.google.com/codejam/contest/2974486/dashboard#s=p0), a magician gives two arrangements of a grid of 16 cards numbered 1 to 16. A volunteer thinks of a card on one of the rows in each of the two grids, and the magician identifies a card that is unique to both rows, if it exists. If there are multiple cards common to both rows, output "Bad magician!";  if there are no cards common to both rows, output "Volunteer cheated!"

To do this, we simply count how many times each card has appeared in a row that the volunteer has picked. This can be stored in an integer array of size 16. If the count for a card is two, it has appeared in both rows. We iterate over those counts -- if there is one card that has a count of 2, then output that card; if there are multiple cards with a count of 2, then output "Bad magician!";  if there are no cards with a count of 2, output "Volunteer cheated!"

~~~
lang c++
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    for(int z=1; z<=N; z++) {
        int a; cin >> a;
        int count[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                int x; cin >> x;
                if(i==a-1) count[x-1]++;
            }
        }
        cin >> a;
        for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                int x; cin >> x;
                if(i==a-1) count[x-1]++;
            }
        }
        int two = 0, ans;
        for(int i=0; i<16; i++) {
            if(count[i] == 2) {
                two++;
                ans = i+1;
            }
        }
        if(two == 1) {
            cout << "Case #" << z << ": " << ans << endl;
        } else if(two == 0) {
            cout << "Case #" << z << ": " << "Volunteer cheated!" << endl;
        } else {
            cout << "Case #" << z << ": " << "Bad magician!" << endl;
        }
    }
    return 0;    
}
~~~

# Problem B: Cookie Clicker Alpha

In this [problem](https://code.google.com/codejam/contest/2974486/dashboard#s=p1), you start with 0 cookies and a production rate of 2 cookies per second. When you can afford to buy a new farm, you can choose either to buy a new farm, or to never buy a new farm again and just keep producing cookies. The goal is to reach `x` cookies. Observe that if you wanted to buy a certain number of farms, it is always better to buy them as soon as possible. 

* Each farm produces cookies at rate `f`.
* Each farm costs `c` cookies.
* The goal is to get `x` cookies.

Suppose that, it takes time `tf` to get `k` farms. Then, the cookie generation rate would be `r = 2 + k*f`, since you start out with a rate of `2` and each of the `k` farms contributes `f`. Immediately after getting the `k` farms, you have no cookies. Now, you can choose to either:

* Never buy a farm again and go for the `x` cookies. At a rate of `r(k) = 2 + k*f`, you'll need time `x/r(k)` to make `x` cookies. The total time is therefore `t(k) = tf(k) + x/r(k)`.
* Save up and buy another farm as soon as possible. At a rate of `r(k) = 2 + k*f`, you'll need time `c/r(k)` to get the farm. Therefore, the new `tf(k+1) = tf(k) + c/r(k)`. 

We now have a recursive definition of `tf` as a function of `k`. Obviously, `tf(0) = 0` at the start. So, we can just iterate our `k` starting at zero. At each `k`, we compute both `t(k)` and `tf(k+1)` using the above formulas. Now we just need the best `t(k)`. Since the function is convex, we can just increase `k` until there is no longer an improvement, i.e. it is no longer the case that `t(k) < t(k-1)`. Here is the code:

~~~
lang c++
#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    int N;
    cin >> N;
    for(int z=1; z<=N; z++) {
        cout << "Case #" << z << ": ";
        long double c, f, x; cin >> c >> f >> x;
        long double t = x/2, _t, tf = 0, r = 2;
        do {
            _t = t;
            tf = tf + c/r; // time to get the requisite number of farms
            r += f;        // rate after getting this many farms
            t = tf + x/r; // time to get x things
        } while(_t > t);
        cout << fixed << setprecision(9) << _t << endl;
    }
    return 0;    
}
~~~

Note that since the problem involves adding lots of small floating point numbers to a big floating point number, floating point additive error will accumulate severely. Using the 64-bit `long double` data type suffices to solve this problem within the desired precision.

# Problem C: Minesweeper Master

In this [problem](https://code.google.com/codejam/contest/2974486/dashboard#s=p2), given dimensions `r, c` of a grid of the Minesweeper game, and a number `m` of mines, we wish to place the mines such that we can click somewhere to solve the game in one click (i.e. reveal all cells not containing mines). We output a grid where mines are denoted by the asterisk `'*'` and empty spots are denoted by the dot `'.'` and the click location is marked by the letter `'c'`. 

There are a number of cases.

**Case 1**: There are `m = r*c-1` mines. Then, there is only one spot without a mine and trivially clicking that spot solves it.

**Case 2**: There is either one column or one row. We can trivially solve this by outputting `c` followed by `r*c-m-1` dots, followed by `m` mines, e.g.

~~~~
    c............**************
~~~~

or

~~~~
    c
    .
    .
    *
    *
~~~~

**Case 3**: There is more than one column and more than one row. Here are some observations: First, it's easier if we just click the top left corner. This is intuitive to me but no attempt to explain why this is the case. Second, the smallest number of empty spots you can have is 4. it looks like this:

~~~~
    c.******
    ..******
    ********
    ********
~~~~

Unlike some other people who have fancy dynamic programming solutions, mine is a simple greedy approach. First, we fill the grid with mines and initialize the position as shown above. Where possible, we grow the area of emptiness until we have exactly the correct number of mines. The way we grow the empty area is straightforward: we alternatingly grow rightwards along the first two rows and downwards along the first two columns. When it is no longer possible to grow like this, we just fill empty out the remaining region column by column, left to right, top to bottom. 

Here is an interactive demo of how it works:


???
<ul>
<li> <code>r</code>: <input type="text" id="r" value="13"/></li>
<li> <code>c</code>: <input type="text" id="c" value="21"/></li>
<li> <code>m</code>: <input type="text" id="m" value="100"/></li>
</ul>
<input type="button" id="restart" value="restart">
<pre id="minesweeper"></pre>
???

Can you see why it works?

First, it avoids bad things like:

~~~~
    c...**     001?**
    ...*** --> 234***
    ******     ******
~~~~

since it grows the first two rows at the same time and the first two columns at the same time. Second, it avoids bad things like:

~~~~
    c....*     00002*
    .....* --> 23213*
    ***..*     ***??*
~~~~

since it fills out the rest of the rows and columns in a monotonic way. Third, it can reach all possible number of mines except the imposible cases. It is harder to show this is true, but it seems intuitive to me.

Here's my code:

~~~
lang c++
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    for(int z=1; z<=N; z++) {
        cout << "Case #" << z << ": " << endl;
        int c, r, m; cin >> r >> c >> m;
        int _ = c*r - m;
        if(_ == 1) {
            for(int i=0; i<r; i++) {
                for(int j=0; j<c; j++) {
                    cout << ((i||j)?'*':'c');
                } cout << endl;
            }
        } else if(c == 1) {
            cout << "c\n";
            for(int i=1; i<_; i++) {
                cout << "." << endl;
            }
            for(int i=_; i<r; i++) {
                cout << '*' << endl;
            }
        } else if(r == 1) {
            cout << "c";
            for(int i=1; i<_; i++) {
                cout << '.';
            }
            for(int i=_; i<c; i++ ) {
                cout << '*';
            } cout << endl;
        } else if(_ < 4) {
            cout << "Impossible" << endl;
        } else {
            char s[60][60];
            for(int i=0; i<r; i++) {
                for(int j=0; j<c; j++) {
                    s[i][j] = '*';
                }
                s[i][c] = '\n';
                s[i][c+1] = '\0';
            }
            s[0][0] = 'c';
            s[0][1] = '.';
            s[1][0] = '.';
            s[1][1] = '.';
            _-=4;
            int zxcv = 0, x = 2, y = 2;
            while(_ > 1) {
                zxcv = 0;
                if(_ > 1 && x < c) {
                    s[0][x] = '.';
                    s[1][x] = '.';
                    x++;
                    _-=2;
                    zxcv = 1;
                }
                if(_ > 1 && y < r) {
                    s[y][0] = '.';
                    s[y][1] = '.';
                    y++;
                    _-=2;
                    zxcv = 1;
                }
                if(!zxcv) break;
            }
            for(int j=2; j<x; j++) {
                for(int i=2; i<y; i++) {
                    if(_ > 0) {
                        s[i][j] = '.';
                        _--;
                    } else {
                        break;
                    }
                }
            }
            if(_ > 0) {
                cout << "Impossible" << endl;
            } else
            for(int i=0; i<r; i++) {
                cout << s[i];
            }
        }
    }

    return 0;    
}
~~~

# Problem D: Deceitful War

In this [problem](https://code.google.com/codejam/contest/2974486/dashboard#s=p3), Naomi and Ken play a game called War. They both start out with `n` items of weights between 0 and 1. Both players don't know their opponent's blocks' weights. On each move, Naomi selects a block and announces its weight. Then ken selects a block and weighs it against Naomi's block, on a balance scale. Whoever has the heavier block wins a point. Then both blocks are discarded. This is repeated `n` times in total. Naomi may try to deceive Ken by playing a game called Deceitful War. Here, Naomi knows all of Ken's blocks' weights, and she may lie about her block's weight when playing it (without revealing her deception).

Ken's strategy is to play his lightest block that beats Naomi's block. 

Naomi's strategy is to play her blocks in increasing order. Hopefully, by the time Naomi reaches her heavier blocks, Ken would not have any more heavy blocks.

Naomi's deceitful strategy is to again play in increasing order. If her lightest block is lighter than Ken's lightest block, she is going to lose, inevitably, so she would claim her block is of a weight just less than Ken's heaviest block. This would bait Ken into playing his heaviest block. If Naomi's lightest block is heavier than Ken's lightest block, she would claim it weights 0.9999 (or arbitrarily close to 1, the maximum weight). Sensing an inevitable loss, Ken would play his lightest block. 

The trick is to observe that Deceitful War is exactly the same as just War with the roles reversed -- i.e, Ken plays a block, announces its weight, and then Naomi selects her own block.

Here is my code:

~~~
lang c++
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    for(int z=1; z<=N; z++) {
        cout << "Case #" << z << ": ";
        int n; cin >> n;
        long double *x = new long double[n], *y = new long double[n];
        for(int i=0; i<n; i++) cin >> x[i];
        for(int i=0; i<n; i++) cin >> y[i];
        sort(x, x+n);
        sort(y, y+n);

        int i=0, j=0;
        for(; i<n; i++, j++) {
            if(j>=n) break;
            while(x[j] < y[i] && j < n) j++;
            if(j>=n) break;
            // cerr << "       " << x[j] << " beats " << y[i] << endl;
        }
        cout << i << " ";

        i=0, j=0;
        for(; i<n; i++, j++) {
            if(j>=n) break;
            while(y[j] < x[i] && j < n) j++;
            if(j>=n) break;
            // cerr << "       " << y[j] << " beats " << x[i] << endl;
        }
        cout << n-i << endl;
    }

    return 0;    
}
~~~

Hope that helps!

???
<script>
var grid = [];

var I;

function draw(remaining) {
    if(remaining < 0) {
        document.getElementById('minesweeper').innerHTML = 'Impossible!';
        return;
    }
    var g = [];
    for(var i=0, _i = grid.length; i<_i; i++) {
        g[i] = grid[i].join('');
    }
    document.getElementById('minesweeper').innerHTML = g.join('\n') 
        + '\n\nRemaining mines to clear: ' + remaining;
}

var r, c, remaining, x, y, ii, jj;

function init() {
    if(I) clearInterval(I);
    grid = [];
    r = parseInt(document.getElementById('r').value), 
    c = parseInt(document.getElementById('c').value),
    m = parseInt(document.getElementById('m').value);
    if(r != r || c != c || m != m || r<=0 || c<=0 || m<=0 || m >= r*c) {
        document.getElementById('minesweeper').innerHTML = 'Invalid input.';
        return;
    }
    if(r == 1 || c == 1 || m == r*c-1) {
        document.getElementById('minesweeper').innerHTML = 'See Cases 1 and 2.';
        return;
    }
    for(var i=0; i<r; i++) {
        grid[i] = [];
        for(var j=0; j<c; j++) {
            grid[i][j] = '*';
        }
    }
    grid[0][0] = 'c';
    grid[0][1] = grid[1][0] = grid[1][1] = '.';
    remaining = r*c - m - 4;
    x = y = ii = jj = 2;
    draw(remaining);
    I = setInterval(compute, 200);
}

function compute() {
    if(remaining <= 0) return;
    if(remaining > 1 && x < c && x < y) {
        grid[0][x] = grid[1][x] = '.';
        remaining -=2;
        x++;
    } else if (remaining > 1 && y < r) {
        grid[y][0] = grid[y][1] = '.';
        remaining -=2;
        y++;
    } else if(remaining > 1 && x < c) {
        grid[0][x] = grid[1][x] = '.';
        remaining -=2;
        x++;
    } else if(ii < y && jj < x) {
        grid[ii++][jj] = '.';
        remaining--;
        if(ii >= y) {
            ii = 2; jj++;
        }
    } else {
        remaining = -999;
    }
    draw(remaining);
    if(remaining <= 0) {
        clearInterval(I);
    }
}

document.getElementById('r').onchange = init;
document.getElementById('c').onchange = init;
document.getElementById('m').onchange = init;
document.getElementById('restart').onclick  = init;

init();
</script>