Game Reformulation

Mr. Box doesn’t need to buy boxes until necessary. Therefore, Mr. Box can choose to only buy a box when he receives a ball and there’s no existing box where he can put it.

Let’s call a ball of type \(c\) a ball of color \(c\), and box type \(i\) as box \(i\).

First, let’s consider Mr. Ball’s strategy. Since it’s disadvantageous for Mr. Ball when Mr. Box can use existing boxes, he wants to avoid giving such balls when possible. In other words, calling a box that contains fewer than its capacity of color \(c\) balls a color \(c\) box, if there exists a color \(c\) that doesn’t have a color \(c\) box, Mr. Ball will always choose a ball of color \(c\).

Otherwise, any ball given will allow Mr. Box to earn \(1\) yen without spending money. Mr. Ball wants to escape this situation as quickly as possible, so he chooses color \(c\) of the box with the least remaining capacity and continues giving balls of color \(c\) until that box reaches capacity.

Given that Mr. Ball follows this strategy, from Mr. Box’s perspective, this game can be reformulated as the following game (without Mr. Ball’s participation):

Initially, Mr. Box has an empty list \(L\), and he can repeat the following operations any number of times.

• If the list length is less than \(M\), choose any box \(i\), pay \(P_i-1\) yen, and add \(V_i-1\) to \(L\).
• Otherwise (when list \(L\) has length \(M\)), let \(m\) be the minimum value in the list. Receive \(m\) yen and remove one instance of \(m\) from the list.

\(O(2^N N)\) Solution

Now, assume that a game ends (not necessarily with optimal play), and let’s consider how Mr. Box’s money changed. Let \(i_1,\dots,i_k\) be the boxes Mr. Box bought in this game.

When \(0<k<M\), he only loses money, so it’s better to buy nothing (\(k=0\)). When \(k=0\), the answer is \(0\).

Next, consider when \(k\ge M\). Mr. Box pays \(V_{i_1}+\dots+V_{i_k}-k\) yen. By observing the list operations, we can see that at game end, the remaining elements in the list are the largest \(M-1\) elements among \(V_{i_1}-1,\dots,V_{i_k}-1\). Therefore, the amount Mr. Box receives is the sum of the smallest \(k-(M-1)\) elements among \(V_{i_1}-1,\dots,V_{i_k}-1\). From this, we can find Mr. Box’s optimal strategy by trying all possible box combinations. Time complexity is \(O(2^N N \log N)\). By preprocessing input to sort by \(V_i\), it becomes \(O(2^N N)\).

\(O(N \log N)\) Solution

Assume input is sorted in descending order of \(V_i\). Let \(t\) be the box with the \(M\)-th smallest index among those Mr. Box chooses, and we case on \(t\).

For a fixed \(t\), Mr. Box chooses boxes as follows:

• Choose \(M-1\) boxes \(i\) from boxes \(1,\dots,t-1\)
  • Pay \(P_i-1\) yen for each
• Choose box \(t\)
  • Pay \(P_t-1\) yen
• Choose any number of boxes from \(t,\dots,N\)
  • Gain \(V_i-P_i\) yen for each chosen box \(i\)

Thus, Mr. Box’s optimal strategy in this case is:

• Choose \(M-1\) boxes with smallest \(P_i\) from boxes \(1,\dots,t-1\)
• Choose box \(t\)
• Choose all boxes \(i\) from \(t+1,\dots,N\) where \(V_i-P_i\) is positive

Using a data structure like heap, we can find the sum of the \(M-1\) smallest \(P_i\) from \(1,\dots,t-1\) for all \(t=1\dots,N\) in \(O(N \log N)\). The sum of positive \(V_i-P_i\) from \(t,\dots,N\) for all \(t=1\dots,N\) can be calculated in \(O(N)\) by processing \(t\) in descending order. Therefore, we can solve this problem in \(O(N \log N)\).

Sample Implementation in C++