# Google Kick Start Archive — Round F 2020 problems

## Overview

Thank you for participating in Kick Start 2020 Round F.

Cast

ATM Queue: Written by Vikash Dubey and prepared by Raihat Zaman Neloy.

Metal Harvest: Written by Pablo Heiber and prepared by Raihat Zaman Neloy.

Painters' Duel: Written by Swante Scholz and prepared by Anson Ho.

Yeetzhee: Written by Pablo Heiber and prepared by Jonathan Irvin Gunawan.

Solutions, other problem preparation, reviews and contest monitoring by Andrey Anurin, Anoopam Mishra, Anson Ho, Anushi Maheshwari, Bartosz Kostka, Bohdan Pryshchenko, Cristhian Bonilha, Devanshu Agarwal, Diksha Saxena, Gagan Kumar, Ian Tullis, Jared Gillespie, Jayant Sharma, Jonathan Irvin Gunawan, Kevin Tran, Lalit Kundu, Lizzie Sapiro, Marcin Wawerka, Michał Łowicki, Naranbayar Uuganbayar, Nikhil Hassija, Pablo Heiber, Phil Sun, Raihat Zaman Neloy, Ruoyu Zhang, Sai Surya Upadrasta, Sanyam Garg, Saurabh Joshi, Seunghyun Jo, Sudarsan Srinivasan, Swante Scholz, Swapnil Gupta, Timothy Buzzelli, Vikash Dubey, Vipin Singh, Wajeb Saab, and Yang Xiao.

Analysis authors:

• ATM Queue: Marcin Wawerka
• Metal Harvest: Vipin Singh
• Painters' Duel: Devanshu Agarwal
• Yeetzhee: Phil Sun

## A. ATM Queue

### Problem

There are N people numbered from 1 to N, standing in a queue to withdraw money from an ATM. The queue is formed in ascending order of their number. The person numbered i wants to withdraw amount Ai. The maximum amount a person can withdraw at a time is X. If they need more money than X, they need to go stand at the end of the queue and wait for their turn in line. A person leaves the queue once they have withdrawn the required amount.

You need to find the order in which all the people leave the queue.

### Input

The first line of the input gives the number of test cases T. T test cases follow.

The first line of each test case gives two space separated integers: the number of people standing in the queue, N and the maximum amount X that can be withdrawn in one turn.

The next line contains N space separated integers Ai.

### 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 space separated list of integers that denote the order in which the people leave the queue.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.

1 ≤ N ≤ 100.
1 ≤ Ai ≤ 100.
1 ≤ X ≤ 100.

#### Test Set 2

1 ≤ N ≤ 105 for at most 10 test cases. For the remaining cases, 1 ≤ N ≤ 100
1 ≤ Ai ≤ 109.
1 ≤ X ≤ 109.

### Sample

Sample Input
2
3 3
2 7 4
5 6
9 10 4 7 2
Sample Output
Case #1: 1 3 2
Case #2: 3 5 1 2 4

In Sample Case #1, there are 3 people and the limit to withdraw in one turn is 3. Below is step-by-step description of how the process will look like:

1. The queue initially looks like [1, 2, 3]. The first person withdraws an amount of 2 in their first attempt and leaves the queue.
2. The queue now looks like [2, 3]. The second person wants to withdraw an amount of 7, but they can withdraw only 3 in their first turn. Since they still need to withdraw an amount of 4, they have to rejoin the queue at the end of the line.
3. The queue now looks like [3, 2]. The third person needs to withdraw an amount of 4 but they can only withdraw 3 in their first turn so, they rejoin the queue at the end of the line to withdraw amount of 1 later.
4. The queue now looks like [2, 3]. The second person still needs to withdraw an amount of 4. They withdraw an amount of 3 in their second turn and waits for their next turn to arrive to withdraw the remaining amount of 1.
5. The queue now looks like [3, 2]. The third person withdraws the remaining amount of 1 and leaves the queue.
6. The queue now looks like [2]. The second person withdraws the remaining amount of 1 and leaves the queue.
7. The queue is now empty.
The order in which people leave the queue is [1, 3, 2].

In Sample Case #2, there are 5 people and the limit to withdraw in one turn is 6. Below is step-by-step description of how the process will look like:

1. The queue initially looks like [1, 2, 3, 4, 5]. The first person withdraws an amount of 6, and joins at the end again to withdraw the remaining amount of 3 later.
2. The queue looks like [2, 3, 4, 5, 1]. The second person similarly withdraws an amount of 6 and waits for his next turn to withdraw an amount of 4.
3. The queue looks like [3, 4, 5, 1, 2]. The third person withdraws an amount of 4 and leaves the queue.
4. The queue now looks like [4, 5, 1, 2]. The fourth person withdraws 6 and waits for his next turn.
5. The queue looks like [5, 1, 2, 4]. The fifth person withdraws amount of 2 and leaves the queue.
6. The queue looks like, [1, 2, 4]. All other people now leave the queue after their second turn one by one.
The order in which people leave the queue is [3, 5, 1, 2, 4].

## B. Metal Harvest

### Problem

You are in charge of deploying robots to harvest Kickium from a nearby asteroid. Robots are not designed to work as a team, so only one robot can harvest at any point of time. A single robot can be deployed for up to K units of time in a row before it returns for calibration, regardless of how much time it spends on harvesting during that period. Harvesting can only be done during specific time intervals. These time intervals do not overlap. Given K and the time intervals in which harvesting is allowed, what is the minimum number of robot deployments required to harvest at all possible times?

### Input

The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case gives two space separated integers N and K: the number of time intervals in which harvesting is allowed, and the maximum duration a robot can be deployed for before returning for calibration.

The next N lines contain a pair of space separated integers Si and Ei: the start time and the end time of the i-th interval respectively. Please note that intervals don't include the time unit starting at the moment Ei, so for example an interval with (Si = 2; Ei = 5) has duration of 3 time units.

### 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 number of times robot deployment is needed so that for each interval there is one robot harvesting at that time.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
All Si are distinct.
For any two intervals (Si,Ei) and (Sj,Ej) with Si < Sj, Ei < Sj.

#### Test Set 1

1 ≤ N ≤ 100.
1 ≤ K ≤ 100.
1 ≤ Si < Ei ≤ 200.

#### Test Set 2

100 < N ≤ 105, in at most 10 test cases.
1 ≤ N ≤ 100, in the remaining test cases.
1 ≤ K ≤ 109.
1 ≤ Si < Ei ≤ 109.

### Sample

Sample Input
2
3 5
1 5
10 11
8 9
3 2
1 2
3 5
13 14
Sample Output
Case #1: 2
Case #2: 3

In Sample Case #1, we deploy the robot at time instant 1 and it becomes available for the interval [1, 6]. However, it harvests only for the time range [1, 5]. After that we deploy the robot at 6 and it becomes available for the time interval [6, 11]. This deployment covers both the remaining intervals [8, 9] and [10, 11]. There are multiple optimal strategies here. For example, we can deploy the second robot at 7. It would then cover the range [7, 12], thus harvesting for the intervals [8, 9] and [10, 11].

In Sample Case #2, we deploy the robot at time instant 1, and it becomes available for [1, 3], but harvests for [1, 2] as [2, 3] is not part of any interval. After that we deploy the robot at 3 for the time range [3, 5] in which the robot harvests for the interval [3, 5]. The third deployment is done at time instant 13 making the robot available for time range [13, 15]. However, it harvests only for the interval [13, 14]. Thus three deployments are needed to cover all the intervals.

## C. Painters' Duel

### Problem

A new art museum is about to open! It is a single-story building in the shape of a large equilateral triangle. That triangle is made up of many smaller identical equilateral-triangle-shaped rooms, and the side length of the museum is S times the side length of any one of the rooms. Each room has doors connecting it to all other rooms with which it shares a side (not just a vertex).

Each room is identified by two numbers: the row of the building it is in (counting from top to bottom, starting from 1), followed by its position within that row (counting from left to right, starting from 1). Here is an example of how the rooms are connected and labeled when S = 3:

Alma and Berthe are artists who are painting the rooms of the museum. Alma starts in the room (RA, PA), and Berthe starts in a different room (RB, PB). Each of them has already painted their starting room. C of the other rooms of the museum are under construction, and neither Alma nor Berthe is allowed to enter these rooms or paint them.

Alma and Berthe are having a friendly competition and playing a turn-based game, with Alma starting first. On a painter's turn, if their current room is adjacent to at least one unpainted room that is not under construction, the painter must choose one of those rooms, move to it, and paint it. Otherwise, the painter cannot move and does nothing on their turn. Once both painters are unable to move, the game is over. The score of the game is the number of rooms painted by Alma minus the number of rooms painted by Berthe.

Both painters make optimal decisions, with Alma trying to maximize the score and Berthe trying to minimize the score. Given this, determine the best score Alma can guarantee for the game, regardless of what Berthe does.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing six integers S, RA, PA, RB, PB, and C. Respectively, these are the side length of the museum (as a multiple of the side length of a room), the row and position of Alma's starting room, the row and position of Berthe's starting room, and the number of rooms that are under construction. Then, there are C more lines. The i-th of these lines (counting starting from 1) contains two integers Ri and Pi, representing the row and position of the i-th room that is under construction.

### 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 best score that Alma can guarantee for the game, as described above.

### Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
0 ≤ CS2 - 2.
1 ≤ RAS.
1 ≤ PA ≤ 2 × RA - 1.
1 ≤ RBS.
1 ≤ PB ≤ 2 × RB - 1.
(RA, PA) ≠ (RB, PB).
1 ≤ RiS, for all i.
1 ≤ Pi ≤ 2 × Ri - 1, for all i.
(Ri, Pi) ≠ (RA, PA), for all i.
(Ri, Pi) ≠ (RB, PB), for all i.
Either Ri < Ri+1, or Ri = Ri+1 and Pi < Pi+1, for all i < C.

T = 48.
S = 2.

1 ≤ T ≤ 100.
2 ≤ S ≤ 6.

### Sample

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

In Sample Case #1, the turns must proceed as follows:

1. Alma moves to room (2, 2).
2. Berthe cannot move.
3. Alma moves to room (2, 3).
4. Berthe still cannot move.
5. Alma cannot move. Since neither painter can move, the game is now over.

Alma has painted 3 rooms and Berthe has painted 1 room, so the score is 3 - 1 = 2.

In Sample Case #2, neither painter can move. They only paint their starting rooms.

The following additional cases could not appear in Test Set 1, but could appear in Test Set 2.

2
3 3 4 2 1 2
2 3
3 1
3 3 2 2 3 2
2 1
3 1

The correct output for these two cases would be:

Case #1: 0
Case #2: -1

In Case #1, Alma can move to (3, 5) or (3, 3). She cannot move to (2, 3), which is under construction.

• If she moves to (3, 5), she will have no more moves and Berthe will go on to paint two more rooms. Score: 2 - 3 = -1.
• If Alma moves to (3, 3), then Berthe can do one of the following:
• Move to (3, 2), leaving neither painter with any future moves. Score: 2 - 2 = 0.
• Move to (2, 2). Then the rest of the game must play out as follows: Alma moves to (3, 2), Berthe moves to (1, 1). Score: 3 - 3 = 0.

So Alma knows that moving to (3, 3) guarantees a score of 0 no matter what Berthe does, which is better than the score of -1 that she would get by moving to (3, 5). Therefore, Alma moves to (3, 3). Notice that:

• We do not know exactly how the rest of this game will play out, but we do know the best score that Alma can guarantee.
• It is possible that one or more rooms that are not under construction do not get painted.

In Case #2, Alma must move to (3, 3), and then it is better for Berthe to move to (3, 4) than to (2, 2).

## D. Yeetzhee

### Problem

Pommel is very bored at home so she has invented a new game involving N dice. Each die has the numbers from 1 to M written on it. Whenever she throws a die, it has an equal probability of landing on each of the M possible values.

Pommel places all the dice in a row. She goes through the dice one at a time from left to right. For each die she rolls, Pommel can either keep the value she rolled and move on to the next die or she can re-roll the die. Pommel can re-roll a die as much as she wants before moving on to the next die.

Once Pommel has gone through all the dice, the game is finished. To determine if she has won, she puts the dice into groups. All dice with the same value are put into the same group. So if she finishes the game with x distinct values, then there will be x groups. These groups of dice are then sorted by number of dice in non-decreasing order.

For example:

• If the final dice results are [2, 2, 3, 2, 2, 3], the dice would be put into two groups and ordered as follows: [3, 3] and [2, 2, 2, 2].
• If the final dice results are [1, 6, 7, 7], the dice would be put into three groups and ordered as follows: [6], [1], and [7, 7] (or equivalently, [1], [6] and [7, 7]).

Pommel wins if she finishes the game with exactly K groups, and the i-th group contains exactly Ai dice, for all i.

What is the expected value of the total number of dice rolls it will take Pommel to win the game, assuming she plays optimally to minimize this expected value?

It is guaranteed that for any valid input, it is possible for Pommel to win the game.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the integers N, M and K. Then, K lines follow describing the groups she must finish with. The i-th line contains Ai.

### 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 expected number of times it will take to roll all the dice for Pommel to win the game.

y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

### Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ KM.
1 ≤ Ai, for all i.
A1 + A2 + ... + AK = N.
AiAi+1, for all i.

2 ≤ N ≤ 6.
2 ≤ M ≤ 6.

2 ≤ N ≤ 50.
2 ≤ M ≤ 50.

### Sample

Sample Input
2
3 6 2
1
2
5 2 1
5
Sample Output
Case #1: 4.7
Case #2: 9.0

In Sample case #1, Pommel has N = 3 dice, each with a number from 1 to M = 6 written on them. To win, she must finish the game with K = 2 groups. One group must have one die (A1 = 1), while the other group must have two dice (A2 = 2). One optimal strategy for Pommel is as follows:

• Pommel throws the first die once.
• Pommel throws the second die once.
• If the first and second dice are the same, Pommel keeps throwing the third die until it ends in a different value from the first two. It takes 1.2 dice rolls on average.
• If the first and second dice are different, Pommel keeps throwing the third die until it matches the first or the second die. It takes 3 dice rolls on average.
This strategy takes Pommel 4.7 (1 + 1 + 1/6 × 1.2 + 5/6 × 3) dice rolls on average.

In Sample case #2, Pommel has N = 5 dice, each with a number from 1 to M = 2 written on them. To win, she must finish the game with K = 1 group, with all N dice in them (A1 = N). For the first die, Pommel rolls it once. Then, for each remaining die she keeps rolling until it has the same value as the first one. It takes 2 dice rolls on average.

This strategy takes Pommel 9 (1 + 2 + 2 + 2 + 2) dice rolls on average.

## Analysis — A. ATM Queue

Firstly, denote Ki as the number of times a person will use the ATM. Formally, Ki = ⌈Ai / X⌉.

### Test Set 1

We can directly simulate the process using a queue.

Assume that i-th person, that wants to withdraw Ai, is first in the queue. There are two possibilites:

• AiX. In that case, this person withdraws Ai and leaves the queue. We can add i to the answer.
• Ai > X. In that case, this person withdraws X (thus setting Ai to Ai - X) and goes back to the end of the queue.

Time complexity of this simulation is O(Σ Ki).

In the worst case, when X = 1, Ki = Ai. Since Ai ≤ 100, the worst time complexity is O(N × 100), which easily fits into the time limit.

### Test Set 2

In the second test set, Ki can be as big as 109, so direct simulation is too slow.

Let's look at two people i and j. When will i-th person leave the queue before j-th person? There are two cases:

• Ki < Kj. Since i-th person will use the ATM fewer times than j-th person, they will leave the queue earlier.
• Ki = Kj and i < j. If they both use the ATM the same amount of times, the person earlier in the queue in the initial configuration will leave first.

This observation is enough to form a full solution. Sort people first in ascending order of Ki, and in case of ties in ascending order of their number. After sorting, this is our answer.

Time complexity of this solution is O(N log N).

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

## Analysis — B. Metal Harvest

Consider given time intervals as an array. We will refer to the start time of i-th interval as Si and to the end time of i-th interval as Ei.

Let us sort the time interval array by start time in ascending order. To start the harvesting, we need to deploy our first robot at the start time of the first interval (S1) in the sorted array. It is not optimal to deploy the robot before S1 because we would be wasting robot hours. Per the problem statement, our first robot can be deployed from S1 to S1 + K before it returns for calibration. Let us define interval length of i-th interval as interval_lengthi = Ei - Si.
The following cases are possible for our first robot:

1. interval_length1 > K : In this case, as soon as our first robot finishes, we need to deploy another robot to cover the remaining part of the interval.
2. interval_length1K : This can be further divided in two cases:
1. Bring the first robot back as soon as the first interval finishes. We cannot re-deploy this robot since a robot can only harvest for consecutive units of time.
2. Allow the first robot to be available until K units of time has elapsed. This is a better strategy since it allows us to utilize the robot for future harvesting.

Based on the above scenarios, the optimal strategy is to deploy a robot at the beginning of the first harvesting interval, for K hours. If after K hours the robot is inside the first or any subsequent harvesting interval, deploy another robot to replace it. Otherwise, deploy another robot as soon as the next harvesting interval begins. Repeat this for every interval and keep count of the number of total deployments.

### Test Set 1

For this test set we can loop over sorted time intervals and then have another inner loop to go over each point in time of such interval.
At the i-th point in time, if there is no robot currently deployed for harvesting, we can deploy a robot and keep it harvesting for K units of time. If a robot is already currently deployed for harvesting then no action is needed. The total number of robots deployed is the required answer.
Since we are sorting the intevals array and then iterating over each point in time inside an interval, the worst case time complexity will be O( Σ1 ≤ i ≤ N interval_lengthi + N log N), where N is the total number of intervals and interval_lengthi ≤ 200.

### Test Set 2

To solve for this test case we need to find a way to count the number of robots needed for an interval without iterating over each point in time.
Let us say we deploy a robot at S1. The number of robots needed for the first inteval can be calculated as ⌈interval_length1 / K ⌉.
Let us define a variable last_harvest_time as the last point in time covered by all deployed robots and initialise it as 0. It is possible that the last robot deployed to cover the first interval will go beyond E1 hence the last_harvest_time after covering the first interval will be, last_harvest_time = max(last_harvest_time , S1) + number of robots needed for the first interval * K.
For subsequent intervals:

1. If the interval is already fully covered with the last_harvest_time, no action is needed.
2. If the interval is not fully covered by the last_harvest_time then follow a similar strategy as first interval to calculate the number of new robots required and again update the last_harvest_time. Also increment the answer by total number of new robots.

Since we are sorting the intervals array and then iterating over all intervals at once, the worst case time complexity will be O(N log N), where N is the total number of intervals.

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

## Analysis — C. Painters' Duel

### Test Set 1

There are only 4 rooms, (1, 1), (2, 1), (2, 2) and (2, 3). Both the players, will try to paint the room (2, 2), painting which would block the other player to paint more rooms.

Thus there are five cases,

• If C = 2, none of the players can move, therefore the answer is 0.
• If any of the players starts on room (2, 2) and C != 2, they will paint two rooms and the other player will paint one room.
• If room (2, 2) is blocked, none of the players can move, therefore the answer is 0.
• If any room other than (2, 2) is blocked, and no player start on (2, 2), then Alma will paint two rooms and Berthe will paint one room.
• If no room is blocked, and no player start on (2, 2), then Alma will paint three rooms and Berthe will paint one room.

### Test Set 2

At any point during the game, few rooms of the museum might be under construction, few might have been painted by Alma, few might have been painted by Berthe and a few might be unpainted.

The rooms which are either under construction, painted by Alma or painted by Berthe are not paintable any further. Lets represent these rooms as blocked rooms, and the remaining rooms as free rooms. Thus, without losing any information we can uniquely represent the state of the museum with the following parameters,

• The free rooms.
• Position of Alma.
• Position of Berthe.
• Whose turn is it?
• Present score of the game

We can represent blocked/free rooms of the museum as a binary string, 0 denoting the blocked rooms, and 1 representing the free rooms.

Lets define a function, CalcScore(), which takes the binary string, position of Alma and Berthe, and whose turn it is as input parameters and returns the optimal score as output, that is, the minimal possible score if it is Berthe's turn and maximum possible score if it is Alma's turn.

CalcScore() recursively calls itself with every reachable state, that is, the player tries to paint all the three neighbouring rooms, thus, recursively call CalcScore() for all the valid states.

Lets denote T(N) as time complexity when N rooms are free. In every nested call of CalcScore(), the number of free rooms decreases by 1, thus the recursion depth of CalcScore() can be at max S2-2. A room has at most three neighboring rooms, but if it is not the starting position at least one of them will already be painted because that's where the player came from. Thus, when a player reaches a room, he has only two neighboring rooms to move to. So, every call to CalcScore() can generate at max 2 recursive calls to CalcScore().

Thus,

• T(N) = 2 × T(N-1)
• T(0) = O(1)

Therefore, the time complexity of the initial configuration is O(2S2). Which although seems to be not good enough for S = 6, but in practice, the solution passes well within the time limits as most of the recursion depth will be way less than the presumed maximum. Depends on the implemetation details, but the number of calls to CalcScore() for the worst case is of the order of 105.

Although not needed for Test Set 2, but, we can use techniques like Memoization and Alpha–Beta pruning to further speed up the solution.

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

## Analysis — D. Yeetzhee

First, note that Pommel can always win the game in a finite number of moves on expectation. To do so for a given input sequence A1, A2, ... AK, Pommel can simply reroll until the first A1 dice land on 1, the next A2 dice land on 2, and so on, with the last AK dice landing on K. Such an outcome satisfies the group arrangement required by the input; furthermore, on each roll, Pommel has a 1/M chance of rolling the needed value for the die she's on. This implies that Pommel is expected to win in N×M turns. Although this may not be optimal, it demonstrates that Pommel always has a winning strategy.

The basic procedure for calculating the expected value is the same for any approach. Suppose Pommel has already rolled and fixed some (potentially zero) dice. Furthermore, suppose she chooses a set S of dice configurations, such that she will not re-roll her current die if her dice configuration, after her current roll, is in S. If there is a pi probability that her current dice configuration leads to the i-th element of S, then there is a 1 - Σ pi probability that Pommel will have to re-roll. If we now let ei equal the expected number of moves to win starting from state i, assuming Pommel plays optimally, we can solve for the expected number of moves to win starting from Pommel's current dice configuration. If we let this quantity be x:

x = 1 + (1 - Σ pi)x + Σ piei

x = (1 + Σ piei) / (Σ pi)

Approaches to the two tests sets differ in how they may enumerate the possible dice configurations and how they find the optimal set S for any given configuration.

### Test set 1

For this test set it's sufficient to look at all dice roll results directly. There are at most Σ0≤i≤N Mi < 60,000 such possibilities. For a given configuration, performing another roll leads to one of M new dice configurations, so for each configuration we can loop through all 2M-1 possible non-empty subsets of configurations that Pommel could choose to not re-roll on (ignoring subsets that contain configurations that make it impossible for Pommel to reach a winning configuration). For each choice of subset, we compute Pommel's expected turns until winning, and we take the subset with the lowest expected value.

We need to iterate over the dice configurations such that when we're computing the minimum expected value for a configuration C, we know the minimum expected values for each configuration that C can lead to. This can be done, for example, with DFS. The expected value from the empty configuration is our answer. This algorithm runs in O(MN×2M×M) time which is sufficient.

As an example, consider the test case N = 3, M = 2, K = 2, A1 = 1, A2 = 2. Let's compute Pommel's expected turns from winning when she's rolled and locked down a 1. There are two possibilities for the dice configuration after her next turn: [1, 1] and [1, 2], each occuring with probability 1/2. As a precondition to computing the expected turns to win from [1], we know that, on expectation, it takes two moves to win from [1, 1] and one move to win from [1, 2]. We now consider the three possibilies for S: {[1, 1]}, {[1, 2]}, and {[1, 1], [1, 2]}.

S = {[1, 1]} leads to the equation x = 1 + (1 - 0.5) x + 0.5 · 2, which results in x = 4.

S = {[1, 2]} leads to the equation x = 1 + (1 - 0.5) x + 0.5 · 1, which results in x = 3.

S = {[1, 1], [1, 2]} leads to the equation x = 1 + (1 - 0.5 - 0.5) x + 0.5 · 1 + 0.5 · 2, which results in x = 2.5. This is the lowest value, so we now know that if Pommel has rolled a single 1, she will win in 2.5 more turns on expectation if she plays optimally.

### Test set 2

For this test set, the number of possible dice roll outcomes, 5050, is far too large to be enumerated in time. We instead focus on the groupings of dice that could possibly lead to the desired configuration. For example, if Pommel rolls [1, 1, 2, 2] or if she rolls [3, 4, 3, 4], either way, she'll have two groups of two dice, which are equivalent for this problem. A dice grouping can be expressed as a K-tuple of integers (x1, x2, ..., xK) such that the tuple elements are non-decreasing: xi ≤ xi+1 for 1 ≤ i < K. The i-th element of the tuple expresses the number of dice in the i-th smallest dice group, which is zero if there are fewer than K non-empty groups in the current dice configuration. For example, if K=3 and the dice results so far are [2, 2, 3, 2, 2, 3], the grouping can be expressed as (0, 2, 4).

We need to count how many possible K-tuples we need to consider to get an estimate of our algorithm's runtime. One simple bound is that we only need to consider a tuple T if the sum of T's elements is at most K. The total number of tuples we need to consider is therefore at most Σ0≤i≤K p(i) where p(i) is the number of K-tuples whose elements are non-decreasing and add to i. p(i) can be calculated with a script, but it is also the i-th partition number. The sum of the first 50 partition numbers is only slightly more than a million, which is very tractable.

A dice roll could lead Pommel from a given configuration to at most K new configurations. We now need a way of computing the optimal subset of new configurations S to not re-roll that is faster than the naive O(K × 2K) approach. Consider the expected value equation shown above. First, note that if for some i, ei > x, removing configuration i from S will decrease the value of x. Similarly, if there is some configuration C with expected value E[C] < x that is not included in S, adding it to S will lower x. This implies that if some configuration C with expected value E[C] is in S, then all states C' with E[C'] < E[C] must also be in S if Pommel is playing optimally. We can therefore sort all configurations reachable from a given configuration so that they're in ascending order of expected turns until winning. It is guaranteed that the optimal S is a prefix of the sorted list, so it can be found by sorting and iterating over the list in O(K log K) time.

Combining our improved optimal-subset routine with our bound for the number of K-tuples (which was in fact quite loose and can be shown to be significantly lower) gives us an algorithm that runs in time for M, N ≤ 50.

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