hopefully

I tried solving this using greedy using the logic of by letting bob eat the first cake that if he eats entirely then alice wont be able to eat it but it fails so i thought greedy wont work. can you explain your logic plz orz

You can rewrite the problem using the following operations:

min_convolution(f(x), g(x)) where both functions are convex

cut(f(x), c) which returns a function that is f(x) in case f(x) <= c and removes that x from the domain if f(x) > c.

Those are the base for slope trick solutions, so you can code the greedy using slope trick ideas as in https://codeforces.com/contest/1987/submission/268375661

So the answer is yes.

Yes it's greedy

The greedy solution to the problem

https://codeforces.com/problemset/problem/1526/C2

also works.

Here is my submission

https://codeforces.com/contest/1987/submission/268369424

Credits go to Everule for pointing out the similarity, after which I upsolved the problem.

The lazy propagation solution seems to be listed in the editorial for C2.

Thank you for many comments! My latest solution is 268430825 .

#include <bits/stdc++.h>
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> cnt(n + 1, 0);
    for(int i = 0; i < n; i ++) {
        int a; cin >> a;
        cnt[a] ++;
    }
    priority_queue<int> q;
    int sum = 0, valid = 0;
    for(int e : cnt) if(e) {
        valid ++;
        sum += e + 1;
        q.push(e + 1);
        while(sum > valid) {
            sum -= q.top();
            q.pop();
        }
    }
    cout << valid - q.size() << endl;
}
 
int main() {
    int t; cin >> t;
    while(t --) solve();
    return 0;
}