PROBLEM LINK:
Author: rocknot
Tester: yogesh_5326
Editorialist: rocknot
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Sorting
PROBLEM: Priority Sequencing
Meena recently completed his masters degree in Operating System and got an internship at Microsoft. Microsoft is secretly working with Tesla on new operating system for self driving cars but don’t wan to leak this News.When Microsoft realized that Meena is good at designing operating system, They assigned him a work of sequencing the tasks according the priority of that task, so that necessary/important tasks can be handled before some minor tasks.
Meena is given list of tasks and their priorities, there are N distinct tasks having priority from 0 to N−1(all tasks have different priorities).Meena wants to sequence the tasks in increasing order of priority.Meena can swap the adjacent tasks if they are not in increasing order, but the hardware given to Meena is limited so he can swap adjacent tasks only if absolute priority difference between this tasks is 1.You are given array A[N] having priorities of the tasks you need to determine if Meena could sort them.
If it is possible to sequence all the tasks print “YES” else “NO”.
Note! output is case sensitive “YES” and “Yes” are different.
EXPLANATIONS
While transversing the array check if ith element is greater than i+1th element and check that ith and i+1th element have difference 1 swap the elements. If difference is more than 1, in that case sequence cannot be sorted so return false and end the transversing.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
bool checkForSorting(int arr[], int n)
{
for (int i=0; i<n-1; i++)
{
if (arr[i] > arr[i+1])
{
if (arr[i] - arr[i+1] == 1)
swap(arr[i], arr[i+1]);
else
return false;
}
}
return true;
}
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
if (checkForSorting(arr, n))
cout << "YES\n";
else
cout << "NO\n";
}
}