PROBLEM LINK:
Author: Vamsi Kavala
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Getting rid of the storyline and special input format, the problem can be formulated as follows. You are given an array A[1], …, A[N] and a number C. Denote osc[i, j] = max(A[i], …, A[j]) − min(A[i], …, A[j]) (osc is due to oscillation). Further, denote by F[k], where 1 ≤ k ≤ N, the number of those i from 1 to N − k + 1 for which osc[i, i + k − 1] ≤ C. You are also given several values of M. For each of these values you need to find the smallest k such that F[k] ≤ M and the corresponding value F[k].
QUICK EXPLANATION:
Denote by beg[i], where 1 ≤ i ≤ N, the smallest positive number for which osc[beg[i], i] ≤ C. Values beg[i] can be found in O(N) using two deques like in sliding RMQ. Denote by cnt[j] the number of those i for which i − beg[i] + 1 = j. Then, F[k] = cnt[k] + … + cnt[N]. After that the queries can be answered in O(log N) time using binary search. Alternatively one can compute answers for all queries in O(N) time and answer them in O(1) time after that.
EXPLANATION:
Note, that if the segment [i<sub>1</sub>, j<sub>1</sub>] lies inside the segment [i<sub>2</sub>, j<sub>2</sub>], that is, i2 ≤ i1 ≤ j1 ≤ j2, then osc[i<sub>1</sub>, j<sub>1</sub>] ≤ osc[i<sub>2</sub>, j<sub>2</sub>]. Hence beg[i] ≤ beg[i +1]. Indeed, if beg[i] > beg[i +1] then osc[beg[i +1], i] ≤ osc[beg[i +1], i + 1] ≤ C. So beg[i] is not the smallest index satisfying the property osc[j, i] ≤ C.
It allows us to use the following method to find beg[i] for all i. Initially we have beg[1] = 1. Consider some i > 1 and assume that beg[i − 1] is already found. Then we move the index j starting from beg[i − 1] forward and check the condition osc[j, i] ≤ C. We assign beg[i] = j for the first index j which satisfies this condition. It is clear, that the total number of checks we perform is O(N). So with naive check of condition osc[j, i] ≤ C we obtain O(N * N) solution.
To obtain an O(N) solution we need data structure that allows to answer the following queries in O(1) time in average. We have two pointers j and i. At each time we can either increase i by one, increase j by one (but only if j was less than i), or need to find minimum and maximum among the numbers A[j], …, A[i]. In average here means that Q such queries can be answered in O(Q) time. Then the previous solution can be represented by the following pseudo-code
i = 1
j = 1
while i <= N
while osc[j, i] <= C // query of the 3rd type
increase j by 1 // query of the 2nd type
assign beg[i] = j
increase i by 1 // query of the 1st type
The proper data structure for this is two deques minQ and maxQ of successive minimums and maximums in the sequence A[i], A[i − 1], …, A[j]. Namely, the head element minQ[1] of minQ will be i, the second element minQ[2] will be the largest index h < i such that A[h] < A[i]. In general minQ[k] is the largest positive integer h < minQ[k − 1] such that A[h] < A[minQ[k − 1]]. For the last (tail) element of minQ there will be no such h ≥ j. Note, that minQ can contain only one element i in some situations. The deque maxQ is defined in a similar way.
We will use C++ syntax for standard deque operations (see here).
The queries can be implemented now as follows. We consider only how minQ will be affected. maxQ will be changed in a similar way.
For the first query (increase i by one) we should possibly remove first several elements in minQ until the condition A[minQ[1]] < A[i] will be satisfied and after that make i as a head element:
query1()
i = i + 1
while minQ is non-empty and A[minQ.front()] ≥ A[i]
minQ.pop_front()
minQ.push_front(i)
For the second query (increase j by one) we should simply remove the last element if it coincides with j:
query2()
if minQ.back() = j then
minQ.pop_back()
j = j + 1
Finally, for the third query (take minimum) we need to take the last element of minQ:
query3()
return A[minQ.back()]
It seems that such solution can have complexity O(N * Q) for answering Q queries due to the loop in the query1() but it is easy to see that since we always increase either i or j, we add and delete each index from 1 to N at most once in our deques. So the total number of operations performed in these loops during all queries is at most 2 * N.
Alternatively you can check CHEFTOWN - editorial or this article for another exposition of this method.
Now when we find beg[i] for all i we can find cnt[k] for all k in one simple loop after proper initialization:
for k = 1 to N do
cnt[k] = 0
for i = 1 to N do
increase cnt[i – beg[i] + 1] by 1
Clearly, F[k] is the number of those i for which osc[i − k + 1, i] ≤ C. Due to definition of beg[i] this is equivalent to beg[i] ≤ i − k + 1 or i − beg[i] +1 ≥ k. Clearly, the number of such i equals to cnt[k] + … + cnt[N]. Hence F[k] = cnt[k] + … + cnt[N] = cnt[k] + F[k + 1] and can be found in one simple loop:
F[N] = cnt[N]
for k = N – 1 downto 1
F[k] = cnt[k] + F[k + 1]
As was mentioned, now to answer the queries we can either use binary search (see author’s solution) or compute all answers in O(N) time and answer the queries in O(1) time (see tester’s solution).
ALTERNATIVE SOLUTION:
Instead of using deques that we discuss above, which may appear to be quite unusual for many of you, some more standard data structures can be used.
For example, balanced binary search tree allows to perform each query in O(log N) time. So we get O(N * log N) solution. Namely, now query1() is inserting the pair (A[i], i) into the tree, query2() is deleting the pair (A[j], j) from the tree and query3() as before is finding of minimum of maximum. It shouldn’t pass within the time limit but some contestants cram it after proper optimizations. You can use STL set in C++ or TreeSet in Java as a ready to use implemented balanced binary search tree.
Another approach is to use segment tree. It can be constructed in O(N) time, needs O(N) memory and allows to find minimum or maximum on the segment in O(log N) time. So our main pseudo-code for the solution remains the same but each osc[j, i] will require O(log N) time. The entire solution will have a complexity O(N * log N) and shouldn’t pass the time limit. But again, after proper optimizations maybe it is possible to cram it within the time limit.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
RELATED PROBLEMS:
CHEFTOWN
SPOJ - 7739. Sound - BOI7SOU
Timus - 1126. Magnetic Storms
UESTC - 1221. Sliding Window
