You are not logged in. Please login at www.codechef.com to post your questions!

×

# what was the logic to get 100 pts for TREASURE HUNT in march long challenge?

 0 I could only get 30 pts with dp i have seen other ppl submission but dont know the logic they are using asked 14 Mar, 12:32 5★kesh4281 1●1 accept rate: 0%

 3 You need to find the number of cells that can be independently changed. All the other cells are determined once you find those. Because you can choose those x cells, the number of possibilities is $2^x$. Make each cell a variable and using the number system integers mod 2, you can represent all the constraints as a linear system of equations. Each equation is essentially an xor operation. The system equations form a matrix. You can then solve using Gaussian elimination to find the rank of that matrix, which gives the number of independent equations in that system. If there are n cells, than the number of independent variables is $x = n - rank(matrix)$. Compute $2^x mod (10^9+7)$. answered 14 Mar, 14:14 7★wmoise 138●2 accept rate: 8% I also passed it that way but won't the complexity of this be O(n^3). Even with bitset optimisation it will be 900^3/64 and there are 100 testcases. Is my assumption correct or am I missing something here ?? (14 Mar, 20:40) sdssudhu6★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×427
×75
×56
×10

question asked: 14 Mar, 12:32

question was seen: 295 times

last updated: 14 Mar, 20:40