Editorial for Yet Another Contest 7 P1 - Page Turning

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

Every piece where a_i is odd will always have an inconvenience of \frac{a_i-1}{2}, no matter where it is placed, so any ordering of the pieces is optimal. Therefore, we simply need to output the sum of all \frac{a_i-1}{2} along with any ordering.

Time complexity: \mathcal{O}(N)

Subtask 2

Since pieces with odd lengths always have the same inconveniences, we should focus on the pieces where a_i is even. If the piece starts on an odd page, the inconvenience is \frac{a_i}{2}, but if the piece starts on an even page, the inconvenience is only \frac{a_i}{2} - 1.

It follows that we should maximise the number of pieces with even length that start on an even page. There are two possible cases:

  • If there is at least one piece with an odd length, we should output one piece with a odd length, then all of the pieces with even lengths, then all the remaining pieces with odd lengths. This allows every piece with an even length to start on an even page.
  • If every piece has an even length, then every piece will start on an odd page. Thus, the ordering of the pieces doesn't matter.

Time complexity: \mathcal{O}(N)


There are no comments at the moment.