DIGJUMP - Editorial

editorial
, , , , ,
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.

6 Likes
43

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

1 Like
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 : CodeChef: Practical coding for everyone

2 Likes
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.

1 Like
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:

1 Like
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).

1 Like
54

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

1 Like
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.