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


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

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

kesh4281's gravatar image

accept rate: 0%

edited 14 Mar, 12:33

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

wmoise's gravatar image

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

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 14 Mar, 12:32

question was seen: 295 times

last updated: 14 Mar, 20:40