PROBLEM LINK:
Setter: Akshit Monga
Tester: Aryan Choudhary
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
An array A of size N is called stable if all the elements in it are equal. We need to find the minimum number of operations to convert an array into a stable array if an operation can be any one of the following:

Select prefix A[1,2 \dots , k] where A_k >= A_i for all 1 \leq i \leq k and perform A_i = A_k for all 1 \leq i \leq k.

Select any segment A[L, \dots, R] and cyclically shift the elements in this segment to the left keeping other elements in the array unchanged.
EXPLANATION:

If initially all the elements in the array are equal, obviously the answer is 0.

Let max be the maximum element in the array and let it be at index ind. (If multiple indices are possible, take ind as the maximum among them).

If ind =N, we can just perform the first operation taking k = N and convert all the elements in the array equal to max.

If ind \lt N, we need to perform a total of 2 operations. First, we need to apply operation 2 on the segment A[ind,\dots, N]. This sends the value at index ind ( i.e, max) to index N. Now we can perform operation 1 taking k = N, and convert all the elements in the array equal to max.
TIME COMPLEXITY:
O(N) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int tests;
cin >> tests;
while(tests) {
int n;
cin >> n;
vector<int> a(n);
for (int i=0; i<n; i++) {
cin >> a[i];
}
bool allEqual = true;
int max1 = a[0];
for (int i=0; i<n; i++) {
if (i>0 && a[i]!=a[i1]) {
allEqual = false;
}
max1 = max(max1, a[i]);
}
if (allEqual) {
cout << 0 << endl;
}
else if (a[n1] == max1) {
cout << 1 << endl;
}
else {
cout << 2 << endl;
}
}
return 0;
}
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while (t){
int n;
cin>>n;
vector<int>a(n);
int maxi = 0;
int elem = 0;
bool isEqual = true;
for (int i = 0;i<n;i++){
cin>>a[i];
maxi = max(maxi,a[i]);
if (i == 0)
elem = a[0];
else {
if (a[i] != elem)
isEqual = false;
}
}
if (isEqual)cout<<0<<endl;
else if (maxi == a[n  1])cout<<1<<endl;
else cout<<2<<endl;
}
}
Tester's solution
def main():
for _ in range(int(input())):
n=int(input())
a=[int(x) for x in input().split()]
if len(set(a))==1:
print(0)
elif max(a)==a[1]:
print(1)
else:
print(2)
main()
Please comment below if you have any questions, alternate solutions, or suggestions.