# Google Code Jam Archive — Qualification Round 2014 problems

## Overview

Google Code Jam 2014 is off and running! We have 20,595 advancers out of 25,462 people who correctly solved at least one input, and 49,066 registrants. People correctly solved problems from 165 different regions of the world, using 88 different programming languages. All those numbers are records for us!

We opened with a magic trick, and a game about gathering cookies, both of which had solutions that were straightforward -- at least in principle. Next came Minesweeper Master, which had an astonishingly low success rate: under 50% of people who thought they had solved it eventually did; and of our 25 fastest finishers in the round, 11 of them got it wrong on the first try. Last came Deceitful War, a problem that was harder to understand but easier to solve, which asked you to get inside the heads of both an honest game player and a dishonest one.

There are three more rounds to go before the Finals, and we are just getting started. We hope to see all the advancers in the First Rounds!

Cast

Problem A. Magic Trick Written and prepared by Ahmed Aly.

Problem B. Cookie Clicker Alpha Written by Bartholomew Furrow. Prepared by Sean Henderson and Bartholomew Furrow.

Problem C. Minesweeper Master Written and prepared by Igor Naverniouk.

Problem D. Deceitful War Written by Bartholomew Furrow. Prepared by Jonathan Wills and Bartholomew Furrow.

Contest analysis presented by Felix Halim, Topraj Gurung, Zong-Sian Li and Bartholomew Furrow. Solutions and other problem preparation by Jonathan Paulson, Jonathan Shen, Khaled Hafez, Mahbubul Hasan, Mohammad Kotb, Patrick Nguyen and Steve Thomas.

## A. Magic Trick

Note: To advance to the next rounds, you will need to score 25 points. Solving just this problem will not give you enough points.

### Problem

Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!

The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.

Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?

You decide to write a program to help you understand the magician's technique. The program will be given the two arrangements of the cards, and the volunteer's answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.

Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there's no card consistent with the volunteer's answers (the volunteer cheated).

### Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer: the answer to the first question. The next 4 lines represent the first arrangement of the cards: each contains 4 integers, separated by a single space. The next line contains the answer to the second question, and the following four lines contain the second arrangement in the same format.

### Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1).

If there is a single card the volunteer could have chosen, y should be the number on the card. If there are multiple cards the volunteer could have chosen, y should be "Bad magician!", without the quotes. If there are no cards consistent with the volunteer's answers, y should be "Volunteer cheated!", without the quotes. The text needs to be exactly right, so consider copying/pasting it from here.

### Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ both answers ≤ 4.
Each number from 1 to 16 will appear exactly once in each arrangement.

### Sample

Sample Input
```3
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
```
Sample Output
```Case #1: 7
Case #3: Volunteer cheated!
```

### Introduction

Cookie Clicker is a Javascript game by Orteil, where players click on a picture of a giant cookie. Clicking on the giant cookie gives them cookies. They can spend those cookies to buy buildings. Those buildings help them get even more cookies. Like this problem, the game is very cookie-focused. This problem has a similar idea, but it does not assume you have played Cookie Clicker. Please don't go play it now: it might be a long time before you come back.

### Problem

Once you have X cookies that you haven't spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy.

### Example

Suppose C=500.0, F=4.0 and X=2000.0. Here's how the best possible strategy plays out:

2. After 250 seconds, you will have C=500 cookies and can buy a farm that produces F=4 cookies per second.
6. Another farm will cost 500 cookies, which you can buy after 50 seconds.
8. Another farm would cost 500 cookies, but it actually makes sense not to buy it: instead you can just wait until you have X=2000 cookies, which takes about 142.8571429 seconds.
Total time: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 seconds.

Notice that you get cookies continuously: so 0.1 seconds after the game starts you'll have 0.2 cookies, and π seconds after the game starts you'll have 2π cookies.

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated real-valued numbers: C, F and X, whose meanings are described earlier in the problem statement.

C, F and X will each consist of at least 1 digit followed by 1 decimal point followed by from 1 to 5 digits. There will be no leading zeroes.

### Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of seconds it takes before you can have X delicious cookies.

We recommend outputting y to 7 decimal places, but it is not required. y will be considered correct if it is close enough to the correct number: within an absolute or relative error of 10-6. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

### Limits

Memory limit: 1 GB.
1 ≤ T ≤ 100.

#### Small dataset

Time limit: 60 seconds.
1 ≤ C ≤ 500.
1 ≤ F ≤ 4.
1 ≤ X ≤ 2000.

#### Large dataset

Time limit: 120 seconds.
1 ≤ C ≤ 10000.
1 ≤ F ≤ 100.
1 ≤ X ≤ 100000.

### Sample

Sample Input
```4
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0
```
Sample Output
```Case #1: 1.0000000
Case #2: 39.1666667
Case #3: 63.9680013
Case #4: 526.1904762
```

### Note

Cookie Clicker was created by Orteil. Orteil does not endorse and has no involvement with Google Code Jam.

## C. Minesweeper Master

### Problem

Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.

In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don't contain mines have been revealed, the game ends, and you win.

For example, an initial configuration of the board may look like this ('*' denotes a mine, and 'c' is the first clicked cell):

```*..*...**.
....*.....
..c..*....
........*.
..........
```
There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:
```*..*...**.
1112*.....
00012*....
00001111*.
00000001..
```
At this point, there are still un-revealed cells that do not contain mines (denoted by '.' characters), so the player has to click again in order to continue the game.

You want to win the game as quickly as possible. There is nothing quicker than winning in one click. Given the size of the board (R x C) and the number of hidden mines M, is it possible (however unlikely) to win in one click? You may choose where you click. If it is possible, then print any valid mine configuration and the coordinates of your click, following the specifications in the Output section. Otherwise, print "Impossible".

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three space-separated integers: R, C, and M.

### Output

For each test case, output a line containing "Case #x:", where x is the test case number (starting from 1). On the following R lines, output the board configuration with C characters per line, using '.' to represent an empty cell, '*' to represent a cell that contains a mine, and 'c' to represent the clicked cell.

If there is no possible configuration, then instead of the grid, output a line with "Impossible" instead. If there are multiple possible configurations, output any one of them.

### Limits

Memory limit: 1 GB.
0 ≤ M < R * C.

#### Small dataset

Time limit: 60 seconds.
1 ≤ T ≤ 230.
1 ≤ R, C ≤ 5.

#### Large dataset

Time limit: 120 seconds.
1 ≤ T ≤ 140.
1 ≤ R, C ≤ 50.

### Sample

Sample Input
```5
5 5 23
3 1 1
2 2 1
4 7 3
10 10 82
```
Sample Output
```Case #1:
Impossible
Case #2:
c
.
*
Case #3:
Impossible
Case #4:
......*
.c....*
.......
..*....
Case #5:
**********
**********
**********
****....**
***.....**
***.c...**
***....***
**********
**********
**********
```

## D. Deceitful War

This problem is the hardest problem to understand in this round. If you are new to Code Jam, you should probably try to solve the other problems first.

### Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets N identical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works:

1. Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player's blocks.
2. They repeat the following process N times:
1. Naomi chooses one of her own blocks, with mass `ChosenNaomi`.
2. Naomi tells Ken the mass of the block she chose.
3. Ken chooses one of his own blocks, with mass `ChosenKen`.
4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
5. Both blocks are destroyed in a fire.

Naomi has realized three things about War. First, she has realized that she loses a lot. Second, she has realized that there is a unique strategy that Ken can follow to maximize his points without assuming anything about Naomi's strategy, and that Ken always uses it. Third, she has realized that she hates to lose. Naomi has decided that instead of playing War, she will play a game she calls Deceitful War. The great thing about Deceitful War is that Ken will think they're playing War!

Here is how Deceitful War works, with differences between Deceitful War and War in bold:

1. Each player weighs each of his or her own blocks. Naomi also weighs Ken's blocks while he isn't looking, so Naomi knows the weights of all blocks and Ken only knows the weights of his own blocks.
2. They repeat the following process N times:
1. Naomi chooses one of her own blocks, with mass `ChosenNaomi`.
2. Naomi tells Ken a number, `ToldNaomi`, between 0.0kg and 1.0kg exclusive. Ken, who thinks they're playing War, thinks the number Naomi just told him is `ChosenNaomi`.
3. Ken chooses one of his own blocks, with mass `ChosenKen`.
4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
5. Both blocks are destroyed in a fire.

Naomi doesn't want Ken to know that she isn't playing War; so when she is choosing which block to play, and what mass to tell Ken, she must make sure that the balance scale won't reveal that `ChosenNaomi ≠ ToldNaomi`. In other words, she must make decisions so that:

• `ChosenNaomi > ChosenKen` if, and only if, `ToldNaomi > ChosenKen`, and
• `ToldNaomi` is not equal to the mass of any of Ken's blocks, because he knows that isn't possible.

It might seem like Naomi won't win any extra points by being deceitful, because Ken might discover that she wasn't playing War; but Naomi knows Ken thinks both players are playing War, and she knows what he knows, and she knows Ken will always follow his unique optimal strategy for War, so she can always predict what he will play.

You'll be given the masses of the blocks Naomi and Ken started with. Naomi will play Deceitful War optimally to gain the maximum number of points. Ken will play War optimally to gain the maximum number of points assuming that both players are playing War. What will Naomi's score be? What would it have been if she had played War optimally instead?

### Examples

If each player has a single block left, where Naomi has 0.5kg and Ken has 0.6kg, then Ken is guaranteed to score the point. Naomi can't say her number is ≥ 0.6kg, or Ken will know she isn't playing War when the balance scale shows his block was heavier.

If each player has two blocks left, where Naomi has [0.7kg, 0.2kg] and Ken has [0.8kg, 0.3kg], then Naomi could choose her 0.2kg block, and deceive Ken by telling him that she chose a block that was 0.6kg. Ken assumes Naomi is telling the truth (as in how the War game works) and will play his 0.8kg block to score a point. Ken was just deceived, but he will never realize it because the balance scale shows that his 0.8kg block is, like he expected, heavier than the block Naomi played. Now Naomi can play her 0.7kg block, tell Ken it is 0.7kg, and score a point. If Naomi had played War instead of Deceitful War, then Ken would have scored two points and Naomi would have scored zero.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing a single integer N, the number of blocks each player has. Next follows a line containing N space-separated real numbers: the masses of Naomi's blocks, in kg. Finally there will be a line containing N space-separated real numbers: the masses of Ken's blocks, in kg.

Each of the masses given to Ken and Naomi will be represented as a 0, followed by a decimal point, followed by 1-5 digits. Even though all the numbers in the input have 1-5 digits after the decimal point, Ken and Naomi don't know that; so Naomi can still tell Ken that she played a block with mass 0.5000001kg, and Ken has no reason not to believe her.

### Output

For each test case, output one line containing "Case #x: y z", where x is the test case number (starting from 1), y is the number of points Naomi will score if she plays Deceitful War optimally, and z is the number of points Naomi will score if she plays War optimally.

### Limits

Memory limit: 1 GB.
1 ≤ T ≤ 50.
All the masses given to Ken and Naomi are distinct, and between 0.0 and 1.0 exclusive.

#### Small dataset

Time limit: 60 seconds.
1 ≤ N ≤ 10.

#### Large dataset

Time limit: 120 seconds.
1 ≤ N ≤ 1000.

### Sample

Sample Input
```4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458
```
Sample Output
```Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4
```

## Analysis — A. Magic Trick

In the first arrangement, when the volunteer tells the magician the row that contains her card, the magician is able to see a set of four cards in that row. Similarly, in the second arrangement, the magician is able to see another set of four cards in the selected row.

Therefore, after hearing the two volunteer’s answers, the magician will have two sets of cards:
- the first set of four cards that lie in the selected row in the first arrangement, and
- the second set of four cards that lie in the selected row in the second arrangement.

To know which card the volunteer chose, the magician must be able to find exactly one card that is in both sets (i.e., the intersection size of the two sets must be equal to one). If there is more than one card that is in both sets (i.e., the intersection size is bigger than one), then it means the magician can not determine which card the volunteer chose since there are more than one possible card that could have been chosen by the volunteer (the magician did a bad job). If none of the card in the first set is in the second set (i.e., the intersection size is zero), then there is no card consistent with the volunteer's answers (the volunteer cheated).

The sample input covers all three possible cases:

In Case #1, the two sets are {5, 6, 7, 8} and {9, 10, 7, 12}. There is exactly one card (i.e., card 7) that is in both sets, and thus the volunteer chosen card must be 7.

In Case #2, the two sets are {5, 6, 7, 8} and {5, 6, 7, 8}. The card chosen by the volunteer can be any of {5, 6, 7, 8} because all of them contains in both sets. Bad magician!

Lastly, in Case #3, the two sets are {5, 6, 7, 8} and {9, 10, 11, 12}. None of the cards in the first set is in the second set. The volunteer must have cheated!

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — B. Cookie Clicker Alpha

In this problem, we need to decide on the number of cookie farms to buy and also need to decide on when to buy the farms.

The strategy is perhaps surprisingly simple: first, collect enough cookies to buy a farm. Then figure out whether it's faster to buy one farm and then collect X cookies, or simply to collect X cookies now. If it's faster to collect X cookies now, you should do that. If it's faster to buy a farm first, buy that farm and then repeat this process (collect enough cookies to buy another farm...).

It's very easy to say that, but it's not as easy to prove it works. How many farms might you end up buying? If it's in the billions, your program might be too slow, and we never proved it wouldn't be. We also didn't prove that it's best to buy a farm right away as soon as you have enough cookies. The rest of this editorial will go into those questions in detail.

We build the intuition for the solution by using geometry. We represent the problem in the 2d plane. Let the x-axis represent time (in seconds) and the y-axis represent the number of cookies. Initially, we gain cookies at the rate of 2 cookies per second which is shown by line L0 in Figure 1. Let’s say the target number of cookies (X) is 16. We can represent it with line y=16 (LX). This means that if we do not buy any cookie farm then the time it takes to get 16 cookies is given by the intersection between LX and L0. See Figure 1.

Figure 1

Figure 2

Now we discuss the strategy for how early we should buy a cookie farm i.e. should we buy a cookie farm as soon as we have C cookies, or should we wait a little longer before buying a cookie farm? We claim that we should buy a farm as soon as we have C cookies (and not wait any second longer).

Figure 3

In Figure 4, we can observe that the earliest time to buy the first cookie farm is on the intersection of line L0 with line LC (y=C). Then, the earliest time to buy the second cookie farm is on the intersection of line L1 with LC.

Figure 4

A note on doing the actual line intersection computation follows. We want to compute the line intersections between lines L0, L1, L2, etc and y = C or y = X. Let our current line be Ln starting at (Sn, 0) and have a slope of m (i.e. cookies per second after buying n cookie farms). Note that s0 is 0, and m = 2 + n * F. Then the time required to get A cookies is given as: Sn + A / m.

Our solution strategy mentioned above iterates until a winning condition is achieved. But you might be wondering about total iterations needed before we are done. We want to point out that the number of iterations is bounded. In the solution strategy, we noted that the stopping condition for iteration is when we do worse (in terms of time) when buying an additional farm. Let’s formulate that as an equation. Let’s say our current iteration is i with line Li with the next line being Li+1. The intersection between line y = X and Li is given as ti = si + X / (2 + i * F), and similarly intersection between line y = X and Li+1 is given as ti+1 = si+1 + X / (2 + (i + 1) * F). We stop when ti+1 > ti. Note that si+1 - si = C / (2 + i * F). After going through some math, we get i > (X / C) - 1 - (2 / F), which is the iteration when ti+1 becomes bigger than ti. Therefore the iteration should terminate around X / C.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — C. Minesweeper Master

There are many ways to generate a valid mine configuration. In this analysis, we try to enumerate all possible cases and try to generate a valid configuration for each case (if exists). Later, after having some insight, we provide an easier to implement algorithm to generate a valid mine configuration (if exists).

## Enumerating all possible cases

We start by checking the trivial cases:

• If there is only one empty cell, then we can just fill all cells with mines except the cell where you click.
• If R = 1 or C = 1, the mines can be placed from left to right or top to bottom respectively and click on the right-most or the bottom-most cell respectively.

If the board is not in the two trivial cases above, it means the board has at least 2 x 2 size. Then, we can manually check that:

• If the number of empty cells is 2 or 3, it is Impossible to have a valid configuration.
• If R = 2 or C = 2, valid configurations exists only if M is even. For example, if R = 2, C = 7 and M = 5, it is Impossible since M is odd. However, if M = 6, we can place the mines on the left part of the board and click on the bottom right, like this:
```            ***....
***...c
```

If the board is not in any of the above case, it means the board is at least 3 x 3 size. In this case, we can always find a valid mine configuration if the number of empty cells is bigger than 9. Here is one way to do it:

• If the number of empty cells is equal or bigger than 3 * C, then the mines can be placed row by row starting from top to bottom. If the number of remaining mines can entirely fill the row or is less than C - 2 then place the mines from left to right in that row. Otherwise, the number of remaining mines is exactly C - 1, place the last mine in the next row. For example:
• ```            ******        ******
*****.        ****..
......   ->   *.....
......        ......
.....c        .....c
```
• If the number of empty cells is less than 3 * C but at least 9, we first fill all rows with mines except the last 3 rows. For the last 3 rows, we fill the remaining mines column by column from the left most column. If the remaining mines on the last column is two, then last mine must be put in the next column. For example:
• ```            ******        ******
**....   ->   ***...
**....        *.....
*....c        *....c
```

Now, we are left with at most 9 empty cells which are located in the 3 x 3 square cells at the bottom right corner. In this case, we can check by hand that if the number of empty cells is 5 or 7, it is Impossible to have a valid mine configuration. Otherwise, we can hard-coded a valid configuration for each number of empty cell in that 3 x 3 square cells.

Sigh... that was a lot of cases to cover! How do we convince ourselves that when we code the solution, we do not miss any corner case?

## Brute-force approach

For the small input, the board size is at most 5 x 5. We can check all (25 choose M) possible mine configurations and find one that is valid (i.e., clicking an empty cell in the configuration reveal all other empty cells). To check whether a mine configuration is valid, we can run a flood-fill algorithm (or a simple breath-first search) from the clicked empty cell and verify that all other empty cells are reachable (i.e., they are in one connected component). Note that we should also check all possible click positions. This brute-force approach is fast enough for the small input.

The brute-force approach can be used to check (for small values of R, C, M) whether there is a false-negative in our enumeration strategy above. A false-negative is found when there exist a valid mine configuration, but the enumeration strategy above yields Impossible. Once we are confident that our enumeration strategy does not produce any false-negative, we can use it to solve the large input.

## An easier to implement approach

After playing around with several valid mine configurations using the enumeration strategy above, you may notice a pattern: in a valid mine configuration, the number of mines in a particular row is always equal or larger than the number of mines of the rows below it and all the mines are left-aligned in a row. With this insight, we can implement a simpler backtracking algorithm that places mines row by row from top to bottom with non-increasing number of mines as we proceed to fill in the next row and prune if the configuration for the current row is invalid (it can be checked by clicking at the bottom right cell). This backtracking with pruning can handle up to 50 x 50 sized board in reasonable time and is simpler to implement (i.e., no need to enumerate corner / tricky cases).

If the contest time were shorter, we may not have enough time to enumerate all possible cases. In this case, betting on the backtracking algorithm (or any other algorithm that is easier to implement) may be a good idea. Finding such algorithms is an art :).

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Ken's best possible game of War

First, let's think about the best possible outcome for Ken in a game of War. Let's suppose the maximum number of points Ken can get is k; then after a little work convincing yourself, you should see that Ken can achieve that outcome if Ken's k heaviest blocks are played in decreasing order against Naomi's k lightest blocks, also in decreasing order.

That exact pairing likely won't happen, and without knowing Naomi's blocks' weights, Ken doesn't even know what the pairing would be; but Ken can follow a simple strategy to score k points anyway.

## Ken's strategy

Ken's strategy is simple: when Naomi plays a block, Ken beats it with the lightest possible block if he can; and if he can't beat it, he plays his lightest block. It is clear that using such strategy will maximize Ken's winning potential for the following rounds because Ken not only wins one point for this round, but also preserves his heavier blocks for the following rounds.

The following block of text proves that this strategy will earn Ken the maximum possible number of points, k, no matter what Naomi does. If that's obvious to you, or you aren't into formal proofs, go ahead and skip it.

### Proof

In this strategy, to win k points Ken wants to maintain an invariant: after Ken has scored i points, Ken's k-i heaviest blocks will still beat Naomi's k-i lightest blocks. When k-i is zero, Ken cannot win any more points because his heaviest block is lighter than any of Naomi's blocks. Therefore, if that invariant is maintained Ken must have k points when there are no more blocks left.

Proof of invariant:
Suppose Ken has i points. We'll refer to "pairs" of blocks later: Ken has k - i heaviest blocks remaining and his j-th heaviest remaining block is "paired" with Naomi's (k-i-j)-th lightest remaining block. There are three types of blocks Naomi might play:

1. If Naomi plays a block that's heavier than all of Ken's, it isn't from Naomi's lightest k-i blocks. Ken will play his lightest block which isn't from his heaviest k-i blocks, and the invariant is maintained.
2. If Naomi plays a block that's lighter than one of Ken's blocks but isn't from Naomi's lightest k-i blocks, Ken will either beat it with his heaviest block—in which case Naomi's lightest k-i-1 blocks will lose to Ken's heaviest remaining k-i-1 blocks, since nothing has changed about how the remaining blocks are paired—or Ken will beat it with something lighter, in which case his position is obviously no worse. Either way Ken has i+1 points and the invariant is maintained.
3. If Naomi plays a block from her lightest k-i blocks, Ken will either beat it with the block it's paired with, in which case Ken now has i+1 points and the remaining k-i-1 pairs are maintained; or Ken will beat it with something lighter, in which case Ken is clearly no worse off. Either way Ken has i+1 points and the invariant is maintained.

## Naomi's best possible game of War

As we saw in the proof above, Ken can force his maximum possible number of points in War no matter what Naomi does. No wonder Naomi is tired of playing it!

## Naomi's best possible game of Deceitful War

In Deceitful War, however, it turns out that the situation is exactly reversed: as we'll show in the following paragraphs. In War, Ken got the best possible pairings for himself but Naomi will get the best possible pairings for herself in Deceitful War.

## Naomi's strategy for Deceitful War

There are several strategies for Naomi to play Deceitful War optimally. We present one here. Naomi's strategy for that is almost trivial. Assume k is the best possible score Naomi could achieve. Naomi can do score k points by pairing her k heaviest blocks with Ken's k lightest blocks.

Naomi will take her i-th heaviest block and tell Ken that it is heavier than all of Ken's blocks. Ken will believe her and play his lightest block, which is what Naomi wanted. Now Naomi simply has to repeat the process of playing her remaining heaviest blocks from lightest to heaviest and inciting Ken to play his lightest block from lightest to heaviest. After Naomi scores k points, her heaviest block will be lighter than any of Ken's available blocks. Now, since Naomi cannot lie anymore Naomi plays her remaining blocks without lying about their mass.

## Conclusion

It's a particularly beautiful piece of symmetry that Ken can achieve his optimal pairing by being reactive, despite being honest and without information; and Naomi can reverse Ken's advantage by beating Ken's reactiveness with dishonesty and perfect information.

Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Statistics — A. Magic Trick

### Test set 1: 25140 correct solutions (98.7% solve rate)

First
xiaowuc2 3:24
Cypi Python, 4:01
msg555 C++, 4:09
prvak Ruby, 4:42
evima0 4:44
Shortest
ronniepopov -, 2 bytes
GeorgieVell -, 6 bytes
RamIsBack -, 13 bytes
shrey.iitd -, 15 bytes
jatboys1995 -, 17 bytes

## Statistics — B. Cookie Clicker Alpha

### Test set 1: 21736 correct solutions (85.4% solve rate)

First
Kriiii 11:29
xiaowuc2 11:39
Eryx C++, 15:05
Doju C++, 15:11
Lepton.s C++, 15:15
Shortest
ronniepopov -, 2 bytes
Bill2014 -, 2 bytes
GeorgieVell -, 6 bytes
RamIsBack -, 8 bytes
shrey.iitd -, 15 bytes

### Test set 2: 18971 correct solutions (74.5% solve rate)

First
Kriiii 11:29
xiaowuc2 11:39
Eryx C++, 15:05
Doju C++, 15:11
Lepton.s C++, 15:15
Shortest
GeorgieVell -, 6 bytes
RamIsBack -, 8 bytes
xxdcommand -, 51 bytes
pucsdcoder -, 74 bytes
Malkava -, 75 bytes

## Statistics — C. Minesweeper Master

### Test set 1: 3857 correct solutions (15.1% solve rate)

First
Eryx C++, 41:14
facanferff C++, 45:39
Kouprin C++, 50:45
skird C++, 52:14
Corea C++, 53:44
Shortest
jonsmith -, 221 bytes
Howdy -, 258 bytes
gaoxin -, 338 bytes
afkfurion -, 491 bytes
zhyang -, 502 bytes

### Test set 2: 2441 correct solutions (9.6% solve rate)

First
Eryx C++, 41:14
Kouprin C++, 50:45
SnapDragon C++, 56:19
Shortest
yujinwunz -, 702 bytes
JonasVenture -, 825 bytes
yuhang C++, 879 bytes
hpmv Coffeescript, 990 bytes
tana Python, 997 bytes

## Statistics — D. Deceitful War

### Test set 1: 11135 correct solutions (43.7% solve rate)

First
surwdkgo C++, 37:53
ayaze 47:44
Naonao Java, 48:05
brett42 Python, 49:24
Shortest
Liuyichao -, 5 bytes
verb -, 9 bytes
jatboys1995 -, 17 bytes
Linwwww -, 95 bytes

### Test set 2: 10215 correct solutions (40.1% solve rate)

First
surwdkgo C++, 37:53
ayaze 47:44
Naonao Java, 48:05
brett42 Python, 49:24
Shortest
verb -, 11 bytes
JiaYeLi -, 79 bytes
minhaz -, 123 bytes