Approach for UnderTheTunnels from Jan Lunctime 2020?

general
1

I solved it using BFS+DP

Anyother interesting approaches?

2 Likes
2

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

3

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

4

My bfs didn’t work…can u tell me why?
https://www.codechef.com/viewsolution/29184257

5

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

6

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.
7

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

2 Likes
8

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

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

9

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
10

correct. I handled this :slight_smile:

11

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
12

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

2 Likes
13

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

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

    return 0;
}
3 Likes
14

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

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

15

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

16

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

17

Yes, I too solved exactly similar to your code.

1 Like
18

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:

3 Likes
19

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