DIGJUMP - Editorial

editorial
, , , , ,
61

@shiplu can you please check y my code is giving WA . thanks

62

@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…??

63

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?

64

i think the expected output should also be 6 and not 5. correct me if i m wrong(plzz provide the steps).

65

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.

2 Likes
66

…But we can move to the same digit anywhere in the list. That is the main thing in this problem!

67

@Praveen Dhinwa , can you please have a look at my code , looks like it is working for eacha nd every tes cases .

68

@anisdube, your method of taking input is problematic.

69

one more test case of later updating:-
72266886688661137700886699445511449955 ans=6 ex 7-7-3-1-1-5-5

70

@dpraveen

I am trying to make it using BFS but I am not getting how the adjacency list of the graph will be generated.

71

I tried again but still getting TLE. Someone pls help
solution lnk
https://www.codechef.com/viewsolution/10159123

72

didn’t get vivek approach of advanced bfs as explained in editorial

1 Like
73

Those bfs observations were the key to solve this problem, feels good to finally realize that such small observations can make your code from N^2 to N.

74

People using Python.
Use input().strip() while accepting string input as there are whitespaces in the input files I guess.
Wasted around 3 hours since I was getting WA. :confused:

2 Likes
75

I can you pls make me understand how we are optimizing bfs
here is my code : CodeChef: Practical coding for everyone

76

that dp solution in editorial is similar to Bellman-Ford

78

what’s wrong here ?

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int mxN = 1e5;
string s;
unordered_set adj[mxN];
vector adj2[mxN];
int dist[mxN];
bool vis[mxN];

void bfs(int srcPos) {
vis[srcPos] = 1;
dist[srcPos] = 0;
queue q;
q.push(srcPos);
while(q.size()) {
int curr = q.front();
q.pop();
for(int i = 0; i < (int)adj2[curr].size(); i++) {
if(vis[adj2[curr][i]] == 0) {
q.push(adj2[curr][i]);
dist[adj2[curr][i]] = dist[curr] + 1;
vis[adj2[curr][i]] = 1;
}
}
}
}

unordered_set getPos(int j, int val) {
unordered_set ans;
for(int i = 0; i < (int)s.length(); i++) {
if(((s[i] - ‘0’) == val) && (i != j)) {
ans.insert(i);
}
}
return ans;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> s;
int n = s.length();
if(s[0] == s[n - 1]) {
    cout << 1;
    return 0;
}
for(int i = 0; i < n; i++) {
    if((i+1) < n) {
        adj[i].insert(i+1);
        adj[i+1].insert(i);
    }
    if((i-1) >= 0) {
        adj[i].insert(i-1);
        adj[i-1].insert(i);
    }
    unordered_set<int> pos = getPos(i, s[i] - '0');
    for(int k : pos) {
        adj[i].insert(k);
        adj[k].insert(i);
    }
}
for(int i = 0; i < n; i++) {
    vector<int> z(adj[i].begin(), adj[i].end());
    adj2[i] = z;
}
memset(vis, 0, sizeof(vis));
memset(dist, -1, sizeof(dist));
bfs(0);
cout << dist[n - 1];

return 0;

}

80

This is a cool idea.

CA solution

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

81

Can u please check what’s wrong with my solution. I have implemented the bfs to find the shortest path @dpraveen

vector<int> adj[10];
vector<int> visited(100005,false);
vector<int> dist(100005,0);
int n;
string s;
int bfs() {
    queue<pair<int,int> > q;
    q.push({0,0});
    dist[0] = 0;
    while(!q.empty()) {
        int index = q.front().first, step = q.front().second;
        // cout << "index " << index << endl;
        q.pop();
        if(index == n-1){
            break;
        }
        char no = s[index];
        vector<int> v = adj[no-'0'];
        rep(i,0,v.size()) {
            if(i!= 0 and visited[v[i]]) continue;
            if(i != 0){
                dist[v[i]] = dist[v[0]] + 1;
                q.push({v[i],dist[v[i]]});
            }
            visited[v[i]] = true;
            if(v[i]-1>=0 and s[v[i]-1] != no and !visited[v[i]-1]){
                visited[v[i]-1] = true;
                dist[v[i]-1] = dist[v[i]] + 1;
                q.push({v[i]-1,dist[v[i]-1]});
            }
            if(v[i]+1 <n and s[v[i]+1] != no and !visited[v[i]+1]){
                visited[v[i]+1] = true;
                dist[v[i]+1] = dist[v[i]] + 1;
                q.push({v[i]+1, dist[v[i]+1]});
            }
        }
    }
    return dist[n-1];
}
void solve(){
    cin >> s;
    n = s.length();
    rep(i,0,n){
        adj[s[i]-'0'].pb(i);
    }
    cout << bfs() << endl;
}
int main() {
    FAST_FURIER;
    int tt=1;
    // cin >> tt;
    while(tt--){
        solve();
    
    }
}
Thanks in advance!!
82

Please post your entire code.