Now unfortunately Step 2 is quite complex and should probably be done before the tournament starts. I can't see a way of solving this problem without it, but maybe other readers can inform how it could be done.
Step 2: Gain a working knowledge of the subject area (in this case: Linear Algebra) I recognise that this is a linear algebra problem in NM variables over the field of 2 elements, with (NM+K) constraints. There is a general method for solving such problems, which takes time O(V^2C) where there are V variables and C constraints. In this case, the complexity can be as high as 10^30, so we need something cleverer. A general Linear Algebra instinct I have comes into play here, which is that it is easier to deal with linear equations with 0 on the right hand side. So if we can find any solution to Odd It Out and subtract it from our problem, we will instead be dealing with Even It Out, which is likely to be easier. It is easy to find such a solution: Just let b[i,j] be 1 if i and j are odd, and 0 otherwise Then if we let c[i,j]=a[i,j]+b[i,j] (mod 2), we are looking for solutions to c[i,j]+c[i,j+1]+c[i+1,j]+c[i+1,j+1]=0 (mod 2). To be continued... On 30 Apr 2012, at 05:58, Registered user <[email protected]> wrote: > > Problem Statement > It was not very long after the Captain Jack Sparrow returned from his > quest from the Fountain of Youth, when he heard rumours about the > treasure that Blackbeard had hidden. It was said that the treasure > being talked about was the most precious treasure of all times. He and > Gibbs set out to find the truth about the treasure and the treasure > itself, if it existed. > > After a lot of hard work, he found that the rumours were actually > true. The treasure was still safely hidden somewhere near the Bristol, > the birthplace of Blackbeard. But it was also said that Blackbeard had > taken extreme precautions and used his extensive skills of dark magic > to hide the treasure safely. > > Captain Jack Sparrow recalled that Blackbeard was famous not only > because of his notoriety, but also for his wits. Legend has it that he > went undefeated in the famous game named Odd It Out. The game consists > of a matrix and to win, it is required to fill the matrix with two > colours such that no 2x2 square has even number of any colour. Jack > Sparrow knew that it would not be easy to get to the treasure. > > After days of exploration, Captain Jack Sparrow and Gibbs finally find > some remnants of Blackbeard's belongings in a long deserted > island.They proceed for a mile or so, when they face the entrance to a > dark and formidable cave. They go inside the cave, but mysteriously, > the mouth of the cave closes and they are trapped inside. They have no > other option but to continue into the cave till the either end of the > cave or their life! After some time, they arrive in a well lit > antechamber. Captain Jack Sparrow immediately spots the engraving in > the wall, that said – “T’ treasure you look for, lies close t’ you. > But advance only those who be smart enough. Odd it Out and prove > yourselves worthy o’ me treasure. I have already done some work for > ya. Completin’ t’ puzzle be not a difficult task, my friend! But if > you tell me t’ number o’ ways in which you can complete t’ puzzle, > without disturbin’ ma design, t’ gates to your fortune will open, if > not, death awaits you. Think wisely as time is short.” > > They find an n*m matrix drawn on ground, with some square and some > triangular rocks already arranged at some positions. They understood > that the two different rocks resemble the two colours. As Captain Jack > Sparrow, your task is to report the number of ways to complete the > puzzle modulo 10^9 to get to the treasure. > > Input > The first line of the input has three inputs, n, m and k, the number > of rows, number of columns of the table and the number of initially > placed rocks. The next k lines contains data about the initially > placed rocks. The ith line of this section contains three integers x,y > and s, where x and y are the row number and the column number of the > ith rock and s is the shape of the rock. s is 0, if the rock is a > square one and 1 if triangular. It is given that the k cells have > distinct positions. > > Output > Report the number of ways of completing the puzzle modulo 10^9 > > Constraints > For the initial configuration, > 1 <= x <= n and 1 <= y <= m > 2 <= n,m <= 10^5 > 0 <= k <= 10^5 > > Sample Input > 3 4 3 > 2 2 1 > 1 2 0 > 2 3 1 > > Sample Output > 8 > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" 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/google-code?hl=en. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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/google-code?hl=en.
