DIGJUMP - Editorial

bfs
digjump
dijkstra
easy
editorial
june14

#41

Author’s solution link is broken


#42

Nice problem and an amazing tutorial. Lately there’s been a decline in the quality of editorials but this one was certainly one of the best.


#43

See “Another Easy Solution” section in the editorial.Your method is similar to what is described there.


#44

thanks a lot, I missed that part!


#45

@picpunk : I used the same algorithm as yours but I scanned it only thrice i.e. first from left to right and then from reverse and again finally from front . I got AC with this approach and did not scan multiple times as you said . I would like to get a test case for which my solution will get fail because the test cases are still weak IMHO.

Here’s the link to my solution : http://www.codechef.com/viewsolution/4100953


#46

For a reference implementation, see one of the solutions in the references. ???

Where are the references?? Or Can anyone point me the solution using bfs??


#47

@aayushagarwal, my solution gets AC if we scan the array 3 times as well. I’m also not sure if this AC is due to weak test cases though.


#48

@kmampent : But in the editorial it is mentioned that at most we have to do 20 iterations because the maximum value can be 20 , perhaps there can be a test case which I am not able to deduce now .


#49

indeed, it would be interesting to see if someone can find a test case where this method doesn’t work.


#50

beautiful solution, one of the best implementation of bfs


#51

Actually I don’t understand last test case :frowning:
My code output for this one(0123456754360123457) is 7…
Can anyone help me to understand this test case?

Thanks in advance :slight_smile:


#52

can u explain the last one?how can it be 5??


#53

for last case follow this path(indexes in bracket):
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) -> 7(18).


#54

@aayushagarwal: your code gives incorrect output for 348117304825225015142699765169, expected output is 5 and your solution gives 6.


#55

hi all
my code seems to be working for all the below test cases ,
94563214791026657896112 ans -> 4
12345178905 ans -> 3
112 ans -> 2
1112 ans -> 2
4589562452263697 ans -> 5
14511236478115 ans -> 2
0123456754360123457 ans -> 5

still it showed WA . any help is appreciated


#56

@vaibhavatul47 : Thank you for the test case !


#57

hey for “348117304825225015142699765169 . The expected output is 5” i am getting 5 also for this .
totally not sure why it is still saying WA


#58

@jony, I have updated the link.
@rishavz_sagar, Yes, you are right, Updated.


#59

see the updated pseudo code.
also see my accepted submission http://www.codechef.com/viewplaintext/4111204


#60

nice tutorial by dpraveen followed by crisp and self-explanatory implementation by vivek, makes it one of the bestest editorials.