Hello sir
I am doing this question from codeforces.https://codeforces.com/problemset/problem/1284/B
Not able to do this question.Please recommend me something on this.Thanks.
Not able to get logic
Hey @ashishnnnnn look this explanation
Define a non-increasing sequence to be a sequence where ai≥ai+1ai≥ai+1 for all ii. A sequence does not contain an ascent if and only if it is a non-increasing sequence. Thus, we want to count the number of pairs of sequence whose concatenation is not a non-increasing sequence.
If cc is the number of pairs whose concatenation is a non-increasing sequence, the answer is therefore n2−cn2−c. We will focus on computing cc.
If a given sequence is not a non-increasing sequence, concatenating it with another sequence does not change this property. Thus, we will only consider merging two non-increasing sequences.
For non-increasing sequences s,ts,t to be mergeable as a non-increasing sequence, the last element of ss must not be smaller the first element of tt. For all given non-increasing sequence, let’s denote fi,ljfi,lj to be the first/last element of the respective sequence, we want to count the number of pairs 1≤i,j≤n1≤i,j≤n such that li≥fjli≥fj.
Counting this can be done in numerous ways. One way is to sort the sequence ff, and do a binary search for each lili to find how many elements are at most lili. The time complexity of this is O(nlogn)O(nlogn).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.