# Approach for UnderTheTunnels from Jan Lunctime 2020?

I solved it using BFS+DP

Anyother interesting approaches?

2 Likes

Can you explain me the question well? I didnâ€™t quite understand it

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?
https://www.codechef.com/viewsolution/29184257

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

2 Likes

I got tle in the last three cases. Whatâ€™s the issue??

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

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
101010,

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

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

2 Likes

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

``````#include<bits/stdc++.h>
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(){
ios::sync_with_stdio(false);
cin.tie(NULL);

int T; cin >> T;
while(T--){
int N, K; cin >> N >> K;

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);

while(!Q.empty()){
int u = Q.front(); Q.pop();
if(Dist[i] != -1) continue;
Dist[i] = Dist[u] + 1;
Q.push(i);
}
}
cout << Dist[N - 1] << endl;
}

return 0;
}
``````
3 Likes

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

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

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.
https://www.codechef.com/viewsolution/29175390

Can somebody please look at my code and tell me why it TLEd? Thanks in advance.
https://www.codechef.com/viewsolution/29185616

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!

3 Likes

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