Strategies

Back to the problem, Alice's strategy is quite simple: she has to eat the least tasty cake she can. That way she has the lowest limit for the least tasty cake she can eat, thus increasing her possibilities.

Bob's strategy is not so simple. In general, he must prevent Alice from eating as many cakes as he can.

Something to notice is that, because Alice can't eat cakes with the same tastiness twice, it could help to make a list of frequency of the tastiness values of the cakes.

.cpp    int t; cin >> t;
    while(t--){
        int n; cin >> n;
 
        map<int, int> m;
        for(int i = 0; i < n; i++){
            int ai;
            cin >> ai;
            m[ai]++;
        }
 
        vi f;
        for(auto [_, cnt]: m){
            f.push_back(cnt);
        }
        int nn = f.size();
    
        // Rest of the code
    }

Wrong answer

Maybe Bob should eat the cakes in order of frequency as he can. With each "move" of Alice, he can eat one cake, i.e.: remove one to the frequency count of any tastiness value. So we can go one by one accumulating how many cakes Alice has eaten $d_a$ and after each, search for a more tasty stack of cakes with a frequency $\leq d_a$ so Bob can eat it and prevent Alice from doing it.

.cpp        // This the "Rest of the code" in the snippet above

        int ans = 0;
        int da = 0;
        for(int a = 0; a < nn; a++){
            if (f[a] > 0){
                da++; ans++;
                for(int b = a + 1; b < nn; b++){
                    if (f[b] == da){
                        f[b] = 0;
                        da = 0;
                        break;
                    }
                }
            }
        }
 
        cout << ans << '\n';

In this approach, Bob goes greedily trying to eat the cakes from least to most frequent. This was my first attempt, and as you can see it led to a Wrong Answer.

Why?

A simple counter-example, let's say we have a frequency array like this: [1, 2, 2, 50, 50, 50, 50, 1, 1]; with this algorithm, Bob would eat the two 1's at the end but Alice would get to eat from each of the 6 first stacks. Bob's strategy should be to eat from the third stack first, that way he prevents Alice from eating from it, and still has time afterward to eat the 1's at the end.

So, should Bob greedily eat the first stack he can? That doesn't work either. Look at the example [1, 2, 2, 2, 1, 1, 2]; in this case, the optimal strategy for Bob is to eat the last 3 stacks, if he eats any other stack before, Alice would get to the 1's.

$O(2^n)$ Too slow

The most naive approach that gets to the true solution would be to check every possible combination of Alice and Bob taking each value, checking if the configuration is achievable. There are $O(n)$ unique values of tastiness¹. If each value can be taken by Alice or Bob it gives $O(2^n)$ possible configurations. Checking all configurations would be impossible.

Let's see some numbers

A modern personal computer's CPU can do around $10^8$ elemental operations² per second. The fastest supercomputer in 2023 had a speed of around 1 billion gigaFLOPS³; around $10^{18}$ elemental operations per second. There are around $10^{80}$ atoms in the universe⁴.

So, we have to check up to $2^{5000} \simeq 10^{1505}$ possible configurations. If we had a supercomputer on each of the atoms of the universe and used them exclusively for our problem (also assuming each check is an elemental operation, which is not true), we would take $10^{1505} / (10^{80} 10^{18}) = 10^{1407}$ seconds or $\sim 3 \cdot 10^{1398}$ years.

In the context of competitive programming, the online judges run the submissions in (simulated) hardware with about the same computing power as a personal computer. So, for the problem in question, the solution should have a time complexity less or in the same order of $O(n^2)$.

$O(n^3)$ Almost fast enough

In my experience, these sorts of problems in which one could take something or not are usually solvable using Dynamic Programming, a technique in which one re-uses the optimal solution to smaller problems to solve the bigger ones.

The process of solving a problem using dynamic programming involves identifying the overlapping sub-problems whose optimal solutions can be used for the bigger problem, then defining the state variables of the subproblem and the recurrence relation to build the solution from the subproblems.

I found it difficult to get to it because of the checks we needed to perform to be sure that Bob could eat some cakes but in Figure 1 you can see the first checks of the idea.

To check if Bob can eat a stack of cakes or not, we need to know how many cakes Alice has eaten, and we should also keep count of the cakes Bob has eaten so far. So, the state could be a pair $(A, B)$, where $A$ is the number of cakes Alice has eaten, or rather the number of cakes Bob can eat (which is the number of cakes Alice has eaten minus the number of cakes Bob has eaten); and $B$ is the number of stacks of cakes that Bob has eaten.

The first stack can only be eaten by Alice, so the initial set of possible states is $\{(1, 0)\}$. Then we start traversing the array of frequencies from the second position and for each one, we apply the recurrence relation:

• For Bob to be able to eat the stack $f_i$ we need a previous state $(A, B)$ such that $f_i \leq A$, and then that state becomes $(A - f_i, B + 1)$.
• If Bob decides not to eat that stack, Alice eats it and the state becomes $(A + 1, B)$.

This seems like we are also trying all possible combinations of taking or not, but the difference is that we don't care about the configuration of the previous state; we only care about how many more cakes Bob can eat and how many stacks he has eaten. This makes the number of possible states to be $O(n^2)$, because $A$ and $B$ can take $O(n)$ different values.

Because we need to go through the frequency array of size $n$, and for each index check $O(n^2)$ states, the total complexity of the algorithm would be $O(n^3)$. This is fast enough to get the result in a few minutes or seconds, but not fast enough for the contest, we need to make it even faster.

$O(n^2 \log_2{2})$ State compression

Do we really need all states $(A, B)$? After passing through the array, the solution to the problem would be $n - \max(B_i)$. So, for every state with the same $A$ we only care about the one with that biggest $B$, as the other options are suboptimal for our problem. Similarly, we could say that for the same value of $B$, we only want the state with the biggest $A$, as it increases Bob's chances to eat future stacks.

This way we only keep $O(n)$ states and then the complexity of the program will be $O(n^2)$. Here is my full submission with this approach:

.cpp#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;

using lli = long long int;
using vi = vector<int>;
using ii = pair<int, int>;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    int t; cin >> t;
    while(t--){
        int n; cin >> n;

        map<int, int> m;
        for(int i = 0; i < n; i++){
            int ai;
            cin >> ai;
            m[ai]++;
        }

        vi f;
        for(auto [_, cnt]: m){
            f.push_back(cnt);
        }
        int nn = f.size();

		map<int, int> dp;
		dp[1] = 0;
		for(int i = 1; i < nn; i++){
			map<int, int> new_dp;
			for(auto [na, nb]: dp){
				if (na >= f[i]){
					new_dp[na - f[i]] = max(new_dp[na - f[i]], nb + 1);
				}
				new_dp[na + 1] = max(new_dp[na + 1], nb);
			}
			dp = new_dp;
		}

		int max_nb = 0;
		for(auto [_, nb]: dp){
			max_nb = max(nb, max_nb);
		}

        cout << nn - max_nb << '\n';
    }
    
    return 0;
}

I got "Time Limit Exceeded" 😐. What happened? I'm using a map to save the dynamic programming state, and map's operations like finding and inserting a key have logarithmic time complexity. So the actual complexity of my program is $O(n^2 \log_2{n})$. $\log_2{5000} \simeq 12$ which is not a small multiplier.

I changed the map to an unordered_map that performs the find and insert operations in amortized constant time, i.e.: $O(1)$, and I got my first "Accepted" on that problem.

$O(n^2)$ Definitely fast enough

Although the previous solution passed, it took 1640 ms to run while other accepted solutions had times around 100 ms. The issue is still in the unordered_map. It performs insert and find operations in amortized constant time, amortized being the important word here. unordered_map uses hashing of the key to place the key-value pairs and to locate them in constant time after the hashing is performed. But the hashing itself is an expensive operation.

For our problem, the keys are numbers from 1 up to 5000, we can implement a map using a simple array where the values are stored in the index corresponding with the key. This is my final submission that ran in 93 ms!

.cpp#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;

using lli = long long int;
using vi = vector<int>;
using ii = pair<int, int>;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
    #endif
    
    int t; cin >> t;
    while(t--){
        int n; cin >> n;

        vi m(5001, 0);
        for(int i = 0; i < n; i++){
            int ai;
            cin >> ai;
            m[ai]++;
        }

        vi f;
        for(int cnt: m){
			if (cnt) {
            	f.push_back(cnt);
			}
        }
        int nn = f.size();

		vi dp(nn + 1, -1);
        dp[1] = 0;
		for(int i = 1; i < nn; i++){
			vi new_dp(nn + 1, -1);
			for(int na = 0; na <= nn; na++){
				int nb = dp[na];
                if (nb != -1){
                    if (na >= f[i]){
                        new_dp[na - f[i]] = max(new_dp[na - f[i]], nb + 1);
                    }
                    new_dp[na + 1] = max(new_dp[na + 1], nb);
                }
			}
			dp = new_dp;
		}

		int max_nb = 0;
		for(int nb: dp){
			max_nb = max(nb, max_nb);
		}

        cout << nn - max_nb << '\n';
    }
    
    return 0;
}