December 2011 Contest Problem Editorials | CodeChef

December 2011 Contest Problem Editorials

Problem Tester for the contest was David Stolp.

Birthday Gift (written by Vamsi Kavala). The Editorials can be found here.

Hypertrees (written by Gennady Korotkevich). The Editorials can be found here.

Robot Movings (written by Anh Duong Quang). The Editorials can be found here.

Short II (written by Gennady Korotkevich). The Editorials can be found here.

Spinning Wheels (written by Gennady Korotkevich). The Editorials can be found here.

Ciel and Eggs (written by Hiroto Sekido). The Editorials can be found here.

One of the way to speed up

3★rajneesh2k10 @ 11 Dec 2011 11:44 PM
One of the way to speed up your computation of pascal triangle is to replace '%' operation by a '-' operation, which lead to acceptance of solution of problem MOVES by pre-computing pascal triangle. :)

how we can replace % with

1★dabbcomputers @ 12 Dec 2011 02:57 PM
how we can replace % with '-'....?? i used my own mod function to reduce complxity.... ie (x-(x/n)*n)

All the test cases cannot be

4★javadecoder @ 12 Dec 2011 04:32 PM
All the test cases cannot be worst cases,also K<=N ,so it is in order of 10^8,that is why 8s time limit...

@dabbcomputers: Since the

4★javadecoder @ 12 Dec 2011 04:35 PM
@dabbcomputers: Since the computation of pascal triangle involves only the ADDITION of previously computed results,you can rewrite the expression: C[n][r]=(C[n-1][r]+C[n-1][r-1])%mod -----------> C[n][r]=C[n-1][r]+C[n-1][r-1] ,if(C[n][r]>=mod) C[n][r]-=mod This way the computation will be much faster,as it does not involve modulus operation.