POPTUNNL - Editorial

editorial
, , , ,
23

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

I used dfs as well, what is wrong with this approach?

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

can anyone explain me how this part works?

25

this is standard bfs with single source shortest path in unweighted graphs

26

can someone plxx tell me why my code is giving TLE for the 2nd subtask. I use DP and queue approach(not in a perfect DFS/BFS manner).

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

27

Try without pair in queue i also got same TLE

28

Ok I got AC the issue was that I was not doing visited=true while adding in queue so multiple similar elements were getting pushed in queue that is leading to TLE

29

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

why my code gives WA. I done same as you .

30

can you please tell me why my code gives WA.
https://www.codechef.com/viewsolution/29228227

31

Can Anybody Please Tell me why this code is showing wrong answer for POPTUNNL
I included all the necessary comments
Thanks in advance

#include <bits/stdc++.h>
using namespace std;
int p=INT_MAX;

void check(map<int,string>m,int n,int k,int first,int c,map<int,int>visited)
{
//cout<<“first=”<<first<<endl;
if (first==n)
{
//cout<<“c=”<<c<<endl;
p=min(p,c); //taking the minimum count to reach at end vertex
return ;
}
for(int i=max(first-k,1);i<=min(first+k,n);i++)
{
//cout<<“i=”<<i<<endl;
if (i!=first&&visited[i]==0&&m[first][i]==‘1’) // checking the condition
{
visited[i]=1; //marking as this vertex is visited
return check(m,n,k,i,c+1,visited); // exploration of new vertex
visited[i]=0; // unmarking the visited vertex
}
}
}

int main()
{
int t;
cin>>t;
while(t–)
{
int n,k;
cin>>n>>k;
map<int,string>m;
string s;
for (int i=1;i<=n;i++)
{
cin>>s;
s=“0”+s; // here to make index start with 1 i add 0
m[i]=s;
}
map<int,int>visited; // for visited vertex
visited[1]=1;
check(m,n,k,1,0,visited);
if (p==INT_MAX)
cout<<-1<<endl;
else
cout<<p<<endl;
p=INT_MAX;
}
}

32

https://www.codechef.com/viewsolution/29267824
cant figure out whats wrong , someone please help

33

here we are visiting all the adjacent nodes to current node , i.e Adj[u] , where u is current node
and the dist to child node is dist of current node + 1, i.e Dist[i] = Dist[u] + 1; and push ( i ) in queue ,(i is the child node).

2 Likes
34

Thank you for your achar. oops vichaar

35

Can anyone please provide test cases for this question , examples are showing correct results but subtasks are giving WA?

36

I used DIJKSTRA algorithm on the adjacency matrix, got AC partially ,remaining subtasks gives WA, what is wrong with DIJKSTRA approach my solution by dijkstraas compared with BFS approach

37

Good point…I ll check my solution again

1 Like
38

You can simply do it using Single Source Shortest Pah.It’s nicely explained here : Under The Tunnels | CodeChef Jan Lunchtime Solution | Algorithm and Code Explanation by alGOds!! - YouTube

39

It’s nicely explained here : Under The Tunnels | CodeChef Jan Lunchtime Solution | Algorithm and Code Explanation by alGOds!! - YouTube

40

can’t this be solved using dp ?
if then someone has solved it plz reply

41

I used recursion to solve the question and got AC in 4 tasks out of 5. Can someone tell me what’s wrong in my code?
https://www.codechef.com/viewsolution/31739270

42

Yes, I have solved it partially using recursion, but it only passes the first subtask and for the second one it gives TLE, however I have a DP solution also which passes with AC.
The recursion solution as you are asking is here.
Link- CodeChef: Practical coding for everyone