PROBLEM LINK:
Author: Pritish Priyatosh Nayak
Tester: Sibasish Ghosh
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Cakewalk
PREREQUISITES:
Two-pointer
PROBLEM:
Problem-statement
There is a array A of length N and Player 1 is standing on the 1st position in the array and Player 2 is standing in the last position in the array.
Player 1 and 2 both jump simultaneously.
If the position i where Player 1 is standing at has value A_i, then he will jump to index i+A_i in the next step. (He can jump out of the array i.e beyond Nth position ).
If the position j where Player 2 is standing at has value A_j, then he will jump to index j−A_j in the next step. (He can jump out of the array i.e beyond 1st position ).
You have to tell if they will ever land on the same cell at the same time. Print “Yes” if they will , else print “No”.
EXPLANATION:
We can simply simulate the whole process and check if they meet. We can set two variables as pointers L and R, where L represents the current position of Player 1 and R represents the current position of Player 2.
In each step , we update the both L and R simultaneously and check if they are same or not, i.e , L=L+A[L] and R=R-A[R] and then we check if they arrived in same position or not.
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
for (int i = 0; i < n; ++i){
cin>>a[i];
}
int l=0,r=n-1;
bool ok=false;
while(l<r)
{
l+=a[l];
r-=a[r];
if(l==r)ok=true;
}
cout<<((ok)?"Yes\n":"No\n");
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define mod 1000000007
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1,sum=0;
cin>>t;
assert(1 <= t && t <= 100000);
while(t--)
{
ll n,i,j;
cin>>n;
assert(2 <= n && n <= 100000);
sum+=n;
assert(sum <= 100000);
ll a[n+10];
for(i=1;i<=n;i++)
{
cin>>a[i];
assert(1 <= a[i] && a[i] <= 100000);
}
i=1,j=n;
while(i < j)
{
i+=a[i];
j-=a[j];
}
if(i == j)
cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}