DIGJUMP - Editorial

bfs
digjump
dijkstra
easy
editorial
june14

#61

@shiplu can you please check y my code is giving WA . thanks


#62

@vaibhavatul47
Why is ans 5…??
7 to 7(last 7) - 1
7 to 5(left) - 2
5 to 5(left) - 3
5 to 5(left) - 4
5 to 6(left) - 5
6 to 6(last) - 6

It cannot make a jump from ‘5’ at index 8 to ‘5’ at index 6 in 1 step because the problem states only (i-1) backwards.
Can you please explain…??


#63

Can someone explain me that in Sergey Nagin’s solution why are we iterating the loop 20 times . for (int it = 0; it < 20; it++)

I can understand that in each loop dp* gets updated and after some iterations we will get correct result . but how 20?


#64

i think the expected output should also be 6 and not 5. correct me if i m wrong(plzz provide the steps).


#65

indexes -> 0->6,6->5,5->24,24->23,23->29 i.e 3->3,3->7,7->7,7->9,9->9
These are the five steps.


#66

…But we can move to the same digit anywhere in the list. That is the main thing in this problem!


#67

@Praveen Dhinwa , can you please have a look at my code , looks like it is working for eacha nd every tes cases .


#68

@anisdube, your method of taking input is problematic.


#69

one more test case of later updating:-
72266886688661137700886699445511449955 ans=6 ex 7-7-3-1-1-5-5


#70

@dpraveen

I am trying to make it using BFS but I am not getting how the adjacency list of the graph will be generated.


#71

I tried again but still getting TLE. Someone pls help
solution lnk
https://www.codechef.com/viewsolution/10159123


#72

didn’t get vivek approach of advanced bfs as explained in editorial


#73

Those bfs observations were the key to solve this problem, feels good to finally realize that such small observations can make your code from N^2 to N.