Mansur4ik's blog

By Mansur4ik, history, 5 weeks ago, In English

Hello, Codeforces!

Can someone please help with this problem?

I would be grateful, thank you!

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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