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)
3 Likes
Author’s solution link is broken
Nice problem and an amazing tutorial. Lately there’s been a decline in the quality of editorials but this one was certainly one of the best.
6 Likes
See “Another Easy Solution” section in the editorial.Your method is similar to what is described there.
1 Like
thanks a lot, I missed that part!
@picpunk : I used the same algorithm as yours but I scanned it only thrice i.e. first from left to right and then from reverse and again finally from front . I got AC with this approach and did not scan multiple times as you said . I would like to get a test case for which my solution will get fail because the test cases are still weak IMHO.
Here’s the link to my solution : http://www.codechef.com/viewsolution/4100953
2 Likes
For a reference implementation, see one of the solutions in the references. ???
Where are the references?? Or Can anyone point me the solution using bfs??
@aayushagarwal, my solution gets AC if we scan the array 3 times as well. I’m also not sure if this AC is due to weak test cases though.
1 Like
@kmampent : But in the editorial it is mentioned that at most we have to do 20 iterations because the maximum value can be 20 , perhaps there can be a test case which I am not able to deduce now .
indeed, it would be interesting to see if someone can find a test case where this method doesn’t work.
beautiful solution, one of the best implementation of bfs
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;
}
Actually I don’t understand last test case 
My code output for this one(0123456754360123457) is 7…
Can anyone help me to understand this test case?
Thanks in advance 
1 Like
can u explain the last one?how can it be 5??
for last case follow this path(indexes in bracket):
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) -> 7(18).
1 Like
@aayushagarwal: your code gives incorrect output for 348117304825225015142699765169, expected output is 5 and your solution gives 6.
1 Like
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
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 .
8 Likes