DIGJUMP - Editorial

For people whose program is passing all the test cases given by the question as well as other users

Check whether ur program works for inputs such as

00112233445566778899 - 19

445566 - 5

001122 - 5

22445599 - 7

I had the same issue and my program was accepted once i rectified this.

My code passes all the test cases provided above in the comments but I still get WA when submitting :confused: Any help ?
Here’s my code :
http://www.codechef.com/viewsolution/4097046

I’m getting tle. :frowning:
Can plz anyone help me …?

#include

#include

#include
using namespace std;
#define MAX 1000000
#define for(i,n) for( i=0;i<n;i++)

vector< int > v[10];
#define initial 1
#define waiting 2
#define visited 3
#define NIL -1
queue buff;

int main()
{

char s[MAX];

cin>>s;

int n,i,val;

n=strlen(s);

for(i,n)

{  val=s[i]-48;

 v[val].push_back(i);
   }

int state[n];

int pre[n];

for(i,n)
{
state[i]=initial;
pre[i]=-1;
}
int pt,st;

buff.push(0);

vector< int > :: iterator p;

while(!buff.empty())
{
pt=buff.front();
if(pt==n-1)
break;

                st=s[pt]-48;
               
                state[buff.front()]=waiting;
                  //cout<<v[pt].front()<<v[pt].size()<<endl;
               
                
                p=v[st].begin();
                
                
                while(p!=v[st].end())
                {
                                  
                if(state[*p]==initial)                     
               { state[*p]=waiting;
                pre[*p]=pt;
              
                buff.push(*p);}
                
                p++;
                }
                
                
                
               if(  (pt+1< n)&& (state[pt+1]==initial))
              { state[buff.front()+1]=waiting;
               pre[buff.front()+1]=pt;
               buff.push(buff.front()+1);}
               
               
                if((0<  pt-1 )&& (state[pt-1]==initial) )
              { state[buff.front()-1]=waiting;
               pre[buff.front()-1]=pt;
               buff.push(pt-1);}
               
               
               state[pt]=visited;
                buff.pop();
                
               
                 
                
               
               
                }

int sd=0;
int v=n-1;
while(v!=0)
{
v=pre[v];
sd++;

       }

cout<<sd;

return 0;
}

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.

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

can someone explain me the implementation of optimization part of Vivek’s solution ???

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]);
	}
		
}

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

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.

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.

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.

Shouldn’t the maximum number of moves be 19?

5 Likes

can you check your output on this input 023564101237894 ???
Correct answer is 4.

my solution is below can i know for which test case/cases it went wrong please…

check your output for: 248612676
Ans should be 3.

I’m unable to access Author’s solution, It is saying access denied.

1 Like

found why is the answer wrong
For anyone else who is wondering:
The I/p 248612676
answer should be 3

how could the value of i start from 0 during updating dp[i]?I think the value of i should start from 1 in sereja psudo code.

7711965557423006
ur o/p: 6, correct o/p: 5

1 Like

Author’s solution link is broken