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
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
#include
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:
???

r:

c:

m:

???
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
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 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 0) {
s[i][j] = '.';
_--;
} else {
break;
}
}
}
if(_ > 0) {
cout << "Impossible" << endl;
} else
for(int i=0; i
#include
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> x[i];
for(int i=0; i> y[i];
sort(x, x+n);
sort(y, y+n);
int i=0, j=0;
for(; i=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) 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!
???