Discussion @ 1029. Ministry @ Timus Online Judge

karan Approach [3] // Problem 1029. Ministry 28 Aug 2013 17:59

I used dijkstra to do in O(mnlog(mn))? Whats your approach?

Nikunj Banka I used dp [1] // Problem 1029. Ministry 14 Oct 2013 15:16

I used dynamic programming to solve the question.
dp[floor][room][lastStep] indicates the best way to reach top when we are on floor, room and the last step is know. Each state of dp is solved in constant time as we have to do only 2 computations at each step. But my approach runs very very slow.

ძამაანთ [Tbilisi SU] Re: I used dp // Problem 1029. Ministry 29 Oct 2013 02:39

Two dimensions are enough

Han Lin Re: Approach // Problem 1029. Ministry 9 Apr 2014 12:24

DP can solve this problem in O(MN).

Discussion of Problem 1029. Ministry