Explanation of the code, I am checking the polarity of unsorted ends, if they are diff then the question can be solved in one move if not then we need to check if we have different polarity on either end to include it in our range, if yes then it can be done in one move else it should take 2 moves, Please help with the question. thank you.
#include <bits/stdc++.h>
#define lp(n) for(int i=0; i<n; i++)
#define ll long long
#define endl '\n'
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()
#define FAST_IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int main() {
FAST_IO;
int t;
cin >>t;
while(t--){
int n;
cin >> n;
vector<int> arr(n);
vector<char> polarity(n);
pair<int, int> N, S;
N.first = n-1, S.first=n-1, N.second=0, S.second=0;
lp(n) cin >> arr[i];
lp(n) {
cin >> polarity[i];
if(polarity[i]=='N'){
N.first = min(N.first, i);
N.second = max(N.second, i);
}
if(polarity[i]=='S'){
S.first = min(S.first, i);
S.second = max(S.second, i);
}
}
//case -1
bool flag=true;
lp(n-1){
if(polarity[i]!=polarity[i+1]) flag=false;
}
if(flag){
cout << -1 << endl;
continue;
}
// Unsorted Parts
// NN----NS---SN--SS = 1 , that is if the start and the end of unsorted parts combined is different, then answer is 1 else it is 2
int start=n-1, end=0; // index of the start of unsorted part, and the end of unsorted part
// there might be several unsorted parts like in the below example
// 2212352, the unsorted parts are 21, 52, therefore the start = 1 and, end=6
lp(n-1){
if(arr[i]>arr[i+1]){
start = min(i, start);
end = max(i+1, end);
}
}
// cout << start << " " << end << endl;
// the array is sorted already
if(end==0){
cout << 0 << endl;
continue;
}
// unsorted array, finding the moves
flag = false; // meaning it require two moves
if(polarity[start]==polarity[end]){
if(polarity[start]=='S' && N.first<start || polarity[start]=='N' && S.first<start) flag = true;
if(polarity[end]=='S' && N.second>end || polarity[end]=='N' && S.second>end) flag=true;
}else flag = true;
if(flag) cout << 1 << endl;
else cout << 2 << endl;
}
}
Question if from “1800 to 2000 difficulty problems”.