# DIGJUMP - Editorial

Editorialist: Praveen Dhinwa

Easy

bfs, dijkstra

### PROBLEM:

Given a string s of N. You have to go from start of the string(index 0) to the end of the string (index N - 1).
From position i, you can go to next (i + 1) or previous (i - 1) position. You can also move from the current position to the indices where the
character is same as current character s[i].

### QUICK EXPLANATION

• Minimum number of operations can not be greater than 19.
• By your moves, you will never be visiting a single digit more than twice.
• You can solve this problem by a modified bfs.
• You can also make use of simple dijkstra’s algorithm.

### EXPLANATION

Few observations

• Minimum number of operations can not be greater than 19.
Proof:
You can start from first position and go to rightmost index where you can directly go.
Then from that position go to next position and keep repeating the previous step.
Note that you will be visiting a single number at most twice. Hence you can at most make 19 moves because first digit will be visited once.

They will 19 in the cases of 001122334455667788999.

• By your moves, you will never be visiting a single digit more than twice.
Proof:
If you are using more than 2 moves for going from a digit to another, you can simply reduce one of the move by simply going from
one of the position to other in just a single move. So you can simply keep the at most 2 moves for moving from a digit to another.

Wrong greedy strategies
Let us first discuss about some greedy strategies and figure out the reason why they are wrong.

From the current position, go to the rightmost index having same character/digit as the current character/digit.
If this number does not occur again in the right part of array, then go to next position (ie. i + 1).

Please see the following recursive implementation of this strategy.

Pseudo Code

``````def greedy(int cur):
// cur = N denotes end/ target position.
if (cur = N) return 0;
last = cur + 1;
for i = cur + 1 to N:
if (s[i] == s[pos]):
last = i;
return 1 + greedy(cur);
``````

The above strategy will fail in these kind of cases:
010000561
According to greedy strategy, From 0, you will go to rightmost 0, then from that position to 5, then to 6 and finally you will go to 1.
Total number of operations required are 4.
But you can do it in simply 2 operations. Go from 0 to 1 and then go to rightmost 1 (target position).

Wrong dp algorithm
Some contestants have used wrong dp algorithm. Let dp[i] denote the minimum number of moves needed to reach position i from position 0.
Some wre considering the transition from (i - 1) th position to i or
from some position j < i (such that digit at j is same as digit at i.) to i.

Note that this kind of dp solutions are wrong because they don’t consider the moves going backwards (from position i to i - 1), they are only
considering the forward moves.

A simple test case where they will fail.
In the case: 02356401237894, dp program will give answer 6, but we can go from position 0 to 6 and then to 4 on the left side of
second 0 (backward move) and then directly go to 4.
So total number of operations required are 3.

Bfs Solution
Now consider the movement operations from one position to other to be edges of the graph and indices of the string as nodes of the graphs.
Finding minimum number of operations to reach from 0 to N - 1 is equivalent to finding shortest path in the graph above mentioned. As
the weights in the give graph are unit weights, we can use bfs instead of using dijkstra’s algorithm.

So we can simply do a bfs from our start node(index 0) to end node(index n - 1).
Number of nodes in the graph are n, but the number of edges could
potentially go up to N 2 (Consider the case of all 0’s, entire graph is a complete graph.).

Optimized bfs Solution
Now we will make use of the 2 observations that we have made in the starting and we will update the bfs solution accordingly.
Whenever you visit a vertex i such that then you should also visit all the the indices j such that s[j] = s[i] (this follows directly
from observation 2). Now you can make sure to not to push any of the indices having digit same as current digit because according to observation 2,
we are never going to make more than 2 moves from a position to another position with same digit, So after adding that the current character, you should make sure that you are never going to visit any vertex with same value as s[i].

For a reference implementation, see Vivek’s solution.

Another Easy solution
Credit for the solution goes to Sergey Nagin(Sereja).

Let dp[i] denote the number of steps required to go from position 0 to position i.
From the previous observations, we know that we wont need more than 20 steps.
So lets make 20 iterations.

Before starting all the iterations, we will set dp = 0 and dp[i] = infinity for all other i > 1.
On each iteration, we will calculate Q[k] where Q[k] is the minimum value of dp[i] such that s[i] = k.
ie. Q[k] denotes the minimum value of dp over the positions where the digit is equal to k.

We can update the dp by following method.
dp[i] = min(dp[i], dp[i - 1] + 1, dp[i + 1] + 1, Q[s[i]] + 1);

Here the term dp[i - 1] + 1 denotes that we have come from previous position ie (i - 1).
Here the term dp[i + 1] + 1 denotes that we have come from next position ie (i + 1).
The term Q[s[i]] + 1 denotes the minimum number of operations needed to come from a position with same digit as the current i th digit.

Pseudo code:

``````// initialization phase.
dp = 0;
for (int i = 2; i <= N; i++) dp[i] = inf;
for (int it = 0; it < 20; i++) {
// Compute Q[k]
for (int k = 0; k < 10; k++)
Q[k] = inf;
for (int i = 1; i <= n; i++) {
Q[s[i] - '0'] = min(Q[s[i] - '0'], dp[i]);
}
// Update the current iteration.
for (int i = 1; i <= n; i++) {
dp[i] = min(dp[i], dp[i - 1] + 1, dp[i + 1] + 1, Q[s[i] - '0'] + 1);
}
}
// dp[n] will be our answer.
``````

Proof
If you done proof of dijkstra’s algorithm, you can simply found equivalence between the two proofs.

Complexity:
Complexity is O(20 * N). Here 20 is max number of iterations.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution

50 Likes

Shouldn’t the maximum number of moves be 19?

5 Likes

what is wrong with my this DP solution its giving correct answer for 02356401237894 (3)

#include<stdio.h>
#define min(a,b) a<b?a:b
#define int_max 1000000
int main()
{
int jump;

``````char num;

scanf("%s",num);

int i;

jump = 0;

for(i=0;i<100004;i++)
jump[i] = 1000000;
jump = 0;
for(i=1;num[i] != '\0';i++)
{
int j = 0;
//   jump[i] = 1000000;
while(j<i)
{
if( ( i == j+1 || num[i] == num[j]  ))
{
if(jump[i] > jump[j] + 1)
jump[i] = jump[j] + 1;

break;
}

j = j+1;
}
if( jump[i-1]  > jump[i] + 1)
jump[i-1] = jump[i] + 1;
if(jump[i+1] != '\0' && jump[i+1] > jump[i] + 1)
jump[i+1] = jump[i] + 1;
//     printf("%d",j);
}
printf("%d\n",jump[i-1]);
return 0;
``````

}

can you check your output on this input 023564101237894 ???

Can you explain what is wrong with my dp solution. It gave right answer for your test case. I have implemented the dp such that it considers going backwards.

using namespace std;

int main() {
int dp;
string s;
cin>>s;
int len = s.size();
//cout<<s.size()<<endl;
int mini;
memset(mini,-1,sizeof(mini));
for(int i=0;i<len;i++)
dp[i] = 100005;

``````dp = 0;
mini[s-'0']=0;
int curMin,j;
for(int i=1;i<len;i++)
{
if(mini[s[i]-'0']==-1)
mini[s[i]-'0']=i;

curMin = dp[mini[s[i]-'0']];
dp[i] = min(dp[i-1]+1, curMin+1);
if(dp[i] < dp[mini[s[i]-'0']])
mini[s[i]-'0'] = i;

j=i;
while((dp[j-1] > (dp[j]+1))&&(j!=(len-1)))
{
dp[j-1] = dp[j]+1;
if(dp[j-1] < dp[mini[s[j-1]-'0']])
mini[s[j-1]-'0'] = (j-1);
j--;
}
}
/*
cout<<endl;

cout<<mini<<endl;*/
/*for(int i=0;i<len;i++)
cout<<dp[i];
cout<<endl;*/
cout<<dp[len-1];
return 0;
``````

}

Please it will be great if someone can explain to me my mistake here. My approach is similar to Sergey’s approach. My mini array does the same thing that the Q array does in his code

2 Likes

my solution is below can i know for which test case/cases it went wrong please…

Can someone point out the bug in my Greedy problem as well, it gives me WA.
Thanks in advance ``````#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;
struct intint
{
int number;
int start;
int end;
int jump;
};

bool compareJumps(intint a,intint b) { return (a.jump > b.jump); }

bool isCompatible(vector<intint> baseVector, intint toCheck)
{
for(int i=0;i<baseVector.size();i++)
{
if((toCheck.start < baseVector[i].start) && (toCheck.end < baseVector[i].start))
{}
else if((toCheck.start > baseVector[i].end) && (toCheck.end > baseVector[i].end))
{}
else
{
return false;
}
}
return true;
}

int main()
{
string S;
cin>>S;
vector<intint> max;
for(int i=0;i<10;i++)
{
intint temp;
temp.number = i;
temp.jump = -1;
temp.start = -1;
temp.end = -1;
max.push_back(temp);
}
for(int i=0;i<S.length();i++)
{
int number = S[i] - 48;
if(max[number].start == -1)
{
max[number].start = i;
//max[number].jump = 0;
}
else
{
max[number].end = i;
max[number].jump = i - max[number].start;
}
}
sort(max.begin(),max.end(),compareJumps);
vector<intint> jumpsTaken;
for(int i=0;i<max.size();i++)
{
if((max[i].jump > 0)&&(isCompatible(jumpsTaken,max[i])))
{
jumpsTaken.push_back(max[i]);
}
}
int path = S.length() - 1;
for(int i=0;i<jumpsTaken.size();i++)
{
path = path - jumpsTaken[i].jump + 1;
}
cout<<path;
return 0;
}``````

Great Observations. Used BFS for this question. i wish, if i had thought of this bfs optimisation before. great question

1 Like

Ans should be 3.

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
``````
``````nums[number of input] = 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 http://www.codechef.com/viewsolution/4092676

1 Like

1 Like

found why is the answer wrong
For anyone else who is wondering:
The I/p 248612676

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.

http://www.codechef.com/viewsolution/4105903

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

12 Likes