CH2A editorial

editorial
,
1

PROBLEM LINK:

Practice

Contest

Author: Rishabh Jain

Tester: Chandan Boruah

Editorialist: Rishabh Jain

DIFFICULTY:

EASY

PREREQUISITES:

Basic Array

PROBLEM:

Given an array, check wether it can be a sorted array if we can rotate(put first elementin last) it any number of times.

QUICK EXPLANATION:

Author: Simple O(n) approach, by checking the answer for each local minima. or

Tester: Simulate the rotation n(the number of elements in the array) number of times.

EXPLANATION:

Author’s solution: Traverse the array 2 times. Each time we find an element less than previous, we try to check that wether we can get a sorted array from here. The catch here is that we don’t need to check O(n^2) times. The only possible answer can only occur from local minimas.

Tester’s solution: Check if the array is sorted. Then put the first element in last using a linked list and then again check if the array is sorted. Do this “the number of elements in the array” times.

AUTHOR’S SOLUTION IN CPP:

#include<bits/stdc++.h>
#define ll long long
using namespace std;


ll a[50];
ll ans;
int main()
{
	ll t,n,streak;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
			{	
				cin>>a[i];
			}

		string ans = "No";
		streak = 1;
		if(n == 1)
		{
			cout<<"Yes\n";
			continue;
		}

		for(int i=0;i<2*n-1;i++)
		{
			if(a[(i+1)%n] >= a[i%n])
			{	streak++;
				if(streak >= n)
					ans = "Yes";
			}
			else
				streak = 1;
		}

		cout<<ans<<"\n";

	}


	return 0;
}

Tester’s Solution in CS:

using System;
	using System.Collections.Generic;
	class some
	{
		public static void Main()
		{
			int n=int.Parse(Console.ReadLine());
			for(int f=0;f<n;f++)
			{
				int t=int.Parse(Console.ReadLine());
				string[]ss=Console.ReadLine().Split();
				int[]arr=new int[t];
				int[]test=new int[t];
				for(int i=0;i<ss.Length;i++)
				{
					arr[i]=int.Parse(ss[i]);
					test[i]=arr[i];
				}
				Array.Sort(test);
				if(yes(arr,test)){Console.WriteLine("Yes");continue;}
				bool b=false;
				for(int i=0;i<t;i++)
				{
					List<int>ll=new List<int>(arr);
					ll.Add(arr[0]);
					ll.RemoveAt(0);
					arr=ll.ToArray();
					if(yes(arr,test))b=true;
				}
				if(b)Console.WriteLine("Yes");
				else Console.WriteLine("No");
			}
		}
		public static bool yes(int[]arr,int []test)
		{
			for(int i=0;i<arr.Length;i++)
			{	
				if(arr[i]!=test[i])return false;
			}
			return true;
		}
	}