There are a lot of simplifications you can make to get this problem down to a manageable size.
First of all, notice that each of the four buttons inverts itsself. So if you press it twice, you are back to the initial state. The order of button pushes does not matter. Any order of the same button pushes will result in the same set of lights being on. Thus you only need to know if it was pushed an even number of times or an odd number of times. The value of C limits the options if it is less than 4. If C is 3, then all four buttons could not have been pushed an odd number of times. Either 1 or 3 of the buttons was pushed an odd number of times. If C is odd, then an odd number of buttons were pushed an odd number of times. If C is even, and even number of buttons were pushed an even number of times. Now here is the big one which really is not mentioned in the solution. You only need to know the state of lamps 1-6. If you know the state of lamp x, lamp x+6*y is the same. This is true because each button works on an interval divisible by 6. Button 1 affects all lights, button 2 and 3 affect alternating lights, and button 3 affects every third light. So if light 2 is on, so is light 8, 14, 20, etc. You just need to try the 16 possible combinations of odd/even button pushes. At most eight of them will be possible based on the value of C. Determine the final state of lamps 1-6, and then determine if that is consistent with the given final states. If so, output that result. Don On Sep 16, 12:05 pm, Blackwizard <[email protected]> wrote: > I've read this following solution from USACO for "IOI98 - Party Lamps" > problem..but I don't know why 2^4 and I don't know why the complete > search works for this problem...!!! > I didn't get exactly what it say... > Can anybody help me to understand it? > > Thanks... > > IOI 98 - Party Lamps: > > http://olympiads.win.tue.nl/ioi/ioi98/contest/day1/party/party.html > > USACO solution with compelete search: > > You are given N lamps and four switches. The first switch toggles all > lamps, the second the even lamps, the third the odd lamps, and last > switch toggles lamps 1, 4, 7, 10, ... . > Given the number of lamps, N, the number of button presses made (up to > 10,000), and the state of some of the lamps (e.g., lamp 7 is off), > output all the possible states the lamps could be in. > Naively, for each button press, you have to try 4 possibilities, for a > total of 410000 (about 106020 ), which means there's no way you could > do complete search (this particular algorithm would exploit > recursion). > Noticing that the order of the button presses does not matter gets > this number down to about 100004 (about 1016 ), still too big to > completely search (but certainly closer by a factor of over 106000 ). > However, pressing a button twice is the same as pressing the button no > times, so all you really have to check is pressing each button either > 0 or 1 times. That's only 24 = 16 possibilities, surely a number of > iterations solvable within the time limit. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
