CIELBALL - Editorial

anton_lunyov · July 23, 2012, 12:06am

PROBLEM LINK

DIFFICULTY

HARD

PREREQUISITES

Binary search, Dynamic Programming, Breadth-first search

PROBLEM

Tomya and Ciel play a game. There is a box with balls of different colors. There are S_i balls of color i in the box (i = 1, 2, …, N). Tomya has initially M coins. At each move Tomya can bet X coins on some color i if 0 <= X <= L and she has at least X coins before this move. Ciel chooses the ball from the box. If it has color i then Tomya wins B * X coins otherwise she looses her bet. The chosen ball will not return to the box. When the box is empty, the game is over. Tomya’s goal is to have as much coins as she can in the end of game. Ciel can choose any ball from the box and her goal is to minimize the final Tomya’s coins. You need to find the largest number of coins that Tomya can have in the end of the game irregardless of Ciel’s strategy.

QUICK EXPLANATION

The problem can be solved using binary search and dynamic programming. Let Coins(K) is the minimal number of coins Tomya should have initially in order to get at least K coins in the end of the game. The answer is the largest value of K such that Coins(K) <= M. Hence we can apply binary search to find the answer.

Let K be fixed and denote by DP(A₁, A₂, …, A_N) the minimum number of coins Tomya should have at the beginning of the game with S_i = A_i (i=1, 2, …, N) such that she will get at least K coins in the end of the game. Then Coins(K) = DP(S₁, S₂, …, S_N) and initial value of DP is DP(0, …, 0) = K. Clearly we can assume that A₁ >= A₂ >= … >= A_N. Also from greedy reasoning it is clear that Tomya will always bet on the first color and Ciel will always choose the ball of the first or of the second color. Hence DP(A₁, A₂, …, A_N) can be calculated from D1 = DP(A₁ - 1, A₂, …, A_N) and D2 = DP(A₁, A₂ - 1, …, A_N). It can be proved that

**DP(A₁, A₂, ..., A_N) = max{D2, D1 - B * L, ceiling((D1 + B * D2) / (B + 1))},**

where D2 = 0 if the state (A₁, A₂ - 1, …, A_N) does not exist.

It can be proved that the total number of states in such DP is O(N * maxS²), where maxS = max{S₁, …, S_N}.

In order to get AC you also need to build the DP graph before binary search. It can be made using BFS and map. The total complexity of the algorithm is O(CNT * N * log CNT + CNT * log (B * L * maxS)), where CNT = O(N * maxS²).

EXPLANATION

Assume that we are able to answer the following question: what is the minimal number of coins Tomya should have initially in order to get at least K coins in the end of the game. Denote this number as Coins(K). Clearly Coins(K) is non-decreasing function: more coins Tomya wants to get in the end more coins she should have initially. Since initially Tomya has M coins then the answer to the problem will be the largest value of K such that Coins(K) <= M. Since Coins(K) is non-decreasing the problem can be solved using binary search. Assume that for some integers L’ and R’ we know that Coins(L’) <= M < Coins(R’). Then the answer is somewhere between L’ inclusive and R’ not inclusive or shortly in [L’, R’). Consider M’ = floor((L’+R’)/2). If Coins(M’) <= M then the answer will be in [M’, R’) so we can replace L’ by M’ otherwise answer will be in [L’, M’) and we can replace R’ by M’. So at each step we can decrease the length of the segment which contains the answer in two times. Continuing this process we reach in about log₂(R - L) steps the pair (L’; R’) such that Coins(L’) <= M < Coins(R’) and R’ = L’ + 1. Then clearly the answer will be L’.

Now let’s discus how to find initial values of L’ and R’. Clearly we can take L’ = 0 since Coins(0) = 0 <= M. Now let’s find some value of R’. Note that at each move Tomya can bet at most L coins and thus can win at most B * L coins. The total number of moves in the game is exactly S = S₁ + … + S_N. Hence having M coins initially Tomya can have in the end at most M + B * L * S coins. So for R’ = M + B * L * S + 1 we definitely have Coins(R’) > M. As an exercise prove that we can always take L’ = M + B * min(M, L) and R’ = M + B * L * maxS + 1, where maxS = max{S₁, …, S_N}.

Thus the only thing that we should be able to find is Coins(K). This can be made by dynamic programming. Let K be fixed and denote by DP(A₁, A₂, …, A_N) the minimum number of coins Tomya should have at the beginning of the game with S_i = A_i (i=1, 2, …, N) such that she will get at least K coins in the end of the game. Then Coins(K) = DP(S₁, S₂, …, S_N) and initial value of DP is DP(0, …, 0) = K. There are several observations should be made before we can calculate this DP.

Clearly DP(A₁, A₂, …, A_N) is the same for all permutations of sequence (A₁, A₂, …, A_N). Hence we can assume that A₁ >= A₂ >= … >= A_N.
Since Ciel choose the ball by herself there is no sense for Tomya to bet on colors other than the color with largest count of balls (recall that A₁ is now the largest value among all A_i).
If Ciel decides to choose the ball of other color than Tomya’s bet, it is advantageous for Ciel to choose the color with largest count of balls among the remaining colors.

Hence DP(A₁, A₂, …, A_N) can be calculated from DP(A₁ - 1, A₂, …, A_N) and DP(A₁, A₂ - 1, …, A_N) (if A₂ > 0). Usually it is quite clear how to calculate DP from its definition but in this problem it is a separate non-trivial problem.

Consider at first the case when A₂ = 0 and so there are balls of only one color in the box. Then Tomya should bet the maximal possible value and she always wins. Let DP(A₁, 0, …, 0) = D and DP(A₁ - 1, 0, …, 0) = D1. We will prove that

**D = max{0, D1 - B * L, ceiling(D1 / (B + 1))}**,

where ceiling(Y) is the smallest integer not smaller than Y.

Clearly D is the smallest number of coins Tomya should have before the move such that it is possible to bet X coins for some X and have at least D1 coins after the move. X should satisfy the following inequalities 0 <= X <= min{D, L} and D + B * X >= D1 since D + B * X is the number of coins Tomya will have after the winning move. The last inequality is equivalent to (D1 – D) / B <= X. Hence we need to find the smallest value of D such that there exists integer X satisfying inequalities

**max{0, (D1 - D) / B} <= X <= min{D, L}**

Since D and L are integers, existence of such integer X is equivalent to four inequalities:

0 <= D
0 <= L
(D1 – D) / B <= D
(D1 - D) / B <= L

Solving these inequalities on D we get

**D >= max{0, D1 - B * L, D1 / (B + 1)}**.

Hence the minimal value of D is max{0, D1 - B * L, ceiling(D1 / (B + 1))} as was announced before. This gives the formula for calculating of DP(A₁, A₂, …, A_N) in the case when A₂ = 0.

Now consider more complicated case when A₂ > 0. Then Ciel can choose the ball either of the first color in which case Tomya wins or of the second color and Tomya looses her bet. Denote D1 = DP(A₁ - 1, A₂, …, A_N) and D2 = DP(A₁, A₂ - 1, …, A_N). In this case we will prove that

**DP(A₁, A₂, ..., A_N) = max{D2, D1 - B * L, ceiling((D1 + B * D2) / (B + 1))}.**

Clearly DP(A₁, A₂, …, A_N) equals to the smallest value of D such that there exists non-negative integer bet X <= min{D, L} such that if Ciel choose the ball of the first color then Tomya will have at least D1 coins in the end of the move and if Ciel chooses the ball of the second color then Tomya will have at least D2 coins in the end of the move. In the first case Tomya will have D + B * X coins since ball has the same color as Tomya’s bet; in the second case she will have D – X coins as she looses her bet. So X should satisfy the following two additional inequalities: D + B * X >= D1 and D – X >= D2. Solving these inequalities on X and combining them with initial inequalities 0 <= X <= min{D, L} we get

**max{0, (D1 - D) / B} <= X <= min{D, L, D - D2}**

Since D2 >= 0 and D, L, D2 are integers, existence of such integer X is equivalent to four inequalities:

0 <= D – D2
0 <= L
(D1 - D) / B <= D – D2
(D1 - D) / B <= L

Solving these inequalities on D we get

**D >= max{D2, D1 - B * L, (D1 + B * D2) / (B + 1)}**.

Hence the minimal value of D is max{D2, D1 - B * L, ceiling((D1 + B * D2) / (B + 1))} as was announced before.

Thus we are now able to calculate DP(A₁, A₂, …, A_N) in O(1) time if all previous values of DP are calculated. The most intriguing question now is why the number of states in our DP is relatively small. Since at each state we can decrease only one of the first two components of the vector (A₁, A₂, …, A_N) then it can be proved that the total number of states is at most (maxS + 1) * ((N – 1) * maxS + 2) / 2 = O(N * maxS²). This bound is exact and is achievable for the sequence (maxS, …, maxS). The explanation of this fact is quite cumbersome and is left as an exercise to the reader. Even more tough exercise is to manage an algorithm to find an exact number of states in O(maxS + N) time or even in O(N) time.

Since we need to run DP several times in binary search it is better to build DP graph before actual calculation of separate instances of DP. For this we can use Breadth-first search. To generate all possible states we need queue where states to process will be saved and some associative array that assign consecutive non-negative numbers to states. Many languages have built-in data structures for such array. For example in C++ you can use STL container map. Denote our queue by Q and associate array by ID. To save relations between states we need two-dimensional array next with exactly two columns such that next[K][0] and next[K][1] are ids of two states from which DP of the state with id K will be calculated according to the approach described above. Namely if state with id K is (A₁, A₂, …, A_N) then next[K][0] is the id of the state (A₁ - 1, A₂, …, A_N) and next[K][1] is the id of the state (A₁, A₂ - 1, …, A_N). If one or two of these states are incorrect (has negative values or N = 1) we set corresponding next[K][i] to -1. Note that since we consider only non-decreasing states we need to reorder the states (A₁ - 1, A₂, …, A_N) and (A₁, A₂ - 1, …, A_N) before taking their ids.

The initial state for which each DP should be calculated is V₀ = (S₁, …, S_N). Hence we place this state into Q and assign number 0 to it: ID[V₀] = 0. Now at each step we pop the first element from the queue. Let it be the state V = (A₁, A₂, …, A_N) and it has id K. If A₁ > 0 then consider the state (A₁ - 1, A₂, …, A_N). In order to obtain already sorted state we can find the first value i such that A₁ > A_i and decrease A_i-1 by 1 instead of A₁ (if all elements in the state are equal then simply set i to N + 1). If this state was not in ID then we assign the first unused number to it and push it in back of Q. Otherwise we do nothing with this state but in any case this state has id so we can set next[K][0] to this id. Similarly if N > 1 and A₂ > 0 we consider the state (A₁, A₂ - 1, …, A_N) perform the same operations on it and assign its id to next[K][1]. When Q will be empty we finish this process. Check it out the editorialist solution for short and clear implementation of this step.

Denote by CNT the total number of states obtained by this process. Complexity of this step is O(CNT * N * log CNT) if we use some usual efficient associative array data structure.

Now each DP in binary search can be calculated in O(CNT) time. Strictly speaking we now need to calculate DP[0] having initially DP[ID(0, …,0)] = K by the formulas described above where DP[i] should be calculated from DP[next[i][0]] and DP[next[i][1]]. Setting also DP[-1] to 0 we can merge together both cases described above in one formula:

**DP[i] = max{D2, D1 - B * L, ceiling((D1 + B * D2) / (B + 1))},**

where D1 = DP[next[i][0]] and D2 = DP[next[i][1]].

Thus we get the solution which requires O(CNT * N * log CNT + CNT * log (R’ - L’)) time and O(CNT * N) memory, where CNT = O(N * maxS²) and R’ - L’ = O(B * L * maxS).

Finally note that ceiling(A / B) = floor((A + B - 1) / B) so we don’t need to use real function ceiling and can use integer division instead.

SETTER’S SOLUTION

Can be found here.
Setter used the approach described above having some different implementation details. Namely he used the hash table instead of associative array to build the DP graph. Because of this his solution is asymptotically faster than described approach: the complexity is O(CNT * N + CNT * log(B * L * maxS)). Shortly he assigns some hash value at most 2 * CNT to each state. Ideally each state is saved in the element with index of its hash value in hash table but clearly some states can have identical hash values. Hence the following trick is used for inserting the state: starting from the cell with index of hash value we seek for the next free cell in hash table in circular manner and insert current state in that cell. See details in code.

TESTER’S SOLUTION

It coincides with the setter’s solution.

EDITORIALIST’S SOLUTION

Can be found here.
It is an exact implementation of the described approach.