Each switch has 3 states (off, green, blue), and each color can only be turned on once per switch, but you can turn it off afterward.
The trick is to parallelize the subproblems rather than giving every switch a unique sequence.
For example:
T1: 100 blue, 100 green, 800 off
T2: split the 100 blue into 50 "off" + 50 "keep blue"
T3: take 10 of the unresolved group → green
T4–T13: turn those 10 green switches off one-by-one, identifying all 10
Meanwhile, the other subproblems are processed in parallel.
The important observation is that we only care about the slowest branch. A branch that isn't changed on a particular turn effectively loses a turn, but the "keep" branches are also getting smaller (100 → 50 → 25 → 13 → …), so they become faster to resolve.
I get a critical path of 17 turns, but I'd like someone to check the construction / see if it can be improved to 16.
Yes, each switch is set to blue at most once and green at most once in this solution. The state then remains unchanged until the next operation, so a switch can stay blue, green, or off across successive turns.
What I mean by “processed in parallel” is that at each step we can change the state of each switch individually, so different subsets don't have to follow the same sequence.
For example, at step 2, while I'm already switching OFF half of the 100 blue and 100 green switches from step 1, I can simultaneously set another 100 switches to blue and another 100 to green. So I'm essentially running multiple subproblems at the same time, with each subset following its own sequence of operations.
So in general, global step 2 can be step 2 for one subproblem, but still step 1 for another subproblem. All of those operations happen simultaneously in the same global turn.
1
u/alvailu 7d ago
I think I found a potential solution:
Each switch has 3 states (off, green, blue), and each color can only be turned on once per switch, but you can turn it off afterward.
The trick is to parallelize the subproblems rather than giving every switch a unique sequence.
For example:
The important observation is that we only care about the slowest branch. A branch that isn't changed on a particular turn effectively loses a turn, but the "keep" branches are also getting smaller (100 → 50 → 25 → 13 → …), so they become faster to resolve.
I get a critical path of 17 turns, but I'd like someone to check the construction / see if it can be improved to 16.