Even though I was orange before the round, my Edu 118 was rated. In fact, even LGMs got rated.

MikeMirzayanov

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.

Here is the link to the problem: 987E - Petr and Permutations

My solution is:

1. A constructive algorithm to count the number of steps from the identity permutation to the given input permutation. [PROVEN]

2. Compare the parity of the number of steps required with the parity of $$$3n$$$ and $$$7n+1$$$ and print Petr or Um_nik.

Now, I have used the following lemma: If one permutation $$$P1$$$ can be reached from another permutation $$$P2$$$ in even number of steps, then it is not possible to reach $$$P1$$$ from $$$P2$$$ in odd number of steps. Similarly, vice versa.

I can't prove this lemma, and I have tried:

• Induction
• Greedy proof techniques

and they don't seem to work. Any help will be appreciated! Thanks!