PROBLEM LINK:
Setter- Sahil Chimnani
Tester- Encho Mishinev
Editorialist- Abhishek Pandey
DIFFICULTY:
Easy
PRE-REQUISITES:
Observations, Ability to understand formal notations, Patience to read a statement twice or thrice and look at Sample IO and read the given explanation.
PROBLEM:
Given an array A of size N, answer Q queries of form-
- L \ R- Tell if Maximal Increasing Subsequences and Maximal Decreasing Subsequences are equal in number or not.
A sequence is maximal increasing iff-
- The sequence should have contiguous elements.
- A_i < A_{i+1} is followed for all i in the sequence.
- If sequence starts after L, and the first element is A_i, then it should be impossible for A_{i-1} to be part of this sequence (otherwise the sequence isnt maximal right now).
- Similarly, if the sequence ends before R, it should not be possible to include the next element in it.
A maximal decreasing sequence is defined in similar way.
QUICK-EXPLANATION:
Key to AC- Read the statement and look at sample IO. Realize that maximal increasing and decreasing sequences alternate!
Lets henceforth refer to Maximal Increasing Sequence as MIL and Maximal Decreasing Sequence as MDL.
Realize that the MIL and MDL alternate one after the other. Hence, all you need to check is if the first 2 elements and last 2 elements in range [L,R] are both part of different type of sequence of not. If they are part of same type of sequence, then MIL and MDL are not same in number. Else they are!
EXPLANATION:
This editorial will be a short one. Mostly because there is not a lot to discuss or observe apart from the main observation. We will discuss the following-
- How to deal with such statements
- Observing and Proof that MIL and MDL alternate
- Wrapping up and Final Answer.
So lets get started!
Dealing with such statements
Ok, lets take a breath.
Even I was all WTF on my first read of the statement. But doing WTF on statement is not going to fetch me \color{lightgreen}AC. So here is what to do-
- Read the statement. Give it a WTF look for first 5 minutes.
- Then take a deep breath and proceed to sample.
- After understanding (or perhaps not!) the samples, re-read the statement in the new light.
- Focus on keywords like maximal, increasing etc. Try to map which condition is mapping to which keyword.
The last one helps. I usually follow these 4 steps when faced with a tough statement - especially in short contests where sometimes a tough statement turns out to be the cakewalk problem!
Observing and Proving that MIL and MDL alternate
First lets discuss the intuition and then go to the formal proof.
This question tries to look tough by using the word “Maximal” in MDL and MIL which makes everyone think that there must be some rare trick to solve this question. But its not so!
Take this example-
A=[10,20,30,5,6,7]
Say L=1 and R=6 (1 based indexing). We see that there are 2 MIL here, namely (10,20,30) and (5,6,7). What about MDL ? Yes! There is one! (30,5).
Lets take another example!
A=[10,20,30,5,4,3,7,6,100,50]
MIL=[(10,20,30), (3,7) , (6,100)]
MDL=[(30,5,4,3), (7,6) (100,50)]
Look closely! In both these examples, the first element if MDL was the last element of MIL and vice versa!! This is a very big hint to solve the problem, which will be more clear when we look at the proof below.
Let me try to prove that MIL and MDL alternate.
Say my current MIL was from [L_1,R_1] and the next MIL is from [L_2,R_2].
We know that L_2 > R_1 else both the sequences intersect which violates the condition (that these 2 are maximal. Why?)
Now, look at A_{R_1+1}. Clearly A_{R_1+1} < A_{R_1} else it’d also be a part of the MIL. But if that is so, then (A_{R_1},A_{R_1+1}) make a decreasing sequence. Now, we also know that all elements are distinct, so any sequence has to be either increasing or decreasing. But the next MIL starts from L_2, which means that all elements in range [R_1,L_2] (why?) must be decreasing - forming an MDL between two MIL.
A similar proof can be done to prove that even MIL occurs between two MDL's by exact same argument.
This concludes that MIL and MDL's alternate!
Wrapping up the Solution and Final Answer
Now we know that MIL and MDL alternate. So, how does this help in the answer?
Easy! Each MIL will be followed by an MDL and vice versa. Say our query is [L,R]. Now-
- If the elements A_L and A_{L+1} form an MIL, then for answer to be
YES
, elements at A_{R-1} and A_R must form an MDL. This is because since MIL and MDL alternate, we can prove that if A_{R-1} and A_R form an MIL again, then there are odd number of maximal sequences and hence MIL and MDL cannot be equal! - If the elements A_L and A_{L+1} form an MDL, then for answer to be
YES
, elements at A_{R-1} and A_R form an MIL.
The above went over your head? Do not worry, there is an easier way to understand it!
In our range, the sequences will occur like [MIL,MDL,MIL,MDL,MIL,MDL] or [MDL,MIL,MDL,MIL,MDL,MIL,...]. Its easy to see that if the type of sequences at endpoints of range are different, then there are an even number of sequences (and hence equal MIL and MDL), else its not the case!
Now all that is left is to code it and get that much deserved \color{lightgreen}AC
SOLUTION
Setter
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int isincreasing(int a,int b){
if(a<b)
return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<int> v(n+1);
for(int i = 1;i <= n ;i++)
cin >> v[i];
while(q--){
int l, r;
cin >> l >> r;
int counts = 0;
counts += isincreasing(v[l],v[l+1]); //check if l and l+1 is increasing or decreasing
counts += isincreasing(v[r-1],v[r]); ////check if r-1 and r is increasing or decreasing
if(counts == 1) // if strictly one of the above is increasing and one is decreasing
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
Tester
#include <iostream>
#include <stdio.h>
using namespace std;
int n,q;
int a[500111];
int main()
{
int i,j;
scanf("%d %d",&n,&q);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for (i=1;i<=q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
if ( (a[l] < a[l+1]) != (a[r-1] < a[r]) )
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
Time Complexity=O(N+Q)
Space Complexity=O(N)
CHEF VIJJU’S CORNER
Why 2 MIL or MDL cannot intersect
They violate condition 2 and 3! We can just take the union and obtain an even larger MIL/MDL which meant our original sequences weren’t MIL/MDL - a contradiction.
Proof - Why all elements in range (R1,L2), both inclusive, are MDL instead of (R1,L2-1)
Recall the observation about last element of MDL being first element of MIL!
- Solve the problem under following constraints-
- If the elements are no longer distinct. Is the problem solvable in Polynomial time? If yes, suggest an algorithm. If not, prove why.
- Lets say elements are no longer distinct, and in MDL and MIL, elements being equal is allowed. Meaning in MIL, A_i \leq A_{i+1} and in MDL A_i \geq A_{i+1}. Does your previous algo (if any) work? Is this problem solvable? Does setter’s observation of alternating MDL and MIL hold?
- Point out any 1 critical inconsistency in above problem.
Hint for last part
Lets say my sequence has all equal elements, eg - [3,3,3]. Now, is this an MDL or MIL or both?! Does it make sense for a sequence to be both MDL and MIL ?
Setter's Notes
- For any given array, No. of increasing and decreasing sequences will differ by at most 1 because they alternately increase or decrease which keeps the difference \leq 1.
- If the start and the end of the array are opposite to each other i.e. [one increasing and other decreasing], then the No. of increasing and decreasing sequences will be equal else differ by 1.
For example, let A=[10, 20, 30, 40, 50, 49, 48, 47, 46, 100, 200, 300]
- It increases from 10 to 50
- Then decreases from 50 to 46
- Then increases from 46 to 300
Solution:
Check [L, L+1] and [R-1, R], if one is increasing and other is decreasing print “Yes” else print “No”
Related Problems
- Beautiful Garland - Observation
- MATDYS - Observation
- Forced Particles - Observation