PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Nayeemul Islam Swad
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Greedy
PROBLEM:
You are given a permutation P of length N. You can perform the following operation on P:
- Choose any i and j such that i<j and P_i<P_j, and remove exactly one of them from the array. After removing, the remaining parts of the array are concatenated.
Find out if it is possible to apply the given operation any number of times such that only one element remains in the array.
EXPLANATION:
Giving credits to the author for this explanation where it’s due.
The answer is YES if and only if there is no suffix, other than the whole array, of length L (1 \le L < N) that consists of the smallest L elements.
Proof of the only-if part:
Let us prove this by contradiction:
Say we have an array of length N, containing a suffix of length L of smallest L elements. We say that after applying a certain number of operations, only one element remains in the final array.
Since there is a suffix of length L which consists of the smallest L elements it means:
Therefore, there exists no pair (i,j) such that index i and j lies on the prefix A[1\dots x-1] and suffix A[x,\dots,N] respectively and A_i<A_j. Hence there will be at least one element left in the prefix A[1\dots x-1] and at least one element on the suffix A[x,\dots,N].
Therefore there will be at least two elements left in the whole array in the best case and that’s a contradiction to what we assumed.
Proof of the if part:
We can prove the claim using induction. The case when N = 1 and N = 2 are trivial. So let’s assume that N \ge 3. We’ll show that we can remove an element from the array with a valid operation, such that the property that no suffix of length L contains the smallest L numbers, still holds. Let A_i be the maximum number in the array and A_j be the second maximum. We consider two cases,
Case 1:
If i < j, then removing A_i from the array doesn’t break the property. The operation to remove A_i consists of A_i and the element right before it (A_i cannot be the first element, otherwise the property wouldn’t hold)
Case 2:
If i> j, then removing A_j from the array doesn’t break the property. The operation to remove A_j simply consists of A_j and A_i.
Implementation ideas:
Since the array is guaranteed to be a permutation, checking each of the suffix-sums to see if they consist of the smallest natural numbers is enough. In other words, for a suffix of size L, we check if the suffix sum equals \dfrac{L \cdot (L + 1)}{2}.
TIME COMPLEXITY:
\mathcal{O}(N)
SOLUTIONS:
Author's Solution
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
prefix_sum = 0
natural_suffix_sum = 0
answer = True
for i in range(n - 1):
prefix_sum += a[i]
natural_suffix_sum += n - i
if (prefix_sum == natural_suffix_sum):
answer = False
if answer:
print("YES")
else:
print("NO")
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> suf_max(n + 1);
for (int i = n - 1; i >= 0; i--) {
suf_max[i] = max(suf_max[i + 1], a[i]);
}
string ans = "YES";
for (int i = 1; i < n; i++) {
if (suf_max[i] == n - i) {
ans = "NO";
}
}
cout << ans << '\n';
}
return 0;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int suf[n];
suf[n-1] = a[n-1];
for(int i=n-2;i>=0;i--)
suf[i] = max(suf[i+1],a[i]);
for(int i=1;i<n;i++)
{
if(suf[i] == n-i)
{
cout<<"NO"<<"\n";
return;
}
}
cout<<"YES"<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}