11486 - Finding Paths in Grid

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
quol
New poster
Posts: 3
Joined: Sat Sep 13, 2008 11:53 pm

11486 - Finding Paths in Grid

Post by quol » Sat Oct 11, 2008 10:28 pm

Hello,
can anyone give me a hint how to solve this problem effectively?

Here's what I tried:

For the 840 possible states I calculated the adjacency matrix.
Then I used matrix multiplication to precalculate the number of paths of length 2^1 ... 2^30 from each state to each state.

Then for each test case I multiplicated the precalculated matrices to calculate the number of paths.

Even though this solution runs in O(log n) time, of course it is way to slow, as multiplicating two matrices of size 840x840 takes 840^3 steps (using the primitive approach).

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11486 - Finding Paths in Grid

Post by emotional blind » Sun Oct 19, 2008 8:12 am

Number of possible states is less than 840.

Post Reply

Return to “Volume 114 (11400-11499)”