PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Adithya
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
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.