TRP-Editorial

PROBLEM LINK:

Tricky Path

Author: jain_990
Tester: hellb0y_suru
Editorialist: jain_990

DIFFICULTY:

EASY

PROBLEM:

Given an array lets say arr[] and a starting index let say i. You have to reach index that contains element 0 from that given starting index. At every index you can either move i+arr[i] or i-arr[i]. Find whether you will ever be able to reach index that contains 0.

Prerequisites:

  • Basic knowledge of recursion and DFS.

Hint:

Try to construct a graph and then apply DFS.

EXPLANATION:

It follows straightforward approach of constructing a graph and adding i+B and i-B as it’s vertex to ith node.
We can then traverse the graph using Depth First Search (DFS). With every hop we reach a node and then traverse to its vertices, eventually leading to the index having value 0.
If every node gets visited and we still haven’t got 0, it becomes clear that it’s not possible to reach there. Hence false.

Time complexity: O(N) since we will visit every index at most once.

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
vector<int>v[50000];
int vis[50000]={0};
bool path = false;
void dfs(int s,vector<int>&arr)
{
   if(arr[s]==0)
   {
       path = true;
       return;
   }
   if(vis[s])
       return;
   vis[s] = 1;
   for(int i=0;i<v[s].size();i++)
   {
       if(path)
           return;
       dfs(v[s][i],arr);
   }
}
bool canReach(vector<int>& arr, int start) {
   for(int i=0;i<arr.size();i++)
   {
       if(i+arr[i]>=0 && i+arr[i]<arr.size())
       v[i].push_back(i+arr[i]);
       if(i-arr[i]>=0 && i-arr[i]<arr.size())
       v[i].push_back(i-arr[i]);

   }
   dfs(start,arr);
   if(path)
       return true;
   return false;
}
int main()
{
 int n;
 cin>>n;
 vector<int>vvv;
 for(int i=0;i<n;i++)
 {
   int b;
   cin>>b;
   vvv.push_back(b);
   
 }
 int c;
 cin>>c;
 if(canReach(vvv,c))
 {
   cout<<"true";
 }
 else
 {
   cout<<"false";
 }
 return 0;
}

Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

vector<int> g[100000];
vector<bool> vis(100000,0);

void dfs(int node){
   vis[node] = 1;
   for(auto &i: g[node]){
       if(!vis[i]) dfs(i);
   }
}

void sol(){
   int n; cin >> n;
   int a[n];
   for(int i=0;i<n;i++) cin >> a[i];
   int start ; cin >> start;
   for(int i=0;i<n;i++){
       if(a[i]!=0){
           if(i - a[i]>=0) g[i].push_back(i - a[i]);
           if(i + a[i]< n) g[i].push_back(i + a[i]);
       }
   }
   dfs(start);
   for(int i=0;i<n;i++){
       if(a[i]==0 && vis[i]){
           cout << "true";
           return;
       }
   }
   cout << "false";
   return;
}

int main() {
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   sol();
}

3 Likes