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

# | User | Rating |
---|---|---|

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

5 | Um_nik | 181 |

6 | antontrygubO_o | 173 |

7 | maroonrk | 168 |

8 | errorgorn | 165 |

9 | kostka | 164 |

9 | SecondThread | 164 |

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

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:

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

**PROVEN**]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!

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2022 18:05:41 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|