Flashing Fluorescents
Time limit2sMemory limit512 MB
Given up to 16 initial light states, find the earliest time at which all lights can be simultaneously on, where each button press sends a delayed toggle wave down the line and overlapping waves cancel.
- Level
Hard8 of 10
- Topics
- BFS, Bit manipulation, Greedy, Implementation
- Solved
- No attempts yet
Problem
You have n lights in a line, each with its own button. Pressing a light's button toggles that light's state: if the light is on, it turns off, and if it is off, it turns on. The lights change at 1-second timesteps. You can press a button at any time, but the press will not take effect until the next timestep. Before each timestep, you may choose to push at most one button (you may also choose not to press any button).
Pushing a button affects not just the light in question, but all lights down the line. More specifically, if you press the ith button right before the kth timestep, then the (i + m)th light toggles on the (k + m)th timestep (with i + m ≤ n). For example, if you press button 5 just before time 19, then light 5 toggles at time 19, light 6 toggles at time 20, light 7 toggles at time 21, and so on. If you push a button whose effect would occur at the same time as a toggle that an earlier button press would cause, the two cancel each other out, and the same goes for the subsequent toggles.
Suppose there are three lights, all off at the start. If you press the first button before the first timestep, this is what happens over three timesteps:
Now suppose you press the first button before the first timestep, and then the second button between the first and second timesteps. That button press cancels the propagation, and this is what happens (note that the propagation goes no further):
Now suppose you press the first button before the first timestep, and then the third button between the first and second timesteps. All three lights are on at the second timestep (but not at the third):
You want to turn on all the lights. What is the earliest time at which you could possibly see all of the lights turned on? Note that if the lights are all on at time t but not at time t + 1 because of this propagation, t is still the correct answer.
Input
Each input consists of a single test case. Your program may be run multiple times on different inputs. Each test case consists of a single string S (1 ≤ |S| ≤ 16). The string S contains only the characters 1 and 0, where 1 means that light is initially on and 0 means that light is initially off. The first character is light 1, the next is light 2, and so on.
Output
Output a single integer: the earliest time at which all of the lights are on.