## Editorial for DMOPC '21 Contest 10 P3 - Peculiar Reflections

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

What cases are impossible?

What cases require no flips?

How many flips do you need to move the light over?

If , the case is impossible. If , the case is impossible unless . Otherwise, we require that .

Why? Note that for a cell for , we always enter it from one of two directions. If we enter from above or below, but never from the left or right, and the opposite is true if .

Consider the set of cells that we enter from above. Initially we enter , but without flipping anything we enter from above for all . We want to get to , so if we can win without flipping any mirrors.

We can flip two mirrors to move two spots down or left. Effectively this means that we can change from being at the diagonal beginning at to the one at or . Since we want to reach , our answer is .

Build a graph for the input.

Our nodes are .

If the light hits a mirror twice, should we flip that mirror?