Eddagdeg's blog

By Eddagdeg, history, 4 years ago, In English

Hello! There is a field n×m, and k of its cells are impassable walls. A robot is initially at the cell (1,1) (bottom left). The robot can only move right or up, and eventually it needs to get into the cell (n,m), avoiding all obstacles. You need to count the number of ways he can do it. Assume that the sizes n and m are very large (say, 109), and the number k is small (around 100) how to solve that in o(k^3)? any hint please and thanks!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/blog/entry/47764

Read the part "Change object to DP"