# Google Code Jam Archive — World Finals 2011 problems

## Overview

The Final round turned out to be unusually difficult. Most contestants started with problem A and later realized that repeated simulation would work for E-small. Moving beyond that, however, proved to be a nearly impossible feat.

The winner, rng..58, ended up being the only contestant to solve the fiendishly difficult E-large. mystic took second place with B-small and D-small on top of A and E-small. meret came very close to taking the top spot, if not for a failed B-large (caused by a 32-bit int overflow). He finished in third.

Congratulations to the winners! We hope to see everybody next year. The 2012 finals will be held in New York City!

Cast

Problem A. Runs Written by Albert Mao and Bartholomew Furrow. Prepared by Jorge Bernadas Saragoza.

Problem B. Rains Over Atlantis Written by Onufry Wojtaszczyk and Bartholomew Furrow. Prepared by Onufry Wojtaszczyk and Jorge Bernadas Saragoza.

Problem C. Program within a Program Written by David Arthur and Jorge Bernadas Saragoza. Prepared by Jorge Bernadas Saragoza and David Arthur.

Problem D. Ace in the Hole Written by David Arthur and Jorge Bernadas Saragoza. Prepared by Bartholomew Furrow.

Problem E. Google Royale Written by David Arthur and Bartholomew Furrow. Prepared by Onufry Wojtaszczyk.

Contest analysis by Bartholomew Furrow and David Arthur.

Solutions and other problem preparation by Jorge Bernadas Saragoza, John Dethridge, Igor Naverniouk, David Arthur, Bartholomew Furrow, Tomek Czajka, and Onufry Wojtaszczyk.

## A. Runs

### Problem

I have a string S consisting of lower-case alphabetic characters, 'a' - 'z'. Each maximal sequence of contiguous characters that are the same is called a "run". For example, "bookkeeper" has 7 runs. How many different permutations of S have exactly the same number of runs as S?

Two permutations `a` and `b` are considered different if there exists some index `i` at which they have a different character: `a[i] ≠ b[i]`.

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each contains a single non-empty string of lower-case alphabetic characters, S, the string of interest.

### Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of different permutations of S that have exactly the same number of runs as S, modulo 1000003.

### Limits

1 ≤ T ≤ 100.
S is at least 1 character long.
Memory limit: 1GB.

#### Small dataset (Test set 1 - Visible)

S is at most 100 characters long.
Time limit: 30 seconds.

#### Large dataset (Test set 2 - Hidden)

S is at most 450000 characters long.
S has at most 100 runs.
The input file will not exceed 1 megabyte in size.
Time limit: 60 seconds.

### Sample

Sample Input
```2
aabcd
bookkeeper
```
Sample Output
```Case #1: 24
Case #2: 7200
```

## B. Rains Over Atlantis

### Problem

Rains fall on the isle of Atlantis, and will erode all the land to nothingness. What you want to know, so that you can organize the evacuation, is how soon it will happen.

You have a map of Atlantis. The map is a square grid, and each square contains the height of the land in that square, in metres, above sea level. All squares outside the map have height 0; all squares with height 0 are water, and all squares with larger heights are land. There are no squares with lower height.

Water can flow from a source square to a target square if the source square and target square share an edge, and if the height of the water in the target square is lower than or equal to the height of water in the source square.

It's raining very quickly, which means that if there is nowhere for the rain water in a square to flow, water in that square will accumulate until there is a square to which the rain water can flow. Squares that are not on the map can accept any amount of flow. For example, the following map:
```5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9
```
Will quickly fill up with water. We'll call the height of water in each square, plus the height of the land, the water level. It will be:
```5 9 9 9 9 9
0 8 9 5 5 5
3 9 9 9 9 9
```

Note that the 0 in the middle of the land, although it's water, is not connected to the outside of the map and so just accumulates water. The 0 on the border of the land, however, is connected to the outside of the map, and so the water from the 8 can flow through it to the outside.

The direction in which water flows is determined by the water level. If there are multiple possible squares where water could flow from one particular source square, the water from that source will flow to the square with the lowest water level (ties don't matter, as you will see).

Now the erosion begins. Each day, a square is eroded—its height decreases—depending on how water is flowing from it. If water is flowing from S to T, then S's height decreases by `min(WaterLevel(S) - WaterLevel(T), M)`. All erosion happens at exactly the same time, at the end of the day. For example, with M=5, the map above will erode to:

```0 4 4 4 4 4
0 3 5 0 2 0
0 4 4 4 4 4
```
After a day's erosion, excess water will flow away: squares with water level higher than a neighbour's water level will lose water until they are of the same height. Water will also accumulate in the same way that it did on the first day. After the first day, this map's water level will become:
```0 4 4 4 4 4
0 3 5 2 2 0
0 4 4 4 4 4
```
After another day of erosion, the map will look like:
```0 0 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
```

...and the Atlanteans will need to escape in a big hurry. Your task is to determine how many days it will take for all the heights to erode to 0.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing three space-separated integers: H, W and M. The first two denote the size of the map, while the third is the maximum amount a square can erode in one day, as described above. H lines follow, each of which contains W space-separated integers. The ith integer on the jth line denotes the height of the square at (i, j).

### Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of days it takes to erode all the island.

### Limits

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

#### Small dataset (Test set 1 - Visible)

1 ≤ H, W ≤ 10.
1 ≤ M ≤ 100.
0 ≤ all heights ≤ 100.
Time limit: 30 seconds.

#### Large dataset (Test set 2 - Hidden)

1 ≤ H, W ≤ 20.
1 ≤ M ≤ 1015.
0 ≤ all heights ≤ 1015.
Time limit: 60 seconds.

### Sample

Sample Input
```2
3 6 5
5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9
3 6 3
3 8 10 11 10 8
7 5 2 12 8 8
6 9 11 9 8 4
```
Sample Output
```Case #1: 3
Case #2: 5
```

In the second case, the water height looks like: ``` 3 8 10 11 10 8 7 7 7 12 8 8 6 9 11 9 8 4 ```

After one day the island looks as follows: ``` 0 5 7 8 7 5 4 5 2 9 8 5 3 6 8 6 5 1 ```

And after the second day: ``` 0 2 4 5 4 2 1 4 2 6 5 2 0 3 5 3 2 0 ```

And the third day: ``` 0 0 1 2 1 0 0 1 2 3 2 0 0 0 2 0 0 0 ```

After the fourth day, things are looking desperate for the Atlanteans: ``` 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 ```

Finally, on the fifth day the last square erodes away. Atlantis lasted for five days; they probably shouldn't have built their city out of brown sugar.

## C. Program within a Program

### Problem

You have a robot on an infinite east-west highway, and it has a cake to deliver. Every mile along the highway, in both directions, there is a lamppost. You want to program the robot to move exactly N lampposts to the east, and release the cake there. The route does not have to be direct, as long as the robot eventually releases the cake in the right place.

Unfortunately, the robot comes equipped with only very little memory, and it is capable of no advanced logic. To control the robot you will have to give it a very simple program at the start that will get it to release the cake at the proper location. This program must be composed of one or more statements, each of which tells the robot what to do under certain conditions. These statements must be in the following format:

```<S> <M> -> <action>
```

which means that if all of the following conditions are met:

1. The robot is in state `S`.
2. The robot is at a lightpost marked with number `M`.

then it will perform exactly one of the following actions:

1. Mark the current post with a new number, change state and move. To do this `<action>` must be formatted as `"<D> <NS> <NM>"`, where `D` is the direction to move (use 'W' for west and 'E' for east), `NS` is the robot's new state and `NM` is the new mark for the current lightpost.
2. Release the cake at the current position and self-destruct. To do this `<action>` must be formatted as `"R"`.

If you output two or more statements with the same values of `S` and `M`, the robot will misbehave and destroy the cake.

If at any time the robot is in a state X at a lamppost marked with Y such that there is no statement with `S=X` and `M=Y`, then the robot will get confused and eat the cake.

All states and marks must be integers with absolute value no greater than one million (106). Assume that initially the robot is in state zero and all lampposts are marked with zero.

Given N, write a program so the robot releases the cake in the appropriate place. Your program must use at most 30 statements, and it must terminate within X steps.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing an integer N, which indicates the lamppost where the robot must release the cake.

### Output

For each test case, first output "Case #x: y", where x is the number of the test case (starting with 1) and y is the number of statements you will use. Next output y lines, each of which represents a statement for the robot in the format described previously.

WARNING: Judge's response might take up to 5 seconds longer than usual to appear, because your output is run as part of the validation.

### Limits

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

#### Small dataset (Test set 1 - Visible)

0 ≤ N ≤ 500.
X = 250,000 (2.5 × 105).
Time limit: 30 seconds.

#### Large dataset (Test set 2 - Hidden)

0 ≤ N ≤ 5000.
X = 150,000 (1.5 × 105)
Time limit: 60 seconds.

### Sample

 Input Output ``` 3 0 4 0 ``` ``` Case #1: 1 0 0 -> R Case #2: 5 0 0 -> E 1 1 1 0 -> E 2 1 2 0 -> E 3 1 3 0 -> E -1 1 -1 0 -> R Case #3: 3 0 0 -> E 1 1 0 1 -> R 1 0 -> W 0 1 ```
In the first case, the robot is initially in state zero, and there is a zero on the lamppost. So it executes its only statement, which is to release the cake.

In the second case, the robot has five states: 0, 1, 2, 3, and -1. The robot performs the following actions:

• Mark the current lamppost with a 1, move east, and go to state 1.
• Mark the current lamppost with a 1, move east, and go to state 2.
• Mark the current lamppost with a 1, move east, and go to state 3.
• Mark the current lamppost with a 1, move east, and go to state -1.
• Release the cake.

In the third case, the robot has two states, and performs the following actions:

• Mark the current lamppost with a 1, move east, and go to state 1.
• Mark the current lamppost with a 1, move west, and go to state 0.
• Release the cake.
Note that the robot takes different actions at the two times it is in state 0, because it sees a different mark each time.

## D. Ace in the Hole

### Problem

Amy has a deck of N cards with values 1 through N. She arranges the deck so that the values of the cards have no decreasing subsequence of length 3. For example, 1, 5, 4, 6, 3, 2 would be an illegal ordering because 5, 3, 2 is decreasing.

Amy now gives the deck of cards to Ben. Ben knows that the deck has no decreasing subsequence of length 3, but he does not know the exact ordering. He wants to find the card with value 1. He does this by choosing an arbitrary card, picking it up to observe its value, and then repeating until he has found the card with value 1. At each step, Ben chooses a card that will minimize the worst-case number of cards he has to examine.

Ben later tells you that he got unlucky and had to examine all N cards before finding the card with value 1. Given the order in which he examined the cards of the deck, what value did each card have? If there are multiple possibilities, choose the lexicographically greatest one.

A deck `A` is lexicographically greater than a deck `B` if and only if, at the first index at which they differ, the card in `A` has a value greater than the value of the card in `B`.

Example: N = 3, and Ben tried the cards in order 2, 1, 3 (the indices are 1-based). The values of the cards must have been: 2, 3, 1.

Explanation: If card #2 had value 1, then Ben would have stopped immediately. If card #2 had value 2, then Ben would have known the first card must have been the 1, because the ordering (3, 2, 1) is a decreasing subsequence of length 3, and thus could not have been the ordering. In either case, Ben would not have needed 3 guesses. Therefore, we can deduce card #2 have had value 3. Similarly, card #1 could not have had value 1, or Ben could have stopped early. Therefore, the card values must have been 2, 3, 1.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing one integer N, the number of cards in the deck. The next line will contain N integers separated by single spaces, describing the order in which Ben examined the deck: the first integer denotes the 1-based position of the first card he examined, the second integer denotes the 1-based position of the second card he examined, and so on.

### Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the sequence of cards' values, separated by spaces.

### Limits

1 ≤ T ≤ 100
For the provided sequence of guesses, there will be at least one deck that meets all the constraints of the problem, including the constraint that Ben's strategy required him to look at N cards.
Memory limit: 1GB.

#### Small dataset (Test set 1 - Visible)

1 ≤ N ≤ 8
Time limit: 30 seconds.

#### Large dataset (Test set 2 - Hidden)

1 ≤ N ≤ 300
Time limit: 60 seconds.

### Sample

Sample Input
```3
3
2 1 3
1
1
3
3 2 1
```
Sample Output
```Case #1: 2 3 1
Case #2: 1
Case #3: 1 3 2
```

## E. Google Royale

### Problem

While visiting the planet Theta VIII, your team of space explorers is forced to participate in the plot of a badly-written book, which takes place in a hotel/casino called the Google Royale. In order to escape the Royale, you will have to make enough money from gambling that you can buy the hotel for V dollars and leave.

You start with A dollars, and you will participate in betting rounds until one of two conditions is met. If you finish any betting round with ≤ 0 dollars, you will lose; if you finish a betting round with ≥ V dollars, you will buy the hotel and leave. Otherwise you'll keep starting new betting rounds.

Each betting round consists of one or more coin flips. If you have X dollars at the start of the round, you can choose any integer `B` between 1 and `min(X, M)` to bet on the first coin flip.

With probability 50%, you win the coin flip, and the Royale immediately pays you `B` dollars. You now have `X + B` dollars, and the betting round ends.

With probability 50%, you lose the coin flip and owe the Royale `B` dollars. You can now pay the `B` dollars you owe and end the round. Or if `2B ≤ M`, you can instead delay the payment and do a second coin flip with twice the bet: `2B` dollars. If you lose again, then you owe the Royale `B+2B=3B` dollars. You can continue doubling your bet in this way to `4B`, `8B`, etc., until either you win a coin flip, you choose to stop, or your next bet would exceed M. You can even continue if the total of all your bets in the current betting round exceeds `X`.

Once the round is over, you must pay the Royale for each coin flip you lost, and if you won a coin flip, the Royale pays you for that. For example, if you start with a bet of 1 dollars, lose three coin flips, and then win one, you would gain \$8 - \$4 - \$2 - \$1 = \$1. If you lose three coin flips and then stopped, you would lose \$4 + \$2 + \$1 = \$7. If you are left with \$0 or less after paying, then you are broke, and you have just lost the game.

Luckily you have brought an android with you, and he is able to compute the probability that you will win if you follow an optimal strategy. What is that probability, and what is the largest possible first bet you could make to have that probability? Remember that you are not allowed to bet more than M!

### Example

Suppose that you decide to use the following (sub-optimal) strategy. You have `A`=5 dollars; `M=20` and `V=40`. The following sequence of events is possible:

• Round 1: You can start by betting 1, 2, 3, 4 or 5 dollars. You decide to begin a betting round by betting 2 dollars.
• Step 1 (B=\$2): You win the first coin flip. You gain 2 dollars, and the betting round ends. Now you have 7 dollars.
• Round 2: You begin a betting round by betting 5 dollars.
• Step 1 (B=\$5): You lose the first coin flip. Now you owe the Royale 5 dollars. Since `5*2 ≤ 20`, you may do another coin flip with a bet of `5*2=10` dollars. You choose not to. You lose 5 dollars, and the betting round ends. Now you have 2 dollars.
• Round 3: You begin a betting round by betting 2 dollars.
• Step 1 (B=\$2): You lose. Now you owe the Royale 2 dollars. You choose to flip another coin with a bet of 4 dollars.
• Step 2 (B=\$4): You lose. Now you owe the Royale a total of 6 dollars. That's more than you have, which is okay. You choose to flip another coin with a bet of 8 dollars.
• Step 3 (B=\$8): You win. You gain 8 dollars, pay the 2+4=6 dollars you owe, and the betting round ends. Now you have 4 dollars.
• Round 4: You begin a betting round by betting 2 dollars.
• Step 1 (B=\$2): You lose. Now you owe the Royale 2 dollars. You choose to flip another coin with a bet of 4 dollars.
• Step 2 (B=\$4): You lose. Now you owe the Royale a total of 6 dollars. You choose to flip another coin with a bet of 8 dollars.
• Step 3 (B=\$8): You lose. Now you owe the Royale a total of 14 dollars. You choose to flip another coin with a bet of 16 dollars.
• Step 4 (B=\$16): You lose. Now you owe the Royale a total of 30 dollars. Since `2*16>M`, you cannot flip another coin and you must pay what you owe. Now you have -26 dollars; you have lost.

### Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers separated by single spaces: A, M and V, in that order.

### Output

For each test case, output one line containing "Case #x: y z", where x is the case number (starting from 1); y is the probability of winning if you follow an optimal strategy; and z is the maximum first bet you can make without reducing your probability of winning. y must be correct to within an absolute or relative error of 10-6.

### Limits

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

#### Small dataset (Test set 1 - Visible)

1 ≤ M ≤ 20.
1 ≤ A < V ≤ 20.
Time limit: 30 seconds.

#### Large dataset (Test set 2 - Hidden)

1 ≤ M ≤ 1016.
1 ≤ A < V ≤ 1016.
Time limit: 60 seconds.

### Sample

Sample Input
```4
1 1 3
3 6 12
4 20 15
13 6 20
```
Sample Output
```Case #1: 0.333333333 1
Case #2: 0.500000000 3
Case #3: 0.755555555 3
Case #4: 0.730769231 6
```

## Analysis — A. Runs

On a contest made up of unconventional problems, this one stands out as being a little more "normal" than the rest. That doesn't make it easy though! The main techniques here are good old-fashioned dynamic programming and counting, but you need to be very good at them to stand a chance.

The most important observation is that you cannot afford to build strings from left to right. With 450,000 characters, there is just far too much state to keep track of. The correct approach turns out to be placing all of one character type, then all of the next, and so on. Towards that end, let's define Nc to be the number of characters of type c, and define Xc,r to be the number of ways of arranging all characters of type 1, 2, ..., c so that there are exactly r runs. We will compute the X values iteratively using dynamic programming.

Consider a string S using only the first c - 1 character types, and having r0 runs. Note that S has exactly M = N1 + N2 + ... + Nc-1 characters altogether. Additionally, it has a few different types of "character boundaries":

• There is the boundary before the first character and the boundary after the last character. If we add a run of type-c characters in either one of these locations, the total number of runs will increase by 1.
• There are r0 - 1 boundaries between distinct characters. If we add a run of type-c characters in any one of these locations, the total number of runs will increase by 1.
• There are M - r0 boundaries between identical characters. If we add a run of type-c characters in any one of these locations, the total number of runs will increase by 2.
So let's suppose we add x runs of type-c characters in any one of the r0 + 1 boundaries from the first two groups, and we add y runs of type-c characters in any of the M - r0 boundaries from the the third group. There are exactly (r0 + 1 choose x) * (M - r0 choose y) ways of choosing these locations, and we will end up with r0 + x + 2y runs this way. Finally, we need to divide up the Nc characters of type c into these x + y runs. This can be done in exactly (Nc - 1 choose x + y - 1) ways. To see why, imagine placing all the runs together. Then we need to choose x + y - 1 run boundaries from Nc - 1 possible locations. See here for more information.

Therefore, the number of ways of adding all Nc type-c characters to S so as to get a string with exactly r runs can be calculated as follows:

• Loop over all non-negative integers x, y such that r0 + x + 2y = r.
• Add (r0 + 1 choose x) * (M - r0 choose y) * (Nc - 1 choose x + y - 1) to a running total.
• After looping over all x, y, this running total will contain the answer we want.
Note that the answer here depends only on r0. Therefore, the total contribution from all strings with r0 runs is exactly Xc-1,r0 times this quantity. Iterating over all r0 gives us the recurrence we need for X!

This method is actually quite fast. We can use O(450,000 * 100) time to pre-compute all the choose values. Everything else runs in O(26 * 1003) time.

By the way, you probably need to calculate the choose values iteratively rather than recursively. 450,000 recursive calls will cause most programs to run out of stack space and crash! Here is a pseudo-code with a sample implementation (modulo operations removed for clarity):

```def CountTransitions(M, Nc, r0, r):
# Special case: If adding the first batch of characters the
# only possible result is to have one run, and there is only
# one way to achieve that.
if r0 == 0:
return r == 1 ? 1 : 0
result = 0
dr = r - r0
for (y = 0; r0 + 2 * y <= r; ++y):
x = r - (r0 + 2 * y)
nways_select_x = Choose(r0 + 1, x)
nways_select_y = Choose(M - r0, y)
nways_split = Choose(Nc - 1, x + y - 1)
result += nways_select_x * nways_select_y * nways_split
return result

def Solve(freq, runs_goal):
runs_count = [0 for i in range(0, runs_goal + 1)]
runs_count[0] = 1
M = 0
for i, Nc in enumerate(freq):
if Nc > 0:
old_runs_count = list(runs_count)
runs_count = [0 for i in range(0, runs_goal + 1)]
for (r0 = 0; r0 <= runs_goal; ++r0):
for (int r = r0 + 1; r <= runs_goal; ++r):
nways = CountTransitions(M, Nc, r0, r)
runs_count[r] += nways * old_runs_count[r0]
M += Nc
return runs_count[runs_goal]
```
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Analysis — B. Rains Over Atlantis

One obvious solution (which works for small input) is to simulate. The trouble starts when the heights are large, and M is small. Thus, we need to be able to do multiple steps at once.

Begin by noting that, given the current map of heights, we can determine the water levels (i.e., what areas are submerged and what areas are not) using a single run of Dijkstra's shortest path algorithm, in RC log(RC) time.

We will have a single step procedure. What it does is:

1. Calculate water levels for all fields.
2. For each field find out if it is submerged; if not, find the lowest water level in the adjacent fields.
3. Create a new map in which all the heights are lessened by the appropriate erosion, and increase the day counter by one.

This is one step of the simulation, which is also needed for the naive solution.

We will also have a multistep procedure, which tries to perform multiple single steps at once, as long as all of the following are true:

• all non-submerged fields erode at maximum speed,
• the water levels of all submerged fields decrease at the same speed, and
• no submerged field becomes un-submerged during these steps.

The multistep procedure will work as follows:

1. Calculate the water levels for all fields.
2. For each field find out whether it is submerged. If not, find out how much it will erode. If this is not M, break the multistep. Note that we can choose to erode fields to below sea level for simplicity without changing the result.
3. If all fields erode at speed M, then the water levels of all "lakes" also decrease at this speed. Note that each lake has at least one field on the border which is not submerged, but determines the water level of the lake, and this level will decrease by M. Thus, we can continue repeating steps until some field that was submerged surfaces.
4. Thus, we find the submerged field with the smallest amount of water on top, and batch the appropriate number of steps together.
5. If there are no submerged fields, then we increment the day counter by ceil(maxheight / M) and finish the algorithm.

Note that in each multistep one field that was submerged becomes uncovered, and it's easy to see that a field that is not submerged will never become submerged in the future - thus there are at most RC multisteps in the algorithm (actually, fewer because the fields on the edge of the board are never submerged).

Now we want to know how many steps are possible before we can perform a multistep. Define an auxilliary graph that has a node for each un-submerged field. For each lake we join all the fields in this lake to an arbitrary field on the boundary of the lake which defines the water level for the lake (the outlet of the lake). We define natural edges in the graph -- two nodes have an edge if any of the two fields merged into the two nodes were adjacent. For each nodes we can define its "parent" to be one of the nodes with the lowest level adjacent to it. Thus, we have a tree, rooted in the external sea. We define any path going upward in the tree to be "fixed" if all of the edges along the path have a height difference of at least M.

We can now prove that each day either

• a submerged becomes uncovered (thus decreasing the number of multisteps available), or
• the number of vertices that have fixed paths to the root increases, or
• all vertices lie on fixed paths.

If all vertices lie on fixed paths, then we can perform a multistep. As there can be at most RC increases before all vertices are on fixed paths, this means we get at most RC steps and at most one multistep before some field is uncovered, meaning at most (RC)2 steps and RC multisteps in total, giving a running time of (RC)3 log(RC). The constants are very small here, so this will easily run in time.

Now consider any fixed path. We assume the node distribution remains the same (i.e. the lakes remain lakes, and nothing gets uncovered). First notice that it remains a fixed path after one day - all of the fields on the path decrease by the same amount, so the differences remain the same. Now take any vertex that is not on a fixed path, but its parent is. Note that the sea level is on a fixed path by definition, so if no such vertex exists, it means that all vertices are on a fixed path. Then after one day the height of this vertex decreases to the height of the parent, while the height of the parent decreases by M. So the new difference is M, meaning that the vertex has joined the fixed path. This ends the proof.

Note that the upper bound can actually be (more or less) hit in the following map with M = 2: take a winding path of length that is on the order of RC, that does not touch itself, like so:

X X X X X X X
P P P P P P X
X X X X X P X
X P P P P P X
X P X X X X X
X P P P P P X
X X X X X X X

Where X represent very large values, and P represents the path. Thus, for the foreseeable future, the tree described above is actually the single path marked by Ps.

Now take the following values on the path: A, A-2L-1, A+1, A - 4L - 1, A+1, A - 6L - 1, A+1, A - 8L - 1, etc., where L is the length of the path. It is not difficult to check that "off by one" changes get propagated up the path with speed one, and each change gets to be fully propagated before the next one kicks in (due to the uncovering of another lake).

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

## Analysis — C. Program within a Program

Here at the Google Code Jam, we have always tried to encourage a variety of programming languages. But in this problem, we took things a little further by forcing you to program in the language that started them all -- the abstract Turing Machine! Unfortunately, abstract Turing Machines are pretty unwieldy, and that makes even the simple task here quite difficult.

With so few rules allowed, it is important to take advantage of the numbers you can mark onto the lampposts. The obvious approach is to write down, perhaps in binary, the number of steps you need to make, and then have the robot makes decisions based on that. Unfortunately, there is also a rather tight limit on the number of moves, which means you cannot afford to keep going back to the start to check on your number. You will need to take the data with you as you move.

Here is one effective way of doing this:

• First write down the distance you want to go forward in binary, using the values 1 and 2 to represent the binary digits. This information will now be available on the starting lampposts.
• Now repeat the following:
• Trace through the number from right to left, and subtract 1 as you go.
• If the number was 0, then drop the cake right now.
• Otherwise trace through the number from left to right, copying everything one position to the right.
Once you have the high level algorithm, each piece is relatively straightforward to implement. For example, subtracting 1 comes down to formalizing the subtraction algorithm you learned in grade school:
• Start in state 1, which we'll you use to mean you have not yet done the subtraction. If the last digit is 1, you can replace it with 0 and the subtraction is done, so switch to state 2. If the last digit is 0, replace it with 1 but you now need to borrow 1 from the previous digit, so stay in state 1. Either way, move to the previous digit.
• Once you are in state 2, you are just moving left through the number without changing anything.
• If you reach the left end of the number in state 1, then the number must have been 0, so you should drop the cake. Otherwise, you should move onto the copy phase.

And the copy phase is similar but conceptually simpler.

Almost any implementation of this algorithm should be good enough to solve the problem, but there is room for more optimization if you want a challenge! With the 30-rule limit, we were able to bring the number of steps down to about 95,000. Here is the full program to move 5,000 lampposts:

```0 0 -> E 1 1
1 0 -> E 2 3
2 0 -> E 3 1
3 0 -> E 4 3
4 0 -> E 5 2
5 0 -> E 6 3
6 0 -> E 7 1
7 0 -> E 8 3
8 0 -> W 9 3
9 0 -> R
10 0 -> E 11 0
9 1 -> W 9 3
10 1 -> W 10 1
9 2 -> W 10 1
10 2 -> W 10 2
9 3 -> W 10 2
10 3 -> W 10 3
11 1 -> E 12 0
12 0 -> W 9 3
12 1 -> E 12 1
12 2 -> E 13 1
12 3 -> E 14 1
13 0 -> W 10 1
13 1 -> E 12 2
13 2 -> E 13 2
13 3 -> E 14 2
14 0 -> W 10 2
14 1 -> E 12 3
14 2 -> E 13 3
14 3 -> E 14 3
```

Can you do better? We'd love to hear about it if so!

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

## Analysis — D. Ace in the Hole

This is a rather unconventional problem that requires a lot of thought up-front and relatively little implementation.

Let's think about the problem as a competitive game. Ben chooses a card position, and then Amy chooses the value of that card. Amy is not allowed (a) to re-use values, (b) to create a decreasing subsequence of length 3, or (c) to place the 1 before the final turn. Our task it to understand what decisions Amy could have made during the game. We will present the answer first, and then prove it is correct. Define an "adversarial strategy" for Amy as follows:

• At any point, consider the cards that Ben has not yet looked at. Suppose they are in positions p1 < p2 < ... < pm, and have values v1 < v2 < ... < vm.
• If Ben looks at the card in position pk with k < m, then Amy assigns it value vk+1.
• If Ben looks at the card in position pm and either (a) m ≤ 2, or (b) there is a previously revealed card in position less than pm with value between vm-1 and vm, then Amy assigns it value vm. Otherwise, she assigns it value either vm-1 or vm.

We claim that the problem conditions are equivalent to saying that Amy chooses the deck values according to an adversarial strategy. Once that is established, it will be pretty straightforward to find the lexicographically largest solution.

### Adversarial Strategies Cannot Be Exploited

The main technical challenge is to prove that adversarial strategies really do require Ben to look at every card. On a contest of course, you would not need to make this argument quite so rigorously.

Lemma: If the deck values are assigned according to an adversarial strategy, then the deck contains no decreasing subsequence of length 3.

Proof: We follow along as Ben looks at the cards one at a time. At each step, we will say a card is "safe" if Ben has looked at it, and either (a) all cards with a higher position have also been looked at, or (b) all cards with a higher value have also been looked at. Let's suppose the remaining cards are in positions p1 < p2 < ... < pm, and have values v1 < v2 < ... < vm. These are the "unsafe" cards.

We claim the following is true:

• There is no way of assigning values to the remaining cards that will make a decreasing subsequence of length 3 with a safe card.
• If an unsafe card in position pi has been looked at, then it has value vi+1.
We prove this claim by induction on the number of cards that Ben has looked at. Initially, all cards are unsafe and the claim obvious.

Now let's suppose Ben looks at a card C in some position pk.

• Case 1: k < m - 1. Since Ben has not looked at the card in position pm (or else it would be safe), the value of card C will be set according to the first adversarial strategy rule. Specifically, if there are q cards in positions less than pk that have not been looked at, then C will be assigned the (q+1)th smallest unrevealed value. As all safe cards have been revealed, we can restrict our attention to unsafe cards, from which the inductive hypothesis makes it clear that the (q+1)th smallest unrevealed value is vk+1. Since k + 1 < m, the set of safe cards will not change because of this step, and the inductive hypothesis will still be satisfied afterwards.

• Case 2: k = m - 1. By the same reasoning as in Case 1, C will be assigned value vm. However, the set of safe cards will change in this case. Suppose Ben has already looked at the cards in positions pu, pu+1, ..., pm-2, but he has not looked at the card in position pu-1. These cards will all be labeled as safe set because they have high values, while all other cards will remain unsafe. We need to show that they cannot be part of a decreasing subsequence of length 3. By the inductive hypothesis, we can ignore cards that had been previously marked as safe for this purpose. Now, the newly labeled safe cards are arranged in increasing order, there is only one unsafe card positioned after them, and no preceding unsafe card can have higher value, so indeed, they cannot be part of a decreasing subsequence of length 3. Therefore, the inductive hypothesis is once again satisfied.

• Case 3: k = m. Suppose C is assigned value vt. We know Ben has not looked at the card with value vm, or else that card would already be safe. If Ben has also looked at the card with value vm-1, then the adversarial condition forbids C from having value less than vm-1. Otherwise, vm-1 and vm are both still unrevealed, and the adversarial condition demands that C have value vm-1 or vm.
• If t = m-1, then C will be marked as safe but no other cards will. (Ben cannot have looked at the card in position pm-1 because it would have value vm, and would therefore be safe already.) Furthermore, it cannot be part of a length-3 decreasing subsequence because no unsafe card has a larger position and at most one unsafe card can have higher value.
• If t = m, then some additional cards pu, pu+1, ..., pm-2 might also get marked safe. The newly labeled safe cards are arranged in increasing order, there is only one unsafe card positioned after any of them, and no preceding unsafe card can have higher value, so no decreasing subsequence of length 3 can include these cards. Therefore, the inductive hypothesis is once again satisfied.

In any case, the inductive hypothesis holds at each step, and therefore the lemma is proven.

It now follows immediately that Ben requires all N guesses if the cards are assigned according to an adversarial strategy. No matter what cards Ben looks at, Amy can continue her adversarial strategy and avoid revealing either a decreasing subsequence of length 3 or the card with value 1. In particular, Ben can never finish early.

### Non-Adversarial Orders Can Be Exploited

The previous argument is important from a technical perspective, but in practice, you would begin solving this problem from the other side: first showing how Ben can exploit poor strategies. Towards that end, we show that if Amy ever deviates from an adversarial strategy, then Ben can find the 1-card without requiring all N turns.

Let's begin by focusing on the first card Ben looks at.

Observation 1: Suppose Ben looks at card i < N. Then Amy must assign it value i + 1.

Reason: Suppose he sees value j ≠ i + 1. We claim that the value-1 card cannot be in position N. Indeed, if it was in that position, then the condition that the deck has no decreasing subsequence of length 3 implies that (a) all cards with position less than i have value in the range [2, j-1], and (b) all cards with position between i + 1 and N - 1 have value in the range [j+1, N]. If j < i + 1, then there are not enough cards in the range [2, j-1] for this to be possible, and if j > i + 1, then there are not enough cards in the range [j+1, N] to be possible.

Therefore, if Amy assigns this card a value other than i + 1, then Ben need never look at card N. But we know he did indeed have to look at all the cards, so it must be that Amy assigned value i + 1.

Observation 2: Suppose Ben looks at card N. Then Amy must assign it value N - 1 or N.

Reason: Suppose he sees value j < N - 1. If N = 3, then Ben just found the value-1 card, which is an immediate contradiction. Otherwise, N ≥ 4, and we show that Ben can find the 1-value card in less than N - 1 further card checks, which is another contradiction.

Forgetting the information Ben has already obtained, we know the remaining N - 1 card values are placed in the N - 1 preceding positions. By Observation 1, if Ben checks the card in position i, then it must have the (i+1)th smallest value of the remaining cards. (Otherwise, we already know he can find the 1-value card without checking everything.) So if Ben checks the cards in all positions except N - 3 and N - 1, he must see the following values:

2, 3, ..., j-1, j+1, j+2, ..., N-2, ???, N, ???, j.

The two unknown cards have value 1 and N - 1 in some order. However, we know the second-last card cannot have value N - 1, or we would have a decreasing subsequence: N, N - 1, j. Therefore, the 1 must be in that position, and so Ben never needs to check the fourth-last card, and the proof is complete.

There is only one tricky case left. At a given point, let the remaining unrevealed cards be in positions p1 < p2 < ... < pm, and have values v1 < v2 < ... < vm. Suppose that there is a previously revealed card in position less than pm with value between vm-1 and vm. We need to show that if Ben looks at the card in position pm, then Amy must assign it value vm.

Reason: Suppose Amy does not do this. Consider the first time where she does not. Let C be the card in position pm, and let C' be the revealed card that is positioned before C and that has value between vm-1 and vm.

Up until this point, Amy has followed an adversarial strategy, so we can use the inductive statement proven in our first lemma to divide the deck into safe and unsafe cards. We know there is an unrevealed card positioned after C' (namely C) and there is an unrevealed card value that is higher than the value of C' (namely vm), so C' must be an unsafe card.

Let the unsafe cards have positions q1, q2, ..., qr and values w1, w2, ..., wr. Since vm-1 is an unrevealed value, it belongs to an unsafe card and we have vm-1 = wu for some u. Also C' has value wt for some t > u and position pt-1.

Now suppose Amy assigns C a value of vm-1 = wu. Then the card in position qu-1 must be unrevealed, or it would have had the same value. Also, as argued earlier, the card in position qr-1 must be unrevealed or it would have value wr and therefore be safe already. Ben can now exploit Amy's strategy by looking at every card other than qu-1 and qr-1. It is easy to check this will leave only the values 1 and wu+1. But the card in position qr-1 cannot have value wu+1 or we would get a decreasing subsequence: wt, wu+1, wu. Therefore, this card must have value 1, and Ben can avoid checking the card with position qu-1. This proves the final part!

### Finding The Lexicographically Largest Solution

We are now finally ready to discuss the solution. At each step, Amy's strategy is almost completely determined. The only question is whether she should assign vm or vm-1 to the card in position pm when she has the choice. In fact, the two choices lead to identical deck orderings except with vm and vm-1 swapped. In order to make the ordering as large lexicographically as possible, we want vm early on, and so we should always prefer using vm-1.

That's it! We just need to implement the adversarial strategy, always preferring vm-1 over vm. But of course it took a lot of reasoning to get to this stage!

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

## Analysis — E. Google Royale

Google Royale is perhaps the most unapproachable problem we have ever posed for the Google Code Jam. It requires a great deal of understanding before any progress at all can be made on the large input. This is because the interaction between winning probability and starting money is rather complicated, and you cannot possibly afford to do a complete search through all 1016 states. Although the scenario here might seem similar to Millionaire, a previous Code Jam problem, you simply cannot afford the kind of computation that worked there.

First, let's try to understand a betting round. Let the initial bet be y. If you lose k times and then win, your total earnings will be y * 2k-1 - y * 2k-2 - y * 2k-3 - ... - y, which equals y no matter what k is. If you lose, your total earnings will be negative and the exact value will depend on how many times you doubled.

The key to the whole problem is that your expected winnings from a betting round is exactly 0, no matter what your initial bet is and no matter how many times you are willing to double if you keep losing. (Recall that the expected winnings is your "average" winnings -- formally it is defined as sum pi * i, where pi is the probability that you win exactly i dollars.) The expected value is 0 because at each step of each round, you have a 50% chance of winning some money, and a 50% chance of losing the same amount of money. The average winnings is always 0 in each step, and therefore 0 overall.

Now let's think about strategy a little bit. In general, there will be several different strategies that maximize your probability of winning. For now, we will work on identifying only one of them. We will come back to the question of finding the maximum bet later.

Observation 1: If you have x dollars, there is no reason to start a betting round with more than V - x.

Reason: If you bet more than V - x, then winning will always put you over V. If you decrease the bet slightly, then winning is just as good, but losing is no worse. Therefore, you might as well bet less.

From now on, we will always restrict our attention to strategies that follow Observation 1, and therefore, we will never end up with more than V dollars, no matter how lucky or unlucky we are.

Observation 2: Fix a strategy. Let P be the probability of reaching V dollars, and let L be the expected number of dollars you end up with if you lose. Then P = 1 - (V - A) / (A - L). Since V and A are fixed, this means maximizing P is equivalent to minimizing L.

Reason: This follows from the fact that your expected winnings after any number of betting rounds is always equal to 0, or equivalently, your total expected money is always equal to A. Let's see what this tells us at the end of all betting rounds. At that point, you will have won with probability P, in which case your money is exactly V by Observation 1. Or you will have lost with probability 1 - P, in which case your expected money is exactly L. Therefore, we get:
P * V + (1 - P) * L = A
=> P * (V - L) = A - L
=> P = 1 - (V - A) / (A - L).

So now the question reduces to making L as small as possible. Using these ideas, we can make a couple major deductions about the optimal strategy.

Observation 3: If you have x dollars, you might as well do one of two things: (1) bet exactly x and double until you win or until it is no longer possible to double, or (2) bet exactly 1 and do not double even if you lose.

Reason: An optimal strategy will bet some number y and double up to k times. If one of the betting steps results in a win, you will end up with x + y dollars. Otherwise, you will end up with some number x - z dollars. As always, your expected number of dollars is constant, and so is equal to x. We will show how to replace the strategy of betting y and doubling up to k times with a new strategy (possibly requiring multiple betting rounds) that follows the rules we want, and that is at least as effective at reaching x + y dollars.

Case 1: x - z ≥ 0. Instead of betting y, repeatedly bet 1 and do not double. Stop only when your total amount of money increases to x + y or decreases to x - z. Since x - z ≥ 0, it is legal to continue betting until one of these outcomes happens. Like the original strategy, this strategy will result in the same two outcomes (x + y dollars or x - z dollars), and the expected money at the end will still be x for the exact same reason. However, as Observation 2 shows, if two strategies have identical winning and losing outcomes and identical expected values at the end, they have identical probability of getting the better outcome. Therefore, this strategy is identical to the original strategy, and we can just do this instead.

Case 2: x - z < 0. Instead of betting y, repeatedly bet 1 and do not double. Stop only when your total amount of money increases to x + y or decreases to y. If you end up at y, then bet y, and keep doubling until you win or go broke. If you win, go back to the first step and continue betting 1 until you reach x + y or return back down to y. If you end up at y again, bet y, and repeat. Like the original strategy, this will end with you having exactly x + y dollars or with you being broke. However, it is easy to check that L is strictly smaller here than in the original strategy while the expected money at the end, as always, stays equal to x. Therefore Observation 2 guarantees that this new strategy is strictly better than the original strategy.

We have shown that any strategy can switch to betting 1 or x without becoming any worse, and that proves Observation 3.

This is a very powerful observation, but there is still more to understand! With 1016 possible money amounts, we cannot afford to try both strategies in every situation. There is one more idea that drastically cuts down the search space.

Observation 4: For each non-negative integer i, let Mi be the largest integer such that Mi * 2iM. We will call these numbers "inflection points". Then you should never bet all your money unless the amount you have is an inflection point.

Reason: The proof here is very similar to Observation 3. Consider a strategy that bets everything for x satisfying Mi < x < Mi-1. Let y equal x/2, rounded up. Note that 2yx + 1 ≤ Mi-1, so if we bet y, then we can double i times.

The current strategy either gives you 2x dollars or x * (1 - 1 - 2 - ... - 2i-1) = -2x * (2i-1 - 1). However, y / x ≥ 1/2 > (2i-1 - 1) / (2i - 1). Therefore, the losing amount of money for this strategy is more than -2y * (2i - 1).

Now we consider an alternate strategy. Instead of going all in at x, repeatedly bet 1 and do not double. Stop only when your total amount of money increases to 2x or decreases to y. In the latter case, go all in and double up to i times, or until you win. As noted above, your bet will never exceed M, so this is a legal strategy. If you win, start over from the beginning. Like the original strategy, this will either leave you with 2x dollars or broke. However, if you are broke, you end up with y * (1 - 1 - 2 - ... - 2i) = -2y * (2i - 1). As argued above, this losing value is less than it was for the original strategy, and so Observation 2 implies the new strategy has a higher probability of reaching 2x. Therefore, the original strategy could not have been optimal.

When to go All-In: Let's say a dollar amount is an "all-in" point if we should bet everything when we have that amount of money. Observation 4 guarantees that all-in points are a subset of the inflection points, but it is not true that every inflection point is an all-in point.

Consider the inflection points in increasing order. The smallest inflection point will be 1, and certainly that is an all-in point. Let's now consider the second smallest inflection point. Observation 2 says that our goal is to minimize L, so we calculate what we end up with if we go all in from this inflection point and lose. If it is our lowest total yet, we should go all in there. Otherwise, we can do better by betting 1 until we get to the lower inflection point. The same argument applies for the third inflection point, and then the fourth and so on. In this way, we can very quickly calculate an optimal strategy at every dollar amount.

There are two tricky cases to watch out for here:

• By Observation 1, we should only consider inflection points that are at most V / 2.
• It might be that going all-in at a point x is equally effective as betting 1 and waiting until the next all-in point. In this case, we will say x is an "optional all-in point". The other all-in points are called "strict all-in points".

Calculating the Winning Probability: Let Px denote the probability of reaching V if your current amount of money is x. If x is not a strict all-in point, then one optimal strategy is to bet 1 until we reach the strict all-in point directly above x or directly below x, or until we reach V itself. For any x between these all-in points, we have the recurrence: Px = (Px-1 + Px+1)/2, or in other words, Px - Px-1 = Px+1 - Px. This implies Px is linear in this range, and therefore we can calculate Px if we know the value of P at both endpoints.

We can now calculate P by starting from the largest all-in point and working down. For example, suppose the largest all-in point is y and the probability of losing immediately from going all in there is 1 - p. Then Py = p * P2y. Also, by linearity, P2y = Py * (V - 2y) / (V - y) + 1 * y / (V - 2y). We know p, V, and y, so it is easy to calculate Py from here. Once we have Py, we can use the same trick to calculate P for the second-largest all-in point, then for the third-largest all-in point, and so on, until eventually we have calculated all probabilities.

Calculating the Largest Optimal Bet: It remains only to calculate the largest optimal bet. If A is an all-in point, either strict or optional, then certainly we can and should bet A there.

Otherwise, consider a dollar amount x. If x is not a strict all-in point, then we already saw that Px - Px-1 = Px+1 - Px. This means Px is completely linear between strict all-in points, and so we can certainly increase the bet until either winning or losing would take us to a strict all-in point on either side. If x is equal to a strict all-in point however, then 1 is not an optimal bet, and we have Px > (Px-1 + Px+1) / 2, or equivalently, Px - Px-1 > Px+1 - Px. In particular, this means that increasing the bet further would hurt us. Therefore, the largest possible bet is the distance between A and the nearest strict all-in point.

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

## Statistics — A. Runs

### Test set 1: 11 correct solutions (44.0% solve rate)

First
pashka Java, 34:32
g201513 C++, 56:04
mystic Java, 67:44
vepifanov C++, 88:09
Shortest
g201513 C++, 1817 bytes
rng_58 aka rng..58 C++, 1861 bytes
voover C++, 2544 bytes
meret C++, 2574 bytes
pashka Java, 2644 bytes

### Test set 2: 10 correct solutions (40.0% solve rate)

First
pashka Java, 34:32
g201513 C++, 56:04
mystic Java, 67:44
vepifanov C++, 88:09
Shortest
g201513 C++, 1834 bytes
rng_58 aka rng..58 C++, 1861 bytes
voover C++, 2571 bytes
meret C++, 2574 bytes
pashka Java, 2644 bytes

## Statistics — B. Rains Over Atlantis

### Test set 1: 17 correct solutions (68.0% solve rate)

First
vepifanov C++, 29:33
hanshuai C++, 42:00
Palmtenor C++, 53:13
ACRush aka ACRushTC 53:46
pashka Java, 88:13
Shortest
cgy4ever C++, 1819 bytes
Palmtenor C++, 2355 bytes
misof C++, 2472 bytes
ilyakor C++, 2474 bytes
ashmelev C++, 2575 bytes

### Test set 2: 3 correct solutions (12.0% solve rate)

First
misof C++, 156:15
g201513 C++, 158:10
eatmore Java, 160:22
Shortest
g201513 C++, 2947 bytes
eatmore Java, 7266 bytes

## Statistics — C. Program within a Program

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

First
darnley Java, 202:49
Shortest
darnley Java, 5433 bytes

## Statistics — D. Ace in the Hole

### Test set 1: 8 correct solutions (32.0% solve rate)

First
neal_wu 153:25
mystic Java, 167:12
meret C++, 180:15
ir5 C++, 188:04
Shortest
meret C++, 2858 bytes
RAD. C++, 2879 bytes
ir5 C++, 2968 bytes
mystic Java, 4586 bytes
misof C++, 5273 bytes

## Statistics — E. Google Royale

### Test set 1: 20 correct solutions (80.0% solve rate)

First
eatmore Java, 36:22
linguo Python, 54:56
meret C++, 56:19
misof C++, 78:07
ACRush aka ACRushTC 85:59
Shortest
rng_58 aka rng..58 C++, 1547 bytes
Palmtenor C++, 1602 bytes
ir5 C++, 1671 bytes
cgy4ever C++, 1712 bytes
ilyakor C++, 1846 bytes

### Test set 2: 1 correct solutions (4.0% solve rate)

First
rng_58 aka rng..58 C++, 164:15
Shortest
rng_58 aka rng..58 C++, 1547 bytes