Approach for UnderTheTunnels from Jan Lunctime 2020?

I solved it using BFS+DP

Anyother interesting approaches?


Can you explain me the question well? I didn’t quite understand it :slight_smile:

I used BFS (N^2) but i TLEd on the last test case. Was there a better solution?

My bfs didn’t work…can u tell me why?

I used Dijkstra’s (N^2logN) which still passed. Probably there is a bug in your BFS.

My BFS took O(N^2).

Basically I started with,

  1. Those who can reach N directly and then marked their state = 1 (because of direct jump) and put “Those” in queue.
  2. Then do bottom-up approach using BFS-queue by parsing all levels.

Only append the edges where abs(i-j)<=k. Then it won’t tle


I got tle in the last three cases. What’s the issue??

Assume virtually there is N tiles.
Say, N = 6
111111 (current state) --> A

Now when you step on tile 3, then switch 3 get’s activated. Now, switch 3 ka configuration is

Then current state A -> changes to 101010. So, now you can only step on 1, 3, 5 tiles and activate those switches and move to any one of them.

and so-on

1 Like

correct. I handled this :slight_smile:

Okay getting a bit of idea…i got very confused in the middle of it and focused all my time on D question

1 Like

I spent almost 45 minutes only on understanding the question because I had a rough day


I don’t know why the problem statements weren’t clear. I myself read them multiple times and found them perfectly fine.
Also, I expected a much higher number of AC’s in this problem. Donno why the problem caused so many problems.

The intended solution was DFS. Imagine the N tiles as N nodes in a graph. An directed edge between node u and v exists only if it’s possible to jump to tile v from tile u.
We can calculate the edges in the graph by iterating over every switch and this has complexity O(N^2).

Finally, run a DFS on the graph, starting from node 1 (assuming 1 based indexing) and determine the minimum jumps required to reach node N.

This is my solution

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int main(){

    int T; cin >> T;
        int N, K; cin >> N >> K;
        vvi Adj(N);

        for(int n = 0; n < N; n++){
            for(int i = 0; i < N; i++){
                char c; cin >> c;
                if(c == '0' or n == i) continue;
                if(abs(n - i) <= K) Adj[n].push_back(i);

        vi Dist(N, -1); Dist[0] = 0;
        queue<int> Q; Q.push(0);

            int u = Q.front(); Q.pop();
            for(auto i : Adj[u]){
                if(Dist[i] != -1) continue;
                Dist[i] = Dist[u] + 1;
        cout << Dist[N - 1] << endl;

    return 0;

I did with BFS and maintaing distance array.
You can check my code here:

You can first make the adjacency list of the graph where node I is connected to j if state i has jth cell active within kth jump. Then after making the list just simple bfs to calculate the shortest distance would suffice.

Can somebody please look at my code and tell me why it TLEd? Thanks in advance.

Yes, I too solved exactly similar to your code.

1 Like

I am not saying question was hard to understand, but I am dumb ;_;.
I got lost in middle of the statements which if i read with a clearer and fresh mind will make sense to me i hope!
I wasted all the energy on solving D question.
It’s a nice question though! :smiley:


The constraints said that n^2 does not exceed 10^6…So it must pass if your logic is n^2…