Step 1: Translate it into Maths. There is a 2-dimensional array of n x m bits. You are given the values of k of those bits. Calculate the number of ways (modulo 10^9) of filling those other nm-k bits so that each 2x2 subsquare contains an odd number of bits. n, m and k are bounded above by 10^5.
or, even more mathsy: Find the number of solutions (modulo 10^9) of: 0 <= a[i,j] <= 1 for all 0<=i<n and 0<=j<m, a[i,j]+a[i,j+1]+a[i+1,j]+a[i+1,j+1]=1 (mod 2) for all 0<=i<n-2, 0<=j<m-2 given k values of a[i,j]. 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.
