Editorial for DMOPC '22 Contest 2 P2 - Line Trace


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: Riolku

Hint 1

Suppose with a given configuration our output is some array X. If we add a connecting line after all existing connecting lines, what happens to our output?

Hint 2

If the connector connects lines i and i + 1, then our output is the same but with index i and i + 1 swapped.

Part Marks

Because of the above observation, it's clear that an output is achievable iff it is a permutation, since all permutations can be achieved through some number of swaps.

Full Solution

Furthermore, the number of moves required is the number of adjacent swaps required to get from the identity to A. Bubble sort can count this for us easily.

Many will also notice that the answer is simply the number of inversions in the array.

Extra

The ability for lines to be non-horizontal is really just to confuse the reader. It can be shown with topological sort that any configuration with non-overlapping lines can be turned into a configuration with only horizontal lines.

On the topic of overlapping lines, they are excluded to avoid confusion. However, it can be shown that any configuration with overlapping lines is suboptimal, and can be replaced with a better one with no overlapping lines.


Comments

There are no comments at the moment.