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.

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?

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.

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