Editorial for Riolku's Mock CCC S3 - Mosey's Birthday

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.

Authors: Plasmatic, Riolku

Subtask 1

The graph is complete, so any sequence of swaps that sorts the sequence will suffice.

Time Complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

Subtask 2

We can solve for each connected component independently.

Observe that each edge is between nodes $a$ ~a~ and $a+1$ ~a+1~ for some value of $a$ ~a~, so a bubblesort on the component will suffice.

Time Complexity: $\mathcal{O}(N^2+M)$ ~\mathcal{O}(N^2+M)~

Subtask 3

We can solve for each connected component independently.

Observation: We can completely sort any connected component. Using this observation, we can easily determine which values in the component need to go to which nodes.

Observe that each component is a line graph. If we first move values whose final positions are on the ends of a line, we can finalize the value at their position as we will never need to cross it for a swap ever again.

This subtask is intended as a hint towards the full solution.

Time Complexity: $\mathcal{O}(N^2+M)$ ~\mathcal{O}(N^2+M)~

Subtask 4

Again, solve for each connected component independently, using the observation from the last subtask.

For each component, take any spanning tree of the component and root it arbitrarily. We can then solve the problem recursively: for any node $u$ ~u~, make sure all the values that need to go into a subtree of $u$ ~u~ have already been moved into place before moving the value that needs to go to $u$ ~u~ (we can use any path to move a value to its correct position).

Once we move a value into its correct node, we never use that node again for swaps so the value stays in place. For any node $u$ ~u~, by moving the values in the subtree of $u$ ~u~ into place first, we guarantee that there are no longer any paths that need to access $u$ ~u~'s subtree, and can thus safely remove them without any issues.

This solution uses a maximum of $\frac{N(N-1)}{2}$ ~\frac{N(N-1)}{2}~ swaps.

Time Complexity: $\mathcal{O}(N^2+M)$ ~\mathcal{O}(N^2+M)~

Notes: Although there were some solutions that used the $K \le 10^6$ ~K \le 10^6~ to pass, and are actually wrong, breaking these solutions is much more challenging than the problem itself, so congratulations to piddddgy and DM__Oscar for making my weekend a hackfest.

Comments

There are no comments at the moment.