CHEF AND DIGIT JUMP JUNE 2014 CHALLENGE ??

I AM A BEGINNER.PLEASE EXPLAIN ME SOLUTION OF THIS PROBLEM “CHEF AND DIGIT JUMP JUNE 2014”.
WHAT APPROACH IS USED AND WHICH TYPE OF ALGORITHM CAN USED TO SOLVE THESE TYPE OF PROBLEM.

you will have to think this problem from graph point of view where there are edges from an index to another where one can jump (here to i-1,i+1 and all points having same value as that of arr[i]). after this you have to find shortest path from index 0 to n-1.
This can be done by djikstra but since all edge weights are 1 you can perform bfs traversal.

1 Like

you can look at this EDITORIAL for detailed explanation and algorithm used to solve the problem and you cam look at editorials for any contest problem you want but before looking at editorials i suggest you to try the problem as many times as you can because it will increase your thinking level in solving problem and optimizing levels. :stuck_out_tongue:

3 Likes