## Editorial for Yet Another Contest 3 P1 - Shell Swap Scam

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

#### Subtask 1

By examining small cases, or by guessing, we can assume that there always exists a solution when there is exactly one unknown swap. The proof of this lies in the construction presented in subtask . This means that for all unknown swaps apart except for one, we can choose the swapped stones arbitrarily.

All that is left is to choose the final unknown swap. Since there are only three possible final swaps, we can check each of them by simulating through all moves in .

**Time complexity:**

#### Subtask 2

As in Subtask , we assign all unknown swaps except for one arbitrarily, such that there is only one unknown swap. We are no longer guaranteed that there are only three possible swaps, so we need a smarter algorithm.

Let be the position of the stone just before the unknown swap, and let be the position that the stone needs to be in just after the unknown swap in order to end at . We can find by simulating forward through the swaps, and find by simulating through the swaps in reverse order.

Then, if , we can choose to swap and in the unknown swap. Otherwise, we can just choose two distinct shells which are not equal to , and swap them instead.

**Time complexity:**

## Comments