Editorial for DMOPC '22 Contest 2 P2 - Line Trace
Submitting an official solution before solving the problem yourself is a bannable offence.
Suppose with a given configuration our output is some array . If we add a connecting line after all existing connecting lines, what happens to our output?
If the connector connects lines and , then our output is the same but with index and swapped.
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.
Furthermore, the number of moves required is the number of adjacent swaps required to get from the identity to . Bubble sort can count this for us easily.
Many will also notice that the answer is simply the number of inversions in the array.
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.