PROBLEM LINK:
Setter: Ritik Sedana
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Professor is at some direction and Tokyo is at exact opposite direction to professor. To get the same direction as Tokyo, professor can take any substring of S consisting of L and R characters, and perform those operations. Here L means turning left and R means turning right. We need to determine if professor can turn in the same direction as Tokyo or not.
EXPLANATION:
-
Since Tokyo is initially at the exact opposite direction of professor, in order to get to the same direction as Tokyo, Professor can perform two operations of the same type.
-
That means professor can perform either LL or RR to get in the same direction as Tokyo.
-
Therefore in the string S, if there is a substring of length 2 which has equal characters, then the answer is YES.
-
Else the string is either LRLR\dots or RLRL\dots Here, whatever substring we take, if we follow the steps in that substring one move’s effect will cancelled by the next move. ( L and R cancel each other ). Therefore, in this case, the answer is NO.
TIME COMPLEXITY:
O(N) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;
string s;
cin >> s;
bool ok = false;
for (int i = 1; i < n; i++)
{
if (s[i] == s[i - 1])
{
ok = true;
break;
}
}
if (ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
Setter's solution
/* author:Professor*/
#include <iostream>
using namespace std;
#define ll long long
#define pb push_back
#define rep(i,n) for(long long int i=0;i<n;i++)
#define repl(i,L,R) for(long long int i=L;i<=R;i++)
#define vc std::vector<char>
const long long int MOD=1e9+7;
const char nl='\n';
#define vli std::vector<long long int>
const int maxN=1e5+5;
#define sc std::set<char>
#define sli std::set<long long int >
#define qc std::queue<char >
#define qli std::queue<long long int >
#define mli std::map<long long int ,long long int>
#define mc std::map<char, long long int>
#define umli std::unordered_map<long long int,long long int>
#define umc std::unordered_map<char,long long int>
#define mem(arr, x) memset(&arr, x, sizeof(arr))
#define debug(x) cerr <<"["<<#x<<" : "<<x<<"]"<<'\n';
#define gap ' '
#define ff first
#define ss second
#include<cmath>
#include<bits/stdc++.h>
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
void read(ll arr[],ll n){ for(ll i=0;i<n;i++) cin>>arr[i];}
void solve()
{
ll n;
cin>>n;
string s;
cin>>s;
rep(i,n-1)
{
if(s[i]==s[i+1])
{
cout<<"YES"<<nl;
return;
}
}
cout<<"NO"<<nl;
}
int main() {
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r",stdin);
// freopen("output.txt","w",stdout);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
ll t=1;
cin>>t;
while(t--)
{
solve();
}
// cerr<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
// your code goes here
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
bool f = false;
for(int i = 0; i < n - 1; i++){
if(s[i] == 'L' && s[i + 1] == 'L'){
f = true;
break;
}
if(s[i] == 'R' && s[i + 1] == 'R'){
f = true;
break;
}
}
if(f){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions. 