I would do it as a binary (n^2) x (n^2) matrix inversion problem. Without using the terminology of matrix inversion, here is how you would do it 1) For each of the n^2 lights that can be pressed, have a vector<bool> left, where left represents the button that is pressed, and a vector<bool> right, where right represents the lights that get toggled. 2) Now, set integers i and j to be 0, and let indicator be a vector of n^2 int's, initially set to -1. 3) while i < n^2, do the following: 4) if there does not exist a k with k >= j, such that right[k][i] = true (when you press the lights in left[k], light i is toggled), then skip i and return to 3) 5) if there does, choose any such k (say the smallest) and (if k != j), swap left[j] with left[k] and right[j] with right[k]. 6) now right[j][i] = true 7) set indicator[j] = i 8) for all other k (0 <= k < n^2 with k != j) for which right[k][i] = true, let left[j] be the exclusive-or of left[j] and left[k], and let right[j] be the exclusive-or of right[j] and right[k]. 9) increment j 10) return to 3
This algorithm is order n^4 which should be manageable. Note that after doing the swap in step 5) or the exclusive-or in step 8), it remains true that right[i] is the set of lights toggled by pressing the lights in left[i] for all i. Since left and right are not changed by any other steps, it follows that this will always be true, and will be true at the end. Furthermore, if indicator[j] = i, then right[j][i] = true, and for all other k, right[k][i] = false. And for any k that is at lest as large as the terminal value of j, right[k] = false for all k. Then what we have is an automated solver. Essentially, we run through each of the j's for which we have an indicator, and we see if this indicator light is on. If it is, we want to press all of the light switches in left[j]. Cancel out any lights that you are pressing twice, and you should be done. Does that make sense? On Fri, Feb 22, 2013 at 4:25 PM, Registered user <[email protected]>wrote: > problem statement link : > http://www.codechef.com/problems/E2 > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
