ISBIAS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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 :smiley:

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
  1. 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.
  2. 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
23 Likes

I was thinking that this had to something to do with finding MILs and MDLs as quickly as possible, so started to explore things in that direction. I also thought that this could be DP related. Perhaps I store the solutions from other queries and use the previous queries somehow to find the solution to new queries. Sadly, I was wrong both times. But this is very enlightening. I don’t know why I tend to over-engineer and overthink when the solution is so simple. Thank you for the editorial.

Lesson that I learnt: Patience and observation is also part of programming skills.

17 Likes

After 2 days of efforts and dedication on solving problem lead me to the track of O(1) time query solution, I was surprised after finding the O(1) time query process how easy it is, and then submitted the solution immediatly. It got AC solution , I couldn’t control my happiness after 2 days of efforts with less than 10 lines of code and I was laughing on me, was so embarrassing :joy: .

n,q = map(int,input().split())
a = list(map(int,input().split()))
for _ in range(q):
    l,r = map(int,input().split())
    if (a[l-1]<a[l] and a[r-2]<a[r-1]) or (a[l-1]>a[l] and a[r-2]>a[r-1]):
        print('NO')
    else:
        print('YES')

26 Likes

Awesome editorial. So in-depth… Thanks…:smiley:

1 Like

what is the reason behind the size of array being 500111?
the input constriants have input size of 1e5.
thanks in advance.

Anything above 1e5 work.

Got to say the editorials this time are to comprehensive, and appreciated! :+1:

1 Like

For A = [30, 1, 3, 5, 4], L = 1 and R = 5. Your code gives “YES”, whereas it should be “NO”.

Also your code runs in O(N * N) whereas expected is much lower.

Ok thanks

Bro please help me… if the in put n=1,3,2,4,11,13,12,14,21,23,22,24 and L,R is 5,7… the range is 11,13,12… So let’s p as 13… the second conditions is Ap<Ap-1… How is this statement true here? 13 is not < 11… Please help

I almost made around 40 submissions to this problem :frowning: but helpful tq

Bro please help me… if the in put n=1,3,2,4,11,13,12,14,21,23,22,24 and L,R is 5,7… the range is 11,13,12… So let’s p as 13… the second conditions is Ap<Ap-1… How is this statement true here? 13 is not < 11… Please help

Same with me I worked on this problem for whole two days and then did it with DP …But now after seeing the editorial …I am like what the hell is this …It can be solved so simply…:stuck_out_tongue_winking_eye::stuck_out_tongue_winking_eye:

1 Like

This example fails for the first condition only.

It’s dangerous to think too much sometimes :laughing:

this problem makes me feel like an genuine idiot.
.Ughhhhhhhhh.
I am dumb.