Author’s solution link is broken. http://www.codechef.com/download/Solutions/2014/June/Setter/DIGJUMP.cpp
Please fix the link.
We can solve it using a Dijkstra too without relying on the fact that the solution would be bounded by 20. Instead of interconnecting all nodes with the same digit value resulting in potentially ~V^2 edges, we create one super node for each digit from 0 to 9, and connect each digit with its corresponding super node with an edge of weight 0.5. We can thus move to and from same digit nodes in distance 1, which was exactly what was required. This results in ~V edges and we can run Dijkstra on the first node in VlogV time. Finally we can double all edge lengths to avoid floating points and divide the required distance by 2 at the end.
16 Likes
If you are finding “Wrong Answer” then try following testcase :-
0998887776665554443322223300885577
Correct Ans --> 5
Directions : 0,0(last occurrence),8(next),8(index:5),7(next),7(last)
6 Likes
I tried the DP thing, iterating over it and making it better, made a lot of submissions in the process. Here is my last one I tried:
from __future__ import division
def read_mapped(func=lambda x:x):
return map(func, raw_input().strip().split(" "))
def read_int():
return int(raw_input().strip())
def read_str():
return raw_input().strip()
def read_float():
return float(raw_input().strip())
s = map(int, list(read_str()))
lim = len(s)-1
dp = [-1 for _ in xrange(lim+1)]
dp[0] = 0
from collections import defaultdict
dpa = [10**10 for i in xrange(11)]
dpa[s[0]] = 0
for i in xrange(1, lim+1):
minn = dpa[s[i]]
dp[i] = min(minn, dp[i-1])+1
dpa[s[i]] = min(dpa[s[i]]+1, dp[i])
for _ in xrange(19):
dpa = [10**10 for i in xrange(11)]
dpa[s[0]] = 0
for i in xrange(1, lim+1):
minn = dpa[s[i]]
dp[i] = min(minn, dp[i-1], dp[i+1] if i!=lim else 10**10)+1
dpa[s[i]] = min(dpa[s[i]]+1, dp[i])
print dp[-1]
But it gives me a WA. Why is it so?
Edit
I tried chanakya’s input and it gives me 8 as answer instead of 3. I can’t figure out why. 
Input:
0998887776665554443322223300885577
Output:
8
Can anyone tell me what i am commiting mistake in my code…
#include<bits/stdc++.h>
using namespace std;
string str;
int a[10][10],flag[10];
void distance_matrix()
{
int i,j;
for(i=0;i<str.size();i++)
{
if(i==0)
{
a[str[i]-‘0’][str[i+1]-‘0’]=1;
a[str[i]-‘0’][str[i]-‘0’]=0;
flag[str[i]-‘0’]=1;
}
else if(i==str.size()-1)
{
if(flag[str[i]-‘0’]==1)
{
a[str[i]-‘0’][str[i]-‘0’]=1;
a[str[i]-‘0’][str[i-1]-‘0’]=min(2,a[str[i]-‘0’][str[i-1]-‘0’]);
}
else
{
a[str[i]-‘0’][str[i]-‘0’]=0;
a[str[i]-‘0’][str[i-1]-‘0’]=1;
flag[str[i]-‘0’]=1;
}
}
else
{
if(flag[str[i]-‘0’]==1)
{
a[str[i]-‘0’][str[i]-‘0’]=1;
a[str[i]-‘0’][str[i+1]-‘0’]=min(2,a[str[i]-‘0’][str[i+1]-‘0’]);
a[str[i]-‘0’][str[i-1]-‘0’]=min(2,a[str[i]-‘0’][str[i-1]-‘0’]);
}
else
{
a[str[i]-‘0’][str[i]-‘0’]=0;
a[str[i]-‘0’][str[i+1]-‘0’]=1;
a[str[i]-‘0’][str[i-1]-‘0’]=1;
flag[str[i]-‘0’]=1;
}
}
}
/for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
cout<<a[i][j]<<" ";
cout<<endl;
}/
}
int main()
{
//freopen(“in.txt”,“r”,stdin);
//freopen(“out.txt”,“w”,stdout);
int n,i,j,k;
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
a[i][j]=INT_MAX/2;
flag[i]=0;
}
cin>>str;
if(str.size()==1)
{
cout<<“0”<<endl;
return 0;
}
distance_matrix();
int visit[10],distance[10];
for(i=0;i<10;i++)
{
visit[i]=0;
distance[i]=INT_MAX/2;
}
visit[str[0]-‘0’]=1;
for(i=0;i<10;i++)
{
distance[i]=a[str[0]-‘0’][i];
}
distance[str[0]-‘0’]=0;
/for(i=0;i<10;i++)
{
cout<<visit[i]<<" “;
}cout<<endl;
for(i=0;i<10;i++)
{
cout<<distance[i]<<” “;
}
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
cout<<a[i][j]<<” ";
cout<<endl;
}/
for(i=0;i<10;i++)
{
int min_dis=INT_MAX/2,index;
for(j=0;j<10;j++)
{
if(visit[j]==0&&distance[j]<=min_dis)
{
min_dis=distance[j];
index=j;
}
}
visit[index]=1;
for(j=0;j<10;j++)
{
if(visit[j]==0)
{
distance[j]=min(distance[j],min_dis+a[index][j]);
}
}
}
/for(i=0;i<10;i++)
{
cout<<visit[i]<<" “;
}cout<<endl;
for(i=0;i<10;i++)
{
cout<<distance[i]+a[i][i]<<” ";
}/
cout<<distance[str[str.size()-1]-‘0’]+a[str[str.size()-1]-‘0’][str[str.size()-1]-‘0’]<<endl;
return 0;
}
Well the test cases for this problem are still weak . Here is my accepted solution . My code fails on this 348117304825225015142699765169 . The expected output is 5 whereas my code gives 6
as the answer . I was almost half sure whether my solution would pass or not but luckily it passed . Its really difficult to make tricky test cases which can fail wrong solutions . I would request the setter to update the test cases for this problem in the practice section if possible .
11 Likes
i have checked all the test cases given here for each one my code is giving correct output.
can any one tell me for which test case it got failed.@admin…I think for this problem it will be helpful for many of us if test cases used for evaluation be made public.
thanks
3 Likes
http://www.codechef.com/viewsolution/4050931
Can someone check my this code. it is showing run time error. but in my compiler it is providing me with all correct answers. help would be appreciated.
I am not able to understand under the heading “Another Easy Solution” DP.
Pseudo Code is not working for me but using the idea I solved the problem.
So i change the code for moving from position 0 to n-1 .(rather than from 1 to n).
dp[0]=0 ;
dp1 =1;
Answer is given by dp[n-1]
My Solution link is http://www.codechef.com/viewsolution/4110410
I’ve used a solution similar to the one by Sergey Nagin.
I have, however, used 10 iterations instead of 20. I got AC which could be due to weak test cases.
Can someone please give a test case that shows the possible mistake in my code?
Or is it actually possible to do it in 10 and not 20 iterations?
The following arrays in my code have the following meaning as in the pseudo code by Sergin.
val[i] - dp[i] (stores minimum no of moves to reach this point)
minval[i] - Q[i] (stores minimum no of moves to reach the number i)
#include<stdio.h>
#include<string.h>
int main()
{
int i,n;
char str[100000];
int minval[10],val[100001];
scanf("%s",str);
n = strlen(str);
val[0]=0;
val[n]=20000;
for(i=0;i<n;i++) str[i]=str[i]-48;
for(i=0;i<10;i++) minval[i]=20;
minval[str[0]]=0;
for(i=0;i<n;i++)
{
if(i!=0)
{
if(val[i-1]<=minval[str[i]])
{
val[i]=val[i-1]+1;
}
else
{
val[i]=minval[str[i]]+1;
}
if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
}
if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
}
int j;
for(j=0;j<10;j++)
{
for(i=0;i<n;i++)
{
if( i!=0)
{
if(val[i-1]<minval[str[i]]&&val[i-1]<val[i+1])
{
val[i]=val[i-1]+1;
}
else if(val[i+1]<minval[str[i]]&&val[i+1]<val[i-1])
{
val[i]=val[i+1]+1;
}
else
{
val[i]=minval[str[i]]+1;
}
if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
}
if(minval[str[i]]>val[i]) minval[str[i]]=val[i];
}
}
printf("%d\n",val[n-1]);
}
i think the expected answer should also be 6 not 5.
correct me if i m wrong(plzz write the steps)
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 
Any help ?
Here’s my code :
http://www.codechef.com/viewsolution/4097046
I’m getting tle. 
Can plz anyone help me …?
#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]);
}
}
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.