WA in spoj question Magic Grid

general
, , ,
1

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

2

@rajatgoyal

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(NMlog(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 …

3

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