## December CookOff Contest Problem Editorials |

**Problem Setter** for the contest was Zac Friggstad.

**Problem Tester** for the contest was Rajiv Kumar Aggarwal.

----------------------------------------------------------

COMMUTE : The Morning Commute

----------------------------------------------------------

PAIRING : Pairing Chefs

----------------------------------------------------------

PREPARE : Preparing Dishes

----------------------------------------------------------

PUZZLES : Newspaper Puzzle

----------------------------------------------------------

SEEDS : Seeding The Pattern

----------------------------------------------------------

## In SEEDS one can obtain algo

anton_lunyov@ 20 Dec 2010 01:25 AMIn SEEDS one can obtain algo with complexity O(H*d*d+H*k*d+d*d) per test, where H=31

First note that matrix multiplication by modulo 2 can be done in O(d*d) time (since d<32) using bit arithmetic:

(A*B)(i,j) = BitCount(rowA[i] & colB[j])

BitCount(x)=BitCount(x/1024)+BitCount(x%1024)

and numbers BitCount(x) for 0<=x<1024 simply precalculated.

The main trick consider transpose of A.

Denote it again by A.

Then the coefficients of the linear combination of the seeds that yield x_i are then found on the last column of the matrix A^i. But last column of matrix is the product of matrix and the column u = (0,0,...,1).

So here the algo.

Precalc all binary powers A[h] = A^(2^h) for 0<=h<H --> O(H*d*d)

For each of 0<=j<k we need find A^i(j) * u

Let i(j)=2^(r_0)+2^(r_1)+...+2^(r_q) then

A^i(j) * u = A[r_0]*(A[r_1]*...*(A[r_q]*u))

But product of matrix and vector can be calculated in O(d) time using binary arithmetic tricks above. Since q<=H we see that this step done in O(k*H*d) time.

And finally we need apply Gaussian algo which is usually O(d*d*d) but again with binary arithmetic tricks it becomes O(d*d).

My algo in the contest is d time slower since I did not implement these binary tricks.

But this is because I first solve the problem with p=1000000007 where there is no such tricks.

And even without this tricks its in more than ten times faster then other solutions.

I loose first place because of printing “no solutions” instead of “no solution”.

What a pitty! :-(

## In the question "Preparing

jimmy valentine@ 20 Dec 2010 02:33 AMIn the question "Preparing Dishes" , I could not figure out why we are using binary search algorithm here. Please help.

Thanks.