utils/scrapers/prescraped/codeforces/Editorials/1987D

**Hints**
**Hint 1**
Alice's optimal strategy is simple (and kind of fixed).
**Hint 2**
Alice always eats the least tasty cake that she can eat.
**Hint 3**
Convert the given array to it's count array $$$c_i$$$, for example, the array $$$[1, 5, 1, 2, 1, 5, 1]$$$ becomes $$$[4, 1, 2]$$$.
**Hint 4**
Consider a set of $$$k$$$ indices that Bob will choose to eat ($$$c_{i_1} + ... + c_{i_k}$$$ cakes in total). What are the necessary conditions for him to be able to do that?
**Hint 5**
For a set of $$$k$$$ indices $$$1 \le i_1 \le i_2 \le \ldots \le i_k \le |c|$$$, the condition $$$\sum_{j=1}^{p}{c_{i_j}} \le i_p - p$$$ must hold for all $$$1 \le p \le k$$$.
**Tutorial**
Let's consider Alice's strategy. Notice that if both players play optimally, Alice eating a cake with a tastiness value of $$$t$$$ is equivalent to her eating all remaining cakes with $$$a_i \le t$$$. Since it is better for her to have more cakes to choose from later on, she will choose the minimum possible $$$t$$$ on each turn.
Now let's consider Bob's strategy. Suppose Bob ate at least one cake with a tastiness value of $$$t$$$. Then he has to have eaten all of them, because eating only some of them does not affect Alice's possible moves, resulting in wasted turns (he might be forced to waste moves at the end of the game when there are some leftover cakes).
Let $$$A_1, \ldots, A_m$$$ be the sorted unique values of $$$a_1, \ldots, a_n$$$, and let $$$c_i$$$ be the number of occurrences of $$$A_i$$$ in $$$a$$$. Then the game is reduced to Alice finding the first $$$c_i > 0$$$ and assigning $$$c_i := 0$$$, and Bob choosing any $$$c_i > 0$$$ and decreasing it by $$$1$$$.
Since Bob's optimal strategy is for each $$$c_i$$$ either not to touch it or make $$$c_i = 0$$$, we can model it as him selecting some set of indices $$$1 \le i_1 < \ldots < i_k \le m$$$ and zeroing out $$$c_{i_1}, c_{i_2}, \ldots, c_{i_k}$$$ in this order. To be able to zero out $$$c_{i_p}$$$ ($$$1 \le p \le k$$$), Alice must not have gotten to the value $$$c_{i_p}$$$. In $$$c_{i_1} + \ldots + c_{i_p}$$$ turns, Alice will zero out exactly that many values. Additionally, Bob would have zeroed out $$$p - 1$$$ values before index $$$i_p$$$. So, $$$c_{i_1} + \ldots + c_{i_p} + p - 1$$$ must be less than $$$i_p$$$. Transforming this a bit, we get that the condition $$$\sum_{j=1}^{p}{c_{i_j}} \le i_p - p$$$ must hold for all $$$1 \le p \le k$$$.
Bob's objective to maximize the size of the set of incides $$$1 \le i_1 < \ldots < i_k \le m$$$. Let $$$dp[i][k] =$$$ the minimum possible $$$\sum_{j=1}^{k}{c_{i_j}}$$$ over all valid sets of indices $$$1 \le i_1 < \ldots < i_k \le i$$$. Initialize $$$dp[0][0] = 0$$$, and everything else to $$$+\infty$$$. The main idea is to grow valid sets of indices one index at a time.
We will iterate over all $$$i$$$ from $$$1$$$ to $$$m$$$, and then for each $$$k$$$ from $$$0$$$ to $$$m$$$. The transitions are: 
 $$$dp[i][k] = \min(dp[i][k], d[i - 1][k])$$$, which corresponds to not using the current index in the set. 
 Let $$$s := dp[i - 1][k - 1] + c_i$$$. If $$$s \le i_k - k$$$, update $$$dp[i][k] = \min(dp[i][k], s)$$$, which is equivalent to adding the current index to the set. We only need to check the condition on the last index because it is already satisfied for all the previous indices. 
The answer to the problem is $$$m - y$$$, where $$$y$$$ is the largest value where $$$dp[m][y] \le +\infty$$$.
Complexity: $$$\mathcal{O}(n^2)$$$
Note: it is possible to solve in $$$\mathcal{O}(n \log n)$$$ by making an additional observation.
**Solution**
**Feedback**
Good problem 

    



Average problem 

    



Bad problem