I was trying to solve 865D - Buy Low Sell High. When I gave up and saw the editorial, this is the idea presented [I am writing this in code form so that it is easy to understand]:
multiset<int> s;
int ans=0;
for (int c: arr) //for every integer in the input array
{
s.insert(c); //insert one copy for FIRST CHOICE
if (c>*s.begin())
{
ans+=c-*s.begin();
s.erase(s.begin());
s.insert(c); //insert second copy for SECOND CHOICE
}
}
return ans;
The solution is really short, which makes it all the more frustrating that I can't prove it.
I have an intuition on why it may work, but I am far from actually proving it.
I thought about it and if the algorithm is correct, at every iteration, ans actually stores the maximum profit that we can earn, if the array in the problem were upto that index.
However, I cannot prove the solution. I feel that if I get the invariant that is maintained in each iteration of the loop, it will help me prove that the algorithm actually outputs the maximum profit, up-to that iteration. By invariant, I mean, what can we say is true for the elements in the multiset for each step, that helps us prove the solution.
In short, I am asking for help to prove this solution properly. Any help will be appreciated.
Read some information on slope trick.
I remember Petr Mitrichev writing about this problem in his blog. Here is a quote from his post:
And here is a blog post where he explains the solution: A future week.
wow, you have phenomenal memory!!
I see that Petr's algorithm is (very) slightly different from the one described in the blog: he pushes two copies, and makes a sale, every-time. It can be shown that when we do greedy, both algorithms coincide. So they give the same answer.
On the other hand, Petr's algorithm is much much easier to prove.
1) We can show that every sequence of sales can be represented by his algorithm [we can do this by construction: Consider ANY valid sequence. For each $$$i$$$, if $$$a_{i}$$$ is NOT to be sold, we can do the sale with one copy of itself, hence gaining $$$0$$$ profit. Hence one copy remains. If $$$a_{i}$$$ needs to be sold, we can sale it with one remaining copy of the element which is paired off with this $$$a_{i}$$$.]
2) It is also clear that any run of algorithm corresponds to a valid sequence of sales. [the invariant that I was looking for is here: if two copies remain, this means that the item is in sale, if one copy remains, this means the item is neither bought not sold, if zero copies remain, the item is bought. This invariant is maintained throughout each iteration].
3) So these two are processes are equivalent, hence let's find the maximum profit using algorithm. Using greedy exchange, prove that always taking minimum works.
Thanks again. This solves my issues!!!
Another problem like this was in SEERC 2020, problem A. There is a nice description of the solution in the comment on codeforces.
In short, when you have a convex dynamic programming, you can store the differences between subsequent dp values in set or pq. The update operations can be seen as shifts of the whole dp which are just removals from the set or additions of a single element.
nice post!