DIGJUMP - Editorial

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

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[i] 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.

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