shinchankosen's blog

Is greedy right?
By shinchankosen, history, 6 months ago, In English

Problem D in EPIC Institute of Technology Round Summer 2024

I'm not good at English, and this is my first post. I usually post here in Japanese. Nice to meet you.

These are my solution.

$$$O(N^2)$$$

Tutorial says DP, and most Accepted programs are DP, too.

But, my program is greedy. Is greedy the correct way to solve it?

C++ 109 ms

$$$O(N \log N)$$$

use Lazy Segment Tree. If the above greedy is correct, then lazysegtree can be used.

C++ 62 ms

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

hopefully

→ Reply
»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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://mirror.codeforces.com/contest/1987/submission/268375661

So the answer is yes.

→ Reply
»
6 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Yes it's greedy

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The greedy solution to the problem

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

also works.

Here is my submission

https://mirror.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.

→ Reply
»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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;
}
→ Reply