DIGJUMP - Editorial

editorial
, , , , ,
61

I have applied the same logic as given in the Optimized BFS solution and I have tested my program for all the test cases, including the ones given in the comments above. Still it gives wrong answer.

here is the link to my solution:
http://www.codechef.com/viewsolution/5358955

Plz help.

62

Can anyone explain me how to solve this problem using BFS? I am not able to understand how to use BFS on this problem.

63

can someone explain me the implementation of optimization part of Vivekā€™s solution ???

64

Well, my line of reasoning for ā€œAnother easy solutionā€ was different.
Think in terms of forward jump and backward jump.
If there is only forward jumps , then


    for(i=1;i<len;++i)
    {
    	dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1);//min[] equivalent to Q[] in editorial
    	min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]);
    }

is enough to find dp[n-1].

If there is only one backward jump in the final answer , then we need to run the above code , one more time now considering , dp[i+1]+1 also, i.e.



for(i=1;i<len;++i)
{
	if(i==len-1)
		dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1);
	else
		dp[i] = Min(Min(dp[i-1]+1, dp[i+1]+1) ,min[str[i]-'0']+1);
	min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]);
							
}

If there are ā€˜bā€™ backward jumps in total , then we need to run the above code ā€˜bā€™ times. So max is the maximum backward jumps that we can make ?

We know that any minimum moves will not exceed 20. So , that is the bound on backward jumps also.
So ,


dp[0]=0;
min[str[0]-'0']=0;
for(j=1;j<=20;++j)
{
	for(i=1;i<len;++i)
	{
		if(i==len-1)
			dp[i] = Min(dp[i-1]+1 ,min[str[i]-'0']+1);
		else
 			dp[i] = Min(Min(dp[i-1]+1, dp[i+1]+1) ,min[str[i]-'0']+1);
		min[str[i]-'0']=Min(min[str[i]-'0'],dp[i]);
	}
		
}
65

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

66

@dpraveen

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

67

can anyone please tell me why my answer is a tle
https://www.codechef.com/viewsolution/9705925

68

I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.

69

I thought of modelling the problem into graph and then doing a simple bfs to get the correct number of jumps .I tried modelling the problem into graph and since the indices with same character has also an edge, it takes me O(n^2) to model these edges.This gives me TLE. Help me to tackle this problem.

70

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

71

Hi !!
My code is showing correct output on all the cases mentioned at any point above.

Here it is :-
https://hastebin.com/uhiwezozat.py

Unfortunately, it is showing Wrong Answer. Can anyone please help me with a Test Case or suggestions ?

Thanks.

72

didnā€™t get vivek approach of advanced bfs as explained in editorial