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?

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

5★kesh4281
11
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)$.

link

answered 14 Mar, 14:14

wmoise's gravatar image

7★wmoise
1382
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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×427
×75
×56
×10

question asked: 14 Mar, 12:32

question was seen: 295 times

last updated: 14 Mar, 20:40