POPTUNNL - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Adithya
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Breadth-First Search

PROBLEM:

There are N tiles numbered from 1 to N where you are standing at tile numbered 1 and want to reach tile numbered N in a minimum number of steps. Each tile may, at any point, be safe or unsafe to step on. We need to determine the number of steps or determine if it is impossible to reach from tile 1 to tile N. From tile numbered x, you can move to any tile numbered y such that |x-y| \leq K and tile y is safe to step on, where K is fixed.

Each tile has a switch associated with it, each of which is denoted by an N-length binary string S_i. Whenever you move to a tile numbered p, the switch S_p gets activated. When a switch S_p is activated, if j-th character of S_p is 1, then tile numbered j becomes safe to step on, otherwise, tile numbered j becomes unsafe. You cannot step on unsafe tiles.

QUICK EXPLANATION

  • If we are standing at tile numbered x, we can move to tile numbered y if |x-y| \leq K and tile y is safe to step on. For each node x, we can make the list of nodes reachable from x.
  • The above list forms the adjacency list of each node and we are required to find the shortest path from tile 1 to tile N in this directed graph which we can do using BFS.

EXPLANATION

We are currently at tile 1 and we want to reach tile N.
And when we are at tile x, we can move to any tile y such that |x-y| \leq K and after switch at tile x is activated, tile y is safe.

We can easily note at each step, only the current tile matter, not the previous steps. Also, the safe tiles are determined by the current switch only. So, from each node, we get a list of nodes that we can reach. Suppose, for each node, we prepare a list of the reachable nodes.

Hence, we have got a directed unweighted graph with N nodes and we want to find the smallest path from node 1 to node N. Now, we can easily calculate this using Breadth First search or any other shortest path algorithm. If the node N is not reachable at all from node 1, we print -1, thus solving the problem.

Discussion
Suppose the switches work as follows. Initially, all tiles are safe.

Currently, some tiles are safe while others are unsafe. A switch is a binary string S_x of length N, when activated, flips the state of tile y from safe to unsafe and vice versa, if y-th character of S_x is 1.

Can this problem be solved in polynomial time?

TIME COMPLEXITY

The graph construction takes O(N^2) time and BFS takes O(N+M) time, so overall time complexity is O(N^2) per test case.

SOLUTIONS:

Setter's 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;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

string s[1234];
int dist[1234];
vector<vi> adj(12345);
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		int i,j;
		rep(i,n){
			adj[i].clear();
			cin>>s[i];
		}
		rep(i,n){
			rep(j,n){
				if(abs(i-j)<=k && s[i][j]=='1'){
					//cout<<i<<" "<<j<<endl;
					adj[i].pb(j);
				}
			}
		}
		rep(i,n){
			dist[i]=inf;
		}
		dist[0]=0;
		queue<int> que;
		que.push(0);
		int u;
		while(!que.empty()){
			u=que.front();
			rep(i,adj[u].size()){
				if(dist[adj[u][i]]>dist[u]+1){
					dist[adj[u][i]]=dist[u]+1;
					que.push(adj[u][i]);
				}
			}
			que.pop();
		}
		if(dist[n-1]==inf){
			cout<<-1<<endl;
		}
		else{
			cout<<dist[n-1]<<endl;
		}
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class POPTUNNL{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), k = ni();
	    ArrayList<Integer>[] g = new ArrayList[1+n];
	    for(int i = 1; i<= n; i++){
	        String s = n();
	        g[i] = new ArrayList<>();
	        for(int j = 1; j<= n; j++){
	            if(s.charAt(j-1) == '0' || i == j || Math.abs(i-j) > k)continue;
	            g[i].add(j);
	        }
	    }
	    int[] d = new int[1+n];
	    int MX = (int)1e8;
	    Arrays.fill(d, MX);
	    d[1] = 0;
	    Queue<Integer> q = new ArrayDeque<>();
	    q.add(1);
	    while(!q.isEmpty()){
	        int u = q.poll();
	        for(int v:g[u])if(d[v] > d[u]+1){
	            d[v] = d[u]+1;
	            q.add(v);
	        }
	    }
	    if(d[n] == MX)d[n] = -1;
	    pn(d[n]);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new POPTUNNL().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

5 Likes

Anyone please tell me what’s wrong with my code https://www.codechef.com/viewsolution/29182027

Time limit for c++ should be 2 second, i used queue of std::pair and got TLE for second sub-task even with fast IO. Later changed it to queue of integers and got AC.

2 Likes

My solution is giving wrong answer even for partial correct section, but I am not sure what I missed?

Can anyone please let me know where is one of my way of solving this question wrong.
Instead of using bfs by chain extension, I tried to do it somewhat different but can’t figure out where is it getting wrong?
https://www.codechef.com/viewsolution/29186790

And my O(N*log_2(N*K)+N*K) code runs in 0.00 secs
I think your’s should be infinite loop. I don’t think it’s because of TL. How can 0.00 secs code take more than 1 sec just by using pairs. Because pairs should just make it two times slower.

1 Like

please tell me what’s wrong with this approach ,i am using dfs,how to make it work without getting tle,and as in editorial using bfs doesn’t gives tle whereas dfs does,why is it so?
https://www.codechef.com/viewsolution/29192108

can we solve this question using DP?

2 Likes

Can anybody tell me how it can be solved using recursion.

https://www.codechef.com/viewsolution/29189979
can anybody here tell me why my BFS soln is giving TLE on last tc

Yes this solution can be solved using recursion but it only score 50 points. I have attached my C++ code for your reference you can go through that.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll ans = INT_MAX, n, k;

bool check(ll i, ll j)
{
return ((i>=0)&&(i<n)&&(j>=0)&&(j<n));
}
void rec(vectors, ll title, ll jump, bool vis[])
{
if(title == (n-1))
{
ans = min(ans, jump);
return;
}
for(ll i = title + 1; i<= (title + k) ;i++)
{
if(check(i, title)&&(vis[i] == false)){
if(s[title][i] == ‘1’)
{
vis[i] = true;
rec(s, i,jump+1, vis);
vis[i] = false;
}
}

}
for(ll i =  title - 1; i>= (title - k) ;i--)
       {
       if(check(i, title)&&(vis[i] == false)){
       if(s[title][i] == '1')
        {
        vis[i] = true;
        rec(s, i, jump+1, vis);
        vis[i] = false;
        
    }
}

}

}
int main()
{
ll t;cin>>t;
while(t–)
{
cin>>n>>k;
vectors;
bool vis[n];
for(ll i=0;i<n;i++)
{
string ss;cin>>ss;s.push_back(ss);
vis[i] = false;
}
vis[0] = true;
rec(s, 0, 0, vis);
if(ans != INT_MAX)
{
cout<<ans<<endl;
}
else
{
cout<<-1<<endl;
}
ans = INT_MAX;

}

}

Here the “check” array is to keep track of which nodes are connected to the root node “1” , rather than, to see if this node is visited or not.
what I am doing is -
first , after updating all the w[i] for nodes connected to node 1 ,
I travel all the nodes where check[i] = 1, else put them in next round(the todocheck vector), now in the next round if check[i] is true means it has a connection to the root node update its child node’s w’s.
IF none in the todocheck is connected to rootnode then terminate the process with -1.
IF todocheck has no nodes left the terminate the process with answer.

Sir nice explaination but it seems that you haven’t mentioned Time complexity.

1 Like

thanks for your code

Hi
Updated the time complexity. Thanks for pointing out.

Can anyone tell me what’s wrong in my code
https://www.codechef.com/viewsolution/29199078

yes i have solved this using dp.
link to that is ,
https://www.codechef.com/viewsolution/29190098

1 Like

How did you change this?
I did the same optimisation, its still having TLE!

Queue<pair<int,int>> : https://www.codechef.com/viewsolution/29199176
2 Queues<int> : https://www.codechef.com/viewsolution/29199292

plz help me
I m getting tle
#include<bits/stdc++.h>
using namespace std;
int main()
{ int t;
cin>>t;
while(t–)
{int flag,f;
flag=0;f=0;
int n,k;
cin>>n>>k;int ctr=0;
string s;
vectorv;
for(int i=0;i<n;i++)
{cin>>s;
v.push_back(s);
}int it=0;
int j=0;int i=0;
for( i=0;i<n;i=it)
{ if(i==n-1||flag==-900)
break;
for(j=i+k;j>=0;j–)
{ if(j<i-k)
{ flag=-900;
break;
}
if(v[i][j]==‘1’&&i!=j)
{
ctr++;
flag++;
it=j;
break;
}
}
if(f==flag)
break;
else
f++;
}
if(i==n-1)
cout<<ctr<<endl;
else
cout<<"-1"<<endl;

}
return 0;
}

help me
https://www.codechef.com/viewsolution/29199496