Great Observations. Used BFS for this question. i wish, if i had thought of this bfs optimisation before. great question
1 Like
I used O(2^8*8!), cause was not able to come up with easier approach. omg ))
My solution was accepted and uses dynamic programming. However because the solution is based on my intuition I’m not sure if understand whether or why it’s 100% correct.
let dp[i] represent the minimum amount of steps in order to reach position i of the input array. We want to find dp[N-1].
let nums be an array of size 10 where nums[i] represents the minimum amount of moves that are needed in order to reach number i. Note that this number can exist anywhere in the array.
Now we have to scan the array from left to right and then from right to left as many times as needed in order to calculate the final value for dp[N-1]. We stop scanning the array when the values of dp aren’t changed from a single scan (left->right, right->left).
Initialization
all values of dp and nums to INF
dp[0] = 0
nums[number of input[0]] = 0
First we scan it from left to right.
dp[i] = min(dp[i], dp[i-1]+1, nums[number of input[i]]+1)
then we scan the array from right to left:
dp[i] = min(dp[i], dp[i+1]+1, nums[number of input[i]]+1)
then again from left to right, right to left etc, until nothing changes in the array dp.
Basically I assume that the convergence to a solution is fast, however I have yet to think of a proof to this.
6 Likes
Hi All
I used the BFS and dijsktra approach to solve the problem . It is working fine for all cases mentined above .Please have a look at it and would be grateful to let me know whch testcases it failed . Thanks 
1 Like
Can anyone tell me what is wring with this code, it gives wrong answer on submission, but is working fine on my system for every possible input i can think of. I am not able to find the type of input for which it can give a wrong answer.
Who are getting WA can have the following cases :
94563214791026657896112 ans -> 4
12345178905 ans -> 3
112 ans -> 2
1112 ans -> 2
4589562452263697 ans -> 5
14511236478115 ans -> 2
0123456754360123457 ans -> 5
14 Likes
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;
}