Step 3: Play around with the problem a bit to gain some traction. (This is the way I do it - other people may have other methods)
Try and get a feel for what solutions to Even It Out look like. The sample case has 8 solutions - what do they look like? Remembering that we have to flip any bits that are at the intersection of an odd row and an odd column (none of which are specified in the sample data), we are trying to solve ?0?? ?11? ???? with every 2x2 subsquare having an even number of 1's. The top left bit can be 0 or 1, and then by considering the top left square, the middle left bit has to be the other one. 00?? 111? ???? or 10?? 011? ????. By looking at the square starting at the 2nd element on row 1, we know the 3rd element on row 1 must be a 0. 000? 111? ???? or 100? 011? ????. Now the top right bit can be 0 or 1, and then by considering the top right square, the middle right bit has to be the other one. This gives us four possibilities. 0000 1111 ???? 0001 1110 ???? 1000 0111 ???? or 1001 0110 ????. Now, once we choose the bottom left bit, we can work out the bit that is 2nd on the bottom row (from the bottom left square), and then the bit that is 3rd on the bottom row (from the bottom middle square) and finally the bottom right bit (from the bottom right square). This gives us 8 possibilities: 0000 1111 0000 0000 1111 1111 0001 1110 0001 0001 1110 1110 1000 0111 0111 1000 0111 1000 1001 0110 0110 or 1001 0110 1001. Hopefully, by looking at these results, we should have the "Aha!" moment: Every two rows are either identical or complementary and every two columns are either identical or complimentary. Now you can decide if you want to prove it, test it by more investigations, or just rush into a solution, hoping it is right. I often choose the latter. 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.
