I am not able to understand where I am going wrong in this question.

http://www.spoj.com/problems/AMR11A/.

Here’s is the link to my solution: http://ideone.com/dtDpGO

I am not able to understand where I am going wrong in this question.

http://www.spoj.com/problems/AMR11A/.

Here’s is the link to my solution: http://ideone.com/dtDpGO

First of all , I would like to say sorry to you because i am going to post what is not intended here.

I have this solution in my mind…

We can do binary search + (simple DP) …

We can do binary search on the power required by the superhero initially because **X** is the minimum amout of power required to cross the grid then it can also be cross with the **X+1**,**X+2** and so on … This allows us to perform binary search over the power and with the given power we can check we can cross the matrix or not within time **(N*M)**

so the complexity of this solution is O(N*M*log(MAXPOWER)) where MAXPOWER = (N+M-1)x(10^3) it cannot be more than that because of the given constraints…

Cheers codechef and coding

Wishing you a very happy new year

Hope you find this solution useful in some scenario …

Thanks for your help. But this approach will give TLE on spoj. I have got the solution. It is done by filling the dp table table from end,i.e, start from the dp[N][M]=1. The value a dp[0][0] will give the answer.

And my best wishes to you for the year 2015