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

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

,#### Subtask 1

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

**Time Complexity:**

#### Subtask 2

We can solve for each connected component independently.

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

**Time Complexity:**

#### 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:**

#### 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 , make sure all the values that need to go into a subtree of have already been moved into place before moving the value that needs to go to (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 , by moving the values in the subtree of into place first, we guarantee that there are no longer any paths that need to access 's subtree, and can thus safely remove them without any issues.

This solution uses a maximum of swaps.

**Time Complexity:**

**Notes**: Although there were some solutions that used the to pass, and are actually wrong, breaking these solutions is much more challenging than the problem itself, so congratulations to and for making my weekend a hackfest.

## Comments