PROBLEM LINK:
Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
You are given a sequence of positive integers A_1,A_2,…,A_N. You should make all its elements equal by performing a sequence of operations.
In one operation, you may choose any contiguous subsequence A_l,A_{l+1},…,A_r such that for each i (l+1≤i≤r), A_i=A_l, i.e. a sequence of identical elements, then choose any integer x<A_l, and for each i (l≤i≤r), replace A_i by x. The integers x
chosen in different operations may be different.
Find the smallest number of operations necessary to make all elements of the given sequence equal.
DIFFICULTY:
Easy-Medium
CONSTRAINTS
1 \leq N \leq 5*10^5
QUICK EXPLANATION:
For each element find the the first smaller value to the left of it or to the right of it. Afterwards start from values from biggest to smallest and match each value with the one to its left (or its right) by performing one operation and hence making them equal. Finding a smaller element to the left or to the right is a classical problem that can be done using stacks in O(N).
EXPLANATION:
If we have a non-deceasing sequence of N integers consisting of K distinct values then the number of operations needed is equal to K-1. We can do our operations from the end to the beginning of the sequence.
For example:
\{1,1,3,5,8,8,11,11,11\}
Obviously the sequence of operations would be:
\{[7,9]->8 , [5,9]->5 , [4,9]->3 , [3,9]->1\}
It’s obvious that every contiguous segment (subarray) of equal values will go under the same operations throughout the whole solution until reaching the final value. In fact, the final value must be the value of the smallest number in our array. We can’t assume it’s less than that because it would cost us more operations.
As you can notice in the example, it’s always better to decrease elements starting from the elements with the largest values, doing it in this fashion would make us form larger segments of the same value, and thus minimizing operations. That’s the intuition of making every value equal to the first smaller one directly to the left or to the right.
Now let’s start from elements in our array from left to right pushing them to stack one by one. Let’s assume we are processing a certain element. Now while there are elements at the top of the stack with a larger value we need to pop them out and make them all equal to our current element.
Let’s notice 2 observations:
1- By always popping elements at the top of the stack larger than the last pushed element our stack would always be non-decreasing
2- As a result, when we pop X elements, it means that we are fixing a non-decreasing sequence of numbers and thus we need X operations (not X-1 because we already have the target value).
After all we would finish with a stack of Y elements that we can make them equal in Y-1 operations.
Complexity: O(N)
Editorialist solution
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, q, A[N], L[N];
int main()
{
scanf("%d", &q);
for (; q; q --)
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d", &A[i]);
A[0] = * min_element(A + 1, A + n + 1);
for (int i = 1; i <= n; i ++)
{
L[i] = i - 1;
while (L[i] && A[L[i]] >= A[i])
L[i] = L[L[i]];
}
int Cnt = 0;
map < int , int > MP;
for (int i = 1; i <= n; i ++)
if (A[i] != A[0])
{
if (!MP.count(A[i]) || MP[A[i]] < L[i])
Cnt ++;
MP[A[i]] = i;
}
printf("%d\n", Cnt);
}
return 0;
}
Tester Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T , n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int res = 0;
vector <int> S;
for (int j = 0 ; j < n ; j++){
int x;
scanf("%d", &x);
while (!S.empty() && S.back() > x) {
res++;
S.pop_back();
}
if (!S.empty() && S.back() == x) continue;
S.push_back(x);
}
res += S.size();
printf("%d\n", --res);
}
return 0;
}