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?
$$$O(N \log N)$$$
use Lazy Segment Tree. If the above greedy is correct, then lazysegtree can be used.
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://mirror.codeforces.com/contest/1987/submission/268375661
So the answer is yes.
Thanks for the reply! It's good to know that greedy is the correct solution. I didn't know about the slope trick, so I'll go study it.
I just learned slope trick. I understand that it can be applied to this problem!
can you share please the source for learning slope trick
I used this (maspy). But it is written in Japanese.
In this article, https://mirror.codeforces.com/blog/entry/47821 (zscoder) and https://mirror.codeforces.com/blog/entry/77298 (Kuroni) are listed as a reference.
Thanks
Yes it's greedy
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.
Thank you for many comments! My latest solution is 268430825 .