×

 2 1 Problem Link: contest, practice Difficulty: Medium Pre-requisites: Binary Search, Sparse Tables, Segment Tree Problem: You are given ascending-sorted array A[], consisting of N integers. You are to calculate the answers for M queries of the following type: You are given two integers T and D. You should find the minimal integer L such that there is some integer R (L ≤ R) for which the following conditions are satisfied: A[L] + D >= A[L + 1], A[L + 1] + D >= A[L + 2], ... A[R - 1] + D >= A[R], A[R] <= T < A[R + 1] (we assume, that A[N + 1] is infinitely big). Explanation: The first observation, that we should make, is that there is the only R for each query (T, D), that could satisfy to the conditions from the statement. It isn't hard to be sure about that. As far as A[] is an ascending-sorted array, let's define R as the largest integer, such that A[R] <= T. Then T is less than A[R + 1](otherwise R is not the largest integer that we are looking for). Please, note that as far as A[1] <= T, such R always exists. How to find R efficiently? We can use a binary search! Here is a pseudocode, that shows the implementation of the algorithm of searching R. R = 1 LEFT_BOUND = 2 RIGHT_BOUND = N while ( LEFT_BOUND <= RIGHT_BOUND ) begin MID = (LEFT_BOUND + RIGHT_BOUND) / 2 if ( A[ MID ] <= T ) begin R = MID LEFT_BOUND = MID + 1 end else begin RIGHT_BOUND = MID - 1 end end  This subtask works in O( log N ) time. OK, now we know how to find R. But we were asked to find L, not R. So, let's do it. Firstly, let's fix R. We already know, that it's unique for each query and there is no way to choose another R, so we need to adapt L under R. Let's understand, that if L = R, then the conditions from the statement are satisfied. The problem is that R may be not the minimal such L, that satisfies. On the other hand, we can observe, that if for L = X the conditions are satisfied, then for L = X + 1 the conditions are satisfied as well. More formally, let's consider boolean function G(X), 1 <= X <= R. G(X) is true if and only if the conditions are satisfied for L = X, otherwise it's false. This function is monotone. Here is a pseudocode, that shows the implementation of the algorithm of searching L. L = R LEFT_BOUND = 1 RIGHT_BOUND = R - 1 while ( LEFT_BOUND <= RIGHT_BOUND ) begin MID = (LEFT_BOUND + RIGHT_BOUND) / 2 if ( G( MID ) == true ) begin L = MID RIGHT_BOUND = MID - 1 end else begin LEFT_BOUND = MID + 1 end end  This subtask works in O( log N * < complexity of calculation of G > ) time. So, the last subtask, that we should discuss, is how to calculate G efficiently. Firstly, let's forget about this condition: A[R] <= T < A[R + 1]. It doesn't play any role as far as R is fixed and has already satisfied to that condition. Let's assume, that we are calculating G(X) right now. What should we check? In order to make G(X) true, the following conditions must be satisfied: A[X] + D >= A[X + 1], A[X + 1] + D >= A[X + 2], ... A[R - 1] + D >= A[R]. Let's work a little bit with the inequalities. I.e. let's rewrite them in such a way, that D is the only summand to the right of the comparison sign: A[X + 1] - A[X] <= D, A[X + 2] - A[X + 1] <= D, ... A[R] - A[R - 1] <= D. Let's build up array B[], such that B[i] = A[i + 1] - A[i] for each 1 <= i < N. Then, B[X] <= D, B[X + 1] <= D, ... B[R - 1] <= D. We can finally rewrite the inequalities like: max( B[X], B[X + 1], ..., B[R - 1] ) <= D. Well, now it's quite a well-known problem. G(X) is true if and only if the maximal number of array B[] on the range [X, R - 1] is not greater than D. We can use a sparse table in order to answer this query efficiently. If you don't know sparse tables at all, don't be upset. The constraints in this problem are quite soft, you can use a simple segment tree. Nevertheless, the solution, which uses a sparse table instead of a segment tree, works much faster and has a better complexity. Here is a pseudocode, that shows the implementation of building up array B[] and making sparse table P[][] based on B[]. for i from 1 to N - 1 do begin B[i] = A[i + 1] - A[i] P[0][i] = B[i] end for power from 1 to CEILING( LOG_2( N - 1 ) ) do begin for i from 1 to N - 1 do begin if ( i + 2 ^ power - 1 <= N - 1 ) do begin P[ power ][ i ] = max( P[ power - 1 ][ i ], P[ power - 1 ][ i + 2 ^ ( power - 1 ) ] ) end end end  Here is a pseudocode, that shows the implementation of function G(). boolean function G(L) begin LEFT_BOUND = L RIGHT_BOUND = R - 1 (we assume, that variable R is global) LIMIT = D (we assume, that variable D is global too) POWER = FLOOR( LOG_2( RIGHT_BOUND - LEFT_BOUND + 1 ) ); MAX_VALUE = max( P[ POWER ][ LEFT_BOUND + 2 ^ POWER - 1 ], P[ POWER ][ RIGHT_BOUND - 2 ^ POWER + 1 ] ) if ( MAX_VALUE <= LIMIT ) do begin return true end return false end  The Tester and the Setter have another solution, which uses off-line processing of queries. If you are interested, you can check them out. Setter's Solution: link Tester's Solution: link This question is marked "community wiki". asked 23 Feb '14, 15:22 166●14●32●35 accept rate: 0% Both the tester's and setter's solution are exactly same? Btw... Excellent editorial :) (24 Feb '14, 19:03)

 0 Could you please explain the complexity of the sparse table and the final complexity of the solution? answered 23 Feb '14, 17:19 45●2●7 accept rate: 0% Well, we build up the sparse table in O( N * log N ) time. Then, each query we process in O(log N) time, since finding the maximal number on the range takes O(1) time. The total complexity is O( (N + M) log N ). (23 Feb '14, 17:30) Thank You. I suppose that if we implement a segment tree here with range max query then we would take O(log n) for G(X) as well and then the complexity would be O((N+M)(log n)^2). Would this work as well? (23 Feb '14, 19:26) Sorry. I read the below comment and see that O((N+M)(log n)^2) would work if O(NM(log n)) worked. :P (23 Feb '14, 19:27)
 0 My solution complexity was O(nmlogn) ... I wondered how it passed Precomputing step: Build an array B=[] where B[i]=A[i+1]-A[i] Also Build array MaxL[] ... where MaxL[i]=j where j is the largest index less than i, and B[j]>B[i] For each case: I used binary search to get R Then starting from from index R-1 I searched for the first index L where B[L]>D x=R-1 while(B[x]!=-1 && B[x]<=D) { x=MaxL[x]; }  this step has a complexity depending on the distribution of the numbers of B[] But in worst case scenario it is O(n) when B[] is in descending order So the total complexity is O(nmlogn) Here is the link to my submission: submission answered 23 Feb '14, 18:26 212●1●8 accept rate: 0% O(N M log N) is too much to get AC. (23 Feb '14, 19:22) Well, Is there anything with my complexity analysis for the solution, or with the test cases were not strong enough? (23 Feb '14, 19:57) My solution was also sub-optimal, worst case complexity would be O(N.M). I think that the tests are really weak and should be updated. (23 Feb '14, 21:17) Actually, the complexity of my solution turned out not to be O(nmlogn) ... because the length of the longest possible strictly decreasing sequence in array B[] is about 450 ... because there is a limit on the numbers of array A[] which is 10^6 ... So the complexity is not linear. If the limit on array A[] was 10^9 ... it would have timed out ... because the length of longest possible strictly decreasing sequence is in range of 14000. (23 Feb '14, 22:03)
 0 Nice Article !!!! Awesome answered 23 Feb '14, 22:13 2★sp1rs 963●5●13●27 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×12,344
×1,934
×1,279
×614
×27
×7

question asked: 23 Feb '14, 15:22

question was seen: 2,376 times

last updated: 17 Apr '14, 17:03