Please help me with this problem: Chef and Digit Jump

I was solving this question: http://www.codechef.com/problems/DIGJUMP

I used Dijkstra but it is showing TLE. I have been trying to solve this, but was unable to. Can anyone help me finding an issue in this code? Help will be highly appreciated😃
You can see the code on this ideone link too.
TIZ8TF - Online C++ Compiler & Debugging Tool - Ideone.com

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
#define FAST_FURIER ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
#define ppb pop_back
#define mk make_pair
#define sorta(v)            sort(v.begin(), v.end())
#define sortd(v)            sort(v.begin(), v.end(), comp)
#define rep(i,a,N)          for(ll i=a;i<N;i++)
#define rrep(i,a,N)         for(ll i=a;i>N;i--)
#define print(v)            for(ll ite=0;ite<v.size();ite++){cout<<v[ite]<<' ';}cout<<endl;
#define M 1000000007
bool comp(ll x,ll y)
{
    return x > y;
}
 
/*..............................code starts here........................*/
// C is first won in M
vector<int> adj[10];
vector<int> visited(100005,0);
vector<int> dist(100005,1e8);
int n;
string s;
int dijkstra() {
    set<pair<int,int> > q;
    q.insert(mk(0,0));
    dist[0] = 0;
    while(!q.empty()) {
        int index = (*q.begin()).second; q.erase(q.begin());
        visited[index] = 1;
        for(int node: adj[s[index]-'0']){
            if(!visited[node])
            if(dist[index]+1 < dist[node]) {
                dist[node] = dist[index] + 1;
                q.insert(mk(dist[node], node));
            }
            if(node-1 >= 0 and !visited[node-1] and dist[node]+1 < dist[node-1]){
                dist[node-1] = dist[node]+1;
                q.insert(mk(dist[node-1], node -1));
            }
            if(node+1 < n and !visited[node+1] and dist[node]+1 < dist[node+1]){
                dist[node+1] = dist[node]+1;
                q.insert(mk(dist[node+1], node+1));
            }
        }
    }
    return dist[n-1];
}
void solve(){
    cin >> s;
    n = s.length();
    rep(i,0,n){
        adj[s[i]-'0'].pb(i);
    }
    cout << dijkstra() << endl;
}
int main() {
    FAST_FURIER;
    int tt=1;
    // cin >> tt;
    while(tt--){
        solve();
    
    }
}
 

Consider the following test input:

http://vps2.etotheipiplusone.com:30176/public_html/codechef/chef-and-digit-jumps-testcase-large.txt

Besides TLE, you seem to be getting the wrong answer for this:

2754201408
2 Likes

can u please help me in optimizing?? And, what’s the answer for the given TC.

For this test case, 2754201408, I think 4 will be the answer.

Using 0 based indexing, the shortest path is

0 -> 4 -> 5 -> 8 -> 9 (Index based path), or
2 -> 2 -> 0 -> 0 -> 8 (values based path).

Since you’re taking 4 steps, the answer is 4. I hope this is the answer to the above test case.

2 Likes

Check the following implementation.

https://www.codechef.com/viewsolution/43931971

Can u please explain the logic behind your implementation?? I am unable to derive some conclusion from your code!!

Sure, breadth-first search is used to find the shortest distance between the source digit at position 0 and the destination digit at position N-1 in the given string S. Associated with each position (i) S is a state which is a decimal number between 0 and 9. The index vector stores for each value s between 0 and 9 the positions in S whose state is equal to s. The d_min vector stores for each position between 0 and N-1 the minimum number of jumps to reach such position. Initially, d_min[0] = 0 and d_min[pos] = INT_MAX in all other positions. Queue-based breadth-first search is then applied. Initially, the source position 0 is pushed to the queue. Then, while the queue is not empty, its front element (u) is popped. It the d_min[u] >= d_min[N-1], then no further improvement to the optimal answer is possible by jumping from u to any other position. Otherwise, the four possible moves: 1. jumping to the destination position if S[u] = S[N-1], 2. to the left neighbor l = u-1 where l >= 0, 3. to the right neighbor r = u+1 where r < N, and 4. to another position (i) where S[i] = S[u] using the index array, are checked, and the next position is pushed to the queue if jumping from u to it leads to number of jumps that is less than the present minimum number of jumps to such position. After the breadth-first search is completed, the minimum number of jumps to reach the destination position is d_min[N-1]. The boolean vector visited is used such that the fourth type of jumps is check only once for each decimal digit. Check the updated link for slightly shorter implementation.

Try this one:

https://www.codechef.com/viewsolution/36122214