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
hey for “348117304825225015142699765169 . The expected output is 5” i am getting 5 also for this .
totally not sure why it is still saying WA
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
see the updated pseudo code.
also see my accepted submission http://www.codechef.com/viewplaintext/4111204
nice tutorial by dpraveen followed by crisp and self-explanatory implementation by vivek, makes it one of the bestest editorials.
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]);
}
@vaibhavatul47
Why is ans 5…??
7 to 7(last 7) - 1
7 to 5(left) - 2
5 to 5(left) - 3
5 to 5(left) - 4
5 to 6(left) - 5
6 to 6(last) - 6
It cannot make a jump from ‘5’ at index 8 to ‘5’ at index 6 in 1 step because the problem states only (i-1) backwards.
Can you please explain…??
Can someone explain me that in Sergey Nagin’s solution why are we iterating the loop 20 times . for (int it = 0; it < 20; it++)
I can understand that in each loop dp[i] gets updated and after some iterations we will get correct result . but how 20?
i think the expected answer should also be 6 not 5.
correct me if i m wrong(plzz write the steps)
i think the expected output should also be 6 and not 5. correct me if i m wrong(plzz provide the steps).
indexes -> 0->6,6->5,5->24,24->23,23->29 i.e 3->3,3->7,7->7,7->9,9->9
These are the five 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.
…But we can move to the same digit anywhere in the list. That is the main thing in this problem!
@Praveen Dhinwa , can you please have a look at my code , looks like it is working for eacha nd every tes cases .
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;
}