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.

Link - https://www.codechef.com/viewsolution/12947588

@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.

1. You can jump to (i+1)th position.

  This is equal to minimum of (dp[i+1],dp[i]+1).
  So, dp[i+1] = min(dp[i+1],dp[i]+1)
**2. You can jump to (i+p[i])th position**.
  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.

Link to my solution: ALGOA

When will the problems be moved to practice? I have to submit the code.
I can not find the problems in peer.

The question can be solved using level order traversal. First create a graph such that there is a link between i and (i+1) and i and (i+a[i]). But make sure that (i+a[i]<=N). Then run a bfs from the 0th node. Level[N] is the answer but there is some problem with the test cases. I made around 10 submissions. But my partner solved it without creating a graph. Like here there are only 2 edges so he pushed it onto a queue directly and that gave an AC. There is a problem in the TC. Don’t worry.

There’s no cin>>t in the above code, so that maybe the reason for assert error

I am not sure but i guess my approach has high complexity but the answer should be right.

You can refer to @black_well’s explanation. It is almost the same as what I did, except that the implementation is more efficient than mine.

I didn’t think much of updating the index i while iterating, since the small constraints in the problem wouldn’t have had much of an effect in either case.