11486 - Finding Paths in Grid
Posted: 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).
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).