Lights out - shortlist

Cosmin Negruseri
09 iunie 2016

In 2005 I used to write some articles for Ginfo (the romanian informatics gazzette, targeted towards highschool and university cs students). Each article contained a set of problems that were all related in their solution or setup. Quite a few of those articles are on infoarena as well, you can find them by looking for titles that start with "Probleme cu" in the article section (only in romanian).

Writing one of those articles used to take me quite some time, and I have a few drafts remaining. Instead I've resorted to writing shortlists. I write the problems and people solve some of them in the comments :).

I was talking to my friend Slava Gurevich today and he reminded me of this set of problems that I was meaning to write about 10 years ago. So thanks Slava :).

The problems are based on the game Lights Out. They were used in various romanian and other international contests. They vary in difficulty from technical interview level to university coding contest.

Give them a try in the comment section:

1. (technical interview) You are given a 3×3 grid of light bulbs. Some lights are “on”, and some are “off”. Next to each light there is a button. Pressing that button results in toggling the state of both the current light and its four adjacent lights (left, right, up down). For a given configuration find the minimum number of button presses such that all the lights are “off”.
2. (training LOT98) You are given a grid of lights of size NxM (N, M <= 1000). Some lights are “on”, some are “off”. A move consists in choosing a rectangle of size PxQ and toggling the state of all the lights in that rectangle. Come up with an algorithm that finds the minimum number of moves that turn all the lights off.
3. (OJI9*) Again, you are given a grid of NxM lights, that can be either “on” or “off”. One move consists in choosing a row or a column in this grid and toggling the states of all the lights in that row or column. Come up with an algorithm that finds the minimum number of moves to switch all the lights “off”.
4. (LOT9*) Same problem as 1, but the grid size is 20×100.
5. (LOT95) You are given a tree of n <= 1000000 nodes and n - 1 edges. Each node of the tree contains a light bulb and a button. Pressing the button in a node switches the state of the light bulb and the adjacent light bulbs. Come up with an algorithm that finds out the minimum number of button presses to switch all the light bulbs “off”
6. (SGU) You are given an undirected graph of n <= 100 nodes. Each node contains a light bulb and a button. Pressing the button in a node toggles the state of the light bulb and its adjacent light bulbs. Come up with an algorithm that finds out if there is any solution that turns all the lights “off”.
7. (SGU/TOPCODER) Same setup as 6. Come up with an algorithm that finds out how many different solutions there are.
8. (LOT06) You are given a grid of lights of size NxM (N, M <= 1000). Some lights are “on”, some are “off”. A move consists in choosing a cell and switching the state of the lights on the same row and same column but leaving the chosen cell in the same state. Come up with an algorithm that finds out the minimum number of moves to turn all the lights “off”.
9. (CEOI 2000) Planet-X