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

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

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

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

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 154 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/03/2024 15:54:44 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|