This editorial is not provided by Editorialist but so for knowledge.
ERASE BUT ALL ONE
The question requires some observations that can help you to implement it easily. The question asks that given you a permutation, You can do the following operation
Select two distinct indexes i and j such that A[i] < A[j] , then you can remove any one of them and rest array is then concatenated.
You need to use the above operation and tell whether it is possible to delete exactly N-1 elements from the array such that only 1 element is left in the array.
The first and most easy observation is to see that whenever there is a case such that the first element of array is N or last element of array is 1 we can never be able to delete N-1 elements from it as N cannot be deleted in the former case and 1 cannot be deleted in the second case thus there would be one more element atleast left in the array making a total of 2 elements thus not possible. The next observation is just a more generalisation of above small observation.
CLAIM : If the MEX(Minimum Excludant) of the last i numbers is i+1, where 1<= i+1 <= N, then we cannot satisfy the above asked question. Here MEX has been considered to start from 1 and not from 0.
PROOF : Let us take an example for N = 6
Suppose the permutation is = 4 5 3 6 1 2 . In this case we can delete 4 by using 6, 5 by using 6 and then we are left with 3 6 1 2 . It is clear that deleting either 3 or 6 will result in something either 3 1 2 or 6 1 2 for which we cannot do any operation to fulfiil above So the key observations says that if (large numbers are grouped on one side) and (small numbers are grouped on other side) then it would not be possible to do above statement. But now how do we define small and large numbers so here comes MEX use. If I take example given above and start iterating from back of the array then at at index 4 (i.e 1) we get MEX as 3 which is just (2+1) here 2 is the number of elements we have traversed so we cannot do above operations to convert.
For confirmity let us take an example where its possible to convert
for N = 5, 4 3 1 2 5 here at each point MEX condition is not satisified. Let me show you a dry run
. At idx = 4, element = 5 , MEX = 1 , (1+1) = 2 not equal to MEX
At idx = 3 , element = 2 , MEX = 1, (2+1) = 3 not equal to MEX
At idx = 2 , element = 1, MEX = 3, (3+1) = 4 not equal to MEX
At idx = 1, element = 3, MEX = 4, (4+1) = 5 not equal to MEX
At idx = 0 , element = 4, (here we have that our permutation has run out of numbers as MEX = 6 which is not a part of our permuation as N = 5) so here although MEX = 6 is equal to (5+1) but at the same it must be a part of out permutation. So we get that our answer is possible.
Now to find MEX I have used set data structure in C++ STL by which we can easily implement above solution. As retrieval time in set is log(N) so overall time complexity of above approach is
N*log(N) which well fits in time complexity. There are much intelligent implementation for MEX that take O(N) time. You can check them out too.
Solution
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int>A(n);
for(int i = 0; i<n; i++){
cin>>A[i];
}
set<int>mex;
for(int i = 1; i<=n; i++){
mex.insert(i);
}
int p = 0;
bool check = true;
for(int i = n-1; i>=0; i--){
int m = 0;
p++;
mex.erase(A[i]);
m = *(mex.begin());
if(p+1==m){
check = false;
break;
}
}
cout<<(check == true ? "YES\n" : "NO\n");
}
return 0;
}
@cody_36
my solution(not working)
lets say permutation of n elements are
a1 a2 a3… an
step1:some how we delete all elements lesser than a1 to the right of a1
step2:since after step1 we have only elements greater than a1 to its right we can delete all of them by using a1
step3:now we are left with only a1(hence only one element left)
Now anwer lies how we do step1
1)By intution we can say if a1 = n or an = 1 answer is “NO”
2)also we have few other cases where deletions are interdependent like
example1:- [3, 4, 1, 2] here first we have to delete 1,2 (from step1) which is not possible since they are interdependent(means each element of the pair can only be deleted by other in the pair)
example2:- [4,5,2,1,3] here [2,1,3] are interdependent
so to detect these interdependent pairs i used minLeft[i] and maxRight[i] if any two pairs in the array has minLeft[i] and maxRight[i] same
then answer will be “NO”
else “YES”
can we pls tell why this solution is not working i have tried for all permutations of n=4,5 this works but i couldnt understand what im missing
The problem statement specifies that the input array will be a permutation, and the first code you provided relies on that fact. But your input array is not a permutation.
If max element is on the rightmost index then answer is always possible. since it can pair each min element to its left and remove those.
If max element is on the beginning then answer is not possible, since this element cannot be removed from the right elements.
If max element is in between let say at index j, then we need to remove it, but how ?
remove elements from [0, j] index except the minimum value in between.
3.1 If max element gets removed then there might be cases like in which it can remove elements on its left.
3.2 This max element can only be removed by any minimum element on its left.
3.3 While pruning we want the minimum element to be on the left, which can help in removing all greater elements on the right
since the element between min and max element on the left part are redundant we just remove those.
I was actually upsolving cause I was not able to do this day before yesterday cause time was over. Then I was just making observations randomly and then I saw that such pattern was coming out. Then I tried it on 10-20 handmade test cases by me and it was working correctly on all so I gave it a try and it came to be correct answer.