PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
Of course the problem is very much alike the famous Lights Out puzzle. However the size of the board can be big enough and we can’t just tap any cell, but adjacent ones in any 8-directions. Let’s see how it changes the solution. Remember that we only need to find out if the puzzle is solvable.
First we can see that if both dimensions of the board are greater than 1, than the fact that we can tap only adjacent cells doesn’t matter. For example if we consider 2x2 board then starting from any initial cell and from any configuration we can achieve any other configuration and finishing in any other cell. So for bigger boards we can divide the board into 2x2 sub-boards (maybe overlapping) and we can have any configuration we need. The situation is different when one of the dimensions is 1. We will look into it later.
So now both dimensions are more than one and also the statement has it that one of the dimensions is less than 40. Let us consider that 1 < m < 40 and m <= n. Let us work with single lights independently. For each single light turned on (red cell) we can use light chasing method to move the lights to the lowest row. However the number of rows can be large, so we can’t just simulate the steps. We can see that when we eliminate each row there are at most two rows in which the light can be on. And the configuration of these rows on the next step depends on the previous. So the state of the light chasing can be represented by 2 * m bits. And those states go in cycles. Also despite that there are 2 * m bits the actual lengths of the cycles are not large for m < 40. So, for example for the light on in x-th row and y-th column, the calculate the cycle for light chasing starting from the light in y-th column and the take the state number n-x modulo the length of the cycle. Then we merge all the configurations of the last row for all the red cells. We do the same starting from configurations we get after tapping each cell in the first row. No the puzzle can be solved by the standard method for Lights Out involving Gaussian elimination. Alternative way to chase all the lights to the bottom row is using matrix exponentiation.
As it was said before when one of the dimensions in 1 the situation is different. We can see that when Johnny start movement he stepped on 0 cells and his position is 1. When he makes the step he changes the position and step count by one. So we can see that the step count and his position will always have different parity. So not all the configurations are reachable unlike when dimensions are greater than 1. Now we need to check: 1) if it’s possible to turn all the cells blue; 2) how many steps it is needed to do this; 3) if the parity of the final position is different to the parity of number of steps. After checking this and alternatively trying to tap the very first cell we can decide if the puzzle is solvable in this case.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.