Mansur4ik's blog

By Mansur4ik, history, 6 weeks ago,

Hello, Codeforces!

 » 6 weeks ago, # | ← Rev. 2 →   0 We can start by sorting all plates. This makes it possible for us to see how the orientation will be after finishing the operations. Now, we can see, in the problem's example, [1w 2w 3b 4w 5b] has 2 partitions for white, 2 partitions for black. As both the original stack and the results are sorted, the original stack is a subsequence of the final sequence. Hence, the answer, as you may have noticed, is $2P-c-1$ ($P$ being number of partitions, $c$ being the amount of unique colors).Now for the tiebreaking part. We want each range of same numbers to have a minimal amount partitions, because more partitions = more operations. Therefore, for each range of same numbers, we match the first partition to the color above, and match the last partition to the color below (if possible). In this way, we do not have to split the first partition and the last partition, and the total partition count is reduced. Do notice that the previous color may not yet be determined, in this case we have to write a DP solution, $O(cN+NlogN)$ precisely.
•  » » 6 weeks ago, # ^ |   0 TL;DR: minimize the amount of partitions on the constraint that the final sequence is sorted, and then the answer is $2P-c-1$ where $P$ is the number of partitions and $c$ is the amount of stacks originally