# how to solve ALGOA

my solution gets WA more 30 times and i dont know why it’s wrong ,please help me to find where it’s wrong.this is my code . thanks

Hello, I also have the same doubt

I used recursion (brute force) but still got more than 15 WA

https://www.codechef.com/viewsolution/12950313

can someone point out any mistake?

I saw many people solved using BFS, I’ve understood their approach but where did mine go wrong?

Create a graph such that there is a directed edge between every 2 consecutive indexes with weight 1. Also assign weight equal to 1 between i and i+p[i](directed edge) for all i<=n. Finally run dijkstras to get the shortest path from root(0) to target(n).

Run Dijkstra with edges from i to i+1 and i to i+p[i].Since n<=20 and edges<=40 O(N+M)*T would pass.IF p[i] was non negative one could have used dp here.

assert(n>=0) was not working in given code.
https://www.codechef.com/viewsolution/12951258
It may be one of the reasons of WA.@akshayv3,@swetankmodi

there are some cases for which n < 0 , i also got 21 wa due to this…

so what we should print if n<0 ?

if n<0 print 0.
After 25 WA got AC.

The test cases were inconsistent. I made a lot of submissions on this question, only to get RE(SIGABRT) each time. Got fed up of it and just gave up on the contest as I had put in way too much time on this question. Today I login to find that they have rejudged the submissions (after the contest maybe, not sure) and that my very first submission was AC.

This is ridiculous.

By the way I used DP instead of Dijkstra. It’s just that I make more than one iteration (n times, to be exact) over all states starting from 0, to make sure my answers are updated. Note that this wouldn’t have been a problem had p[i] been only positive.

@utkarsh1997 Could you explain your apprach?

There was some problem in the test cases. I have solved it by using dp, but it gave Runtime Error. And I left the contest without attempting any questions because this is very disappointing that you are giving your full energy and then come to know afterwards that there was some error in the problem. But, today I find that the solution was accepted.

I will explain the approach.

Let define dp[i] which state that the minimum number of steps require to reach at ith position. Now consider that you are at ith position. There are two ways to move forward.

``````  This is equal to minimum of (dp[i+1],dp[i]+1).
So, dp[i+1] = min(dp[i+1],dp[i]+1)
``````
``````  if (i+p[i]) is greater than i and less than or equal to n. Then, you can jump directly to
(i+p[i])th position.
So, dp[i+p[i]] = min(dp[i+p[i]],dp[i]+1)

Now if (i+p[i]) is less than i and greater than or equal to 0, then check that the minimum steps
require to reach at (i+p[i])th position is less than (make sure that it should be strictly less
than) dp[i]+1. If it is less than dp[i]+1, then again start updating dp from (i+p[i])th postion.
See my solution if this is difficult to understand.
``````

So, start the loop from 0th position to (n-1)th position and update dp accordingly by using above two ways.