PROBLEM LINK:
Suffix Sort
Author: loud_mouth
Tester: dyrroth
Editorialist: loud_mouth
DIFFICULTY:
EASY
PROBLEM:
Given an array, can we sort it by taking suffix and attaching it to the front and doing it as many times as possible?
Prerequisites:
Sorting, that's it.
EXPLANATION:
First off, if array is already sorted answer is YES, 0.
OBSERVATION : No matter how many times you do the move, the circular
order of the array does not change. Try for yourself!
[1 2 3 4 5 6 7 8] -->
[7 8 1 2 3 4 5 6] -->
[5 6 7 8 1 2 3 4 ] -->and so on...
No matter which array you pick among these, you can always
see that starting at 1, we always get the same 1, 2, 3, 4, 5, 6, 7, 8
order.
Thus, the move can only change the starting point of the circular array,
not it's orientation.
So, the only way the final array is sorted is if it is already sorted
starting from some index x to index (x-1+n)%n. This can be checked in
O(n) and such orientation can be achieved in a single move of size n-x.
So, the answer if YES, 1.
Otherwise answer is NO.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define pb push_back
#define endl '\n'
#define sa(x) sort((x).begin(), (x).end());
#define int long long
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T> static inline void sd(vector<T> &x) {sort((x).begin(), (x).end(), greater<T>()) ; }
void solve(){
int n;
cin>>n;
vi v(n);
rep(i,0,n){
cin>>v[i];
}
int c=0;
rep(i,0,n-1){
if(v[i] > v[i+1]){
c++;
}
}
if(c==0){
cout<<"YES\n0\n";
}
else if(c==1 and v[n-1]<=v[0]){
cout<<"YES\n1\n";
}
else cout<<"NO\n";
}
signed main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int testcases=1;
cin>>testcases;
while(testcases--){
solve();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
bool is_cycle_sort(ll a[], int n)
{
bool f = 1;
int i;
for (i = 0; i < n - 1; i++)
{
if (a[i] > a[i + 1])
break;
}
i++;
for (int j = i; j < n - 1; j++)
{
if (a[j] > a[j + 1])
{
f = 0;
break;
}
}
if (f == 0)
return false;
else
{
if (a[n - 1] <= a[0])
return true;
else
return false;
}
}
int main()
{
int T = 1;
cin >> T;
while (T--)
{
ll n;
cin >> n;
ll arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
if (is_sorted(arr, arr + n))
cout << "YES\n0\n";
else if (is_cycle_sort(arr, n))
cout << "YES\n1\n";
else
cout << "NO\n";
}
return 0;
}
Time Complexity
O(n) to check for such a case (see sample solution)
