TEAMSIZE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vamsi Kavala
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Sliding RMQ, Deque

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

5 Likes

I saw the question as two parts :

  1. Its a sliding window type question in which I have to first select the window sequentially

  2. Determine if there are any duplicates in the selected window and if there are no duplicates then perform minimum and maximum queries…

So for solving the problem I implemented Segmented tree http://www.codechef.com/viewsolution/1475504(TLE and it works for cases with unique skills)

So by implementing segment tree I solved the 2nd part of the question i.e to get the min and max of sliding window…
But I could not figure out the first part…i.e. how to detect duplicate elements in that sliding window…

I have two questions here :

  1. Can anyone tell me how to figure out the duplicate element part in segment tree?
  2. Was my approach wrong…should I have implemented dequeues only(i.e. to solve this particular question)??

Another similar problem :
http://www.acm.uestc.edu.cn/problem.php?pid=1221

2 Likes

Thanks. I have added it.

Hey…answer my query too!!

I don’t understand why you worry about duplicates. Having duplicates is fine. Equal skills do not mean coincidence of cooks. As for the second part, this statement “For each Qth integer(m[Q]) we know that the teamsize varies from 1 to m[Q]” is wrong. In fact team-size varies from 1 to N-m[i]+1 and definitely it is too slow to answer queries by brute force. Your solution now has complexity O(N^2 * log N) which is completely inappropriate for this problem.

1 Like

@anton_lunyov )) thanx…now I got the blunder mistake.

I liked the problem, and when I read the editorial it could have been my code (except for how I solve the queries, in O(N + Q log Q)). But I didn’t got accepted, I must have been forgotten something, is there a way to see for which testcases my code fails?
http://www.codechef.com/viewsolution/1474796
txs in advance

I managed to get my solution to pass using STL mustiset (basically heaps). Thats O(NlogN) time. I had earlier tried using segment trees, but that NlogN failed, no matter how much I tried to optimize. Good job on making testcases differentiate (atleast somewhat) between N and NlogN :slight_smile:

And the sliding RMQ technique was definitely new to me, so thanks for the editorial and the link :slight_smile: [can’t wait to try it out now …]

//