ICM0001 (Suffix Sort) - Editorial

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)

4 Likes

I like Setter solution, Nice work

2 Likes

:innocent:

why does this test case wont work?
3
2 1 3
one can just take the last element then attach it in the front, it will become
3 2 1
similarly repeating this 3 times, will lead to
1 2 3

2 1 3
3 2 1
1 3 2
2 1 3

1 Like

past link of your code or use ``` before code to get format
and what is set u have not declare properly

Really sorry for that here is my code link
https://www.codechef.com/viewsolution/44758457
Please tell what is wrong in it @loud_mouth

Really sorry for that here is my code link
[Solution: 44758457 | CodeChef )(Solution: 44758457 | CodeChef)
Please tell what is wrong in it @loud_mouth

dude check output
for
n=6
6 5 7 1 2 3
n=3
2 2 2
your’s is
no
yes
1
it should be
yes
1
yes
0

i think u miss understood question check editorials

Thank you

#include
using namespace std;

int main() {
long long int a;
cin>>a;
for(long long int i=0;i<a;i++)
{long long int l=0;
long long int b;
cin>>b;
long long int c[b];
long long int mini=0;
long long int maxi=0;
for(long long int j=0;j<b;j++)
{ cin>>c[j];
if(j>0)
{

        if(c[mini]>c[j])
        {//cout<<"hi";
            mini=j;
        }
        if(c[maxi]<c[j])
        {
            maxi=j;
        }
    }
        }
    //    cout<<maxi<<mini<<endl;
    long long  int d=0;
   long long  int e=0;
    for(long long int j=0;j<maxi-1;j++)
    {
        if(c[j]>c[j+1])
        {
            d=1;
            break;
        }
       
    }
    for(long long int j=mini;j<b-1;j++)
    { 
        if(c[j]>c[j+1])
        {
            e=1;
            break;
        }
    }
    long long int m=0;
    if(c[b-1]<c[0])
    {
        m=1;
    }
    
    if(mini==0 && maxi==b-1)
    { 
        for(long long int j=0;j<b-1;j++)
        {
            if(c[j]>c[j+1])
            
            {l++;
                cout<<"NO"<<endl;
                break;
            }
        }
        if(l==0)
        {
            cout<<"YES"<<endl;
            cout<<0<<endl;
        }
    }
    else if(maxi==mini-1 )
    { 
       if(d==0 && e==0 && m==1)
       {
           cout<<"YES"<<endl;
           cout<<1<<endl;
       }
       else
       {
           cout<<"NO"<<endl;
       }
        }
   else
   {
       cout<<"NO"<<endl;
   }

}
return 0;
}

why i am getting WA ,even my answer passing all testcases.