You are not logged in. Please login at www.codechef.com to post your questions!

×

SEAD - Editorial

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

kostya_by's gravatar image

6★kostya_by ♦♦
166143235
accept rate: 0%

edited 17 Apr '14, 17:03

Both the tester's and setter's solution are exactly same? Btw... Excellent editorial :)

(24 Feb '14, 19:03) logic_max5★

Could you please explain the complexity of the sparse table and the final complexity of the solution?

link

answered 23 Feb '14, 17:19

epsilon_0's gravatar image

2★epsilon_0
4527
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) kostya_by ♦♦6★

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) epsilon_02★

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) epsilon_02★

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

link

answered 23 Feb '14, 18:26

ahmed1ossama13's gravatar image

5★ahmed1ossama13
21218
accept rate: 0%

O(N M log N) is too much to get AC.

(23 Feb '14, 19:22) kostya_by ♦♦6★

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) ahmed1ossama135★

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) logic_max5★

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) ahmed1ossama135★

Nice Article !!!! Awesome

link

answered 23 Feb '14, 22:13

sp1rs's gravatar image

2★sp1rs
96351327
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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