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

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 **A _{i}**. The maximum amount a person can withdraw at a time is

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

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.

Time limit: 20 seconds.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **N** ≤ 100.

1 ≤ **A _{i}** ≤ 100.

1 ≤

1 ≤ **N** ≤ 10^{5} for at most 10 test cases. For the remaining cases, 1 ≤ **N** ≤ 100

1 ≤ **A _{i}** ≤ 10

1 ≤

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:

- The queue initially looks like [1, 2, 3]. The first person withdraws an amount of 2 in their first attempt and leaves the queue.
- 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.
- 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.
- 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.
- The queue now looks like [3, 2]. The third person withdraws the remaining amount of 1 and leaves the queue.
- The queue now looks like [2]. The second person withdraws the remaining amount of 1 and leaves the queue.
- The queue is now empty.

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:

- 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.
- 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.
- The queue looks like [3, 4, 5, 1, 2]. The third person withdraws an amount of 4 and leaves the queue.
- The queue now looks like [4, 5, 1, 2]. The fourth person withdraws 6 and waits for his next turn.
- The queue looks like [5, 1, 2, 4]. The fifth person withdraws amount of 2 and leaves the queue.
- The queue looks like, [1, 2, 4]. All other people now leave the queue after their second turn one by one.

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?

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

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.

Time limit: 20 seconds.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

All **S _{i}** are distinct.

For any two intervals (

1 ≤ **N** ≤ 100.

1 ≤ **K** ≤ 100.

1 ≤ **S _{i}** <

100 < **N** ≤ 10^{5}, in at most 10 test cases.

1 ≤ **N** ≤ 100, in the remaining test cases.

1 ≤ **K** ≤ 10^{9}.

1 ≤ **S _{i}** <

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.

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
(**R _{A}**,

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.

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**, **R _{A}**,

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.

Time limit: 40 seconds.

Memory limit: 1 GB.

0 ≤ **C** ≤ **S**^{2} - 2.

1 ≤ **R _{A}** ≤

1 ≤

1 ≤

1 ≤

(

1 ≤

1 ≤

(

(

Either

**T** = 48.

**S** = 2.

1 ≤ **T** ≤ 100.

2 ≤ **S** ≤ 6.

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:

- Alma moves to room (2, 2).
- Berthe cannot move.
- Alma moves to room (2, 3).
- Berthe still cannot move.
- 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).

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 **A _{i}** 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.

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 **A _{i}**.

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.

Time limit: 20 seconds.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

1 ≤ **K** ≤ **M**.

1 ≤ **A _{i}**, for all i.

2 ≤ **N** ≤ 6.

2 ≤ **M** ≤ 6.

2 ≤ **N** ≤ 50.

2 ≤ **M** ≤ 50.

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 (**A _{1}** = 1), while the
other group must have two dice (

- 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.

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 (**A _{1}** =

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

Firstly, denote K_{i} as the number of times a person will use the ATM.
Formally, K_{i} = ⌈**A _{i}** /

We can directly simulate the process using a queue.

Assume that i-th person, that wants to withdraw **A _{i}**, is first in the queue.
There are two possibilites:

**A**≤_{i}**X**. In that case, this person withdraws**A**and leaves the queue. We can add i to the answer._{i}**A**>_{i}**X**. In that case, this person withdraws**X**(thus setting**A**to_{i}**A**-_{i}**X**) and goes back to the end of the queue.

Time complexity of this simulation is O(Σ K_{i}).

In the worst case, when **X** = 1, K_{i} = **A _{i}**.
Since

In the second test set, K_{i} can be as big as 10^{9}, 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:

- K
_{i}< K_{j}. Since i-th person will use the ATM fewer times than j-th person, they will leave the queue earlier. - K
_{i}= K_{j}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 K_{i}, 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

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

Consider given time intervals as an array.
We will refer to the start time of i-th interval as **S _{i}** and to the end time of i-th interval as

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 (**S _{1}**) in the sorted array. It is not optimal to deploy the robot before

The following cases are possible for our first robot:

- interval_length
_{1}>**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. - interval_length
_{1}≤**K**: This can be further divided in two cases: - 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.
- 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.

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_length_{i} + **N** log **N**), where **N** is the total number of intervals and interval_length_{i} ≤ 200.

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 **S _{1}**. The number of robots needed for the first inteval can be calculated as ⌈interval_length

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

For subsequent intervals:

- If the interval is already fully covered with the last_harvest_time, no action is needed.
- 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

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

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.

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 **S**^{2}-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(2^{S2}).
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 10^{5}.

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

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

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 **A**_{1}, **A**_{2}, ... **A**_{K}, Pommel can simply reroll until the first **A**_{1} dice land on 1, the next **A**_{2} dice land on 2, and so on, with the last **A**_{K} 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 p_{i} probability that her current dice configuration leads to the i-th element of S, then there is a 1 - Σ p_{i} probability that Pommel will have to re-roll. If we now let e_{i} 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 - Σ p_{i})x + Σ p_{i}e_{i}

x = (1 + Σ p_{i}e_{i}) / (Σ p_{i})

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.

For this test set it's sufficient to look at all dice roll results directly. There are at most Σ_{0≤i≤N} **M**^{i} < 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 2^{M}-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(**M**^{N}×2^{M}×**M**) time which is sufficient.

As an example, consider the test case **N** = 3, **M** = 2, **K** = 2, **A**_{1} = 1, **A**_{2} = 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.

For this test set, the number of possible dice roll outcomes, 50^{50}, 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 (x_{1}, x_{2}, ..., x_{K}) such that the tuple elements are non-decreasing: x_{i} ≤ x_{i+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** × 2^{K}) approach. Consider the expected value equation shown above. First, note that if for some i, e_{i} > 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

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