SEAD - Editorial

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

4 Likes

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

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

Nice Article !!! Awesome

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 ).

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

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?

Sorry. I read the below comment and see that O((N+M)(log n)^2) would work if O(NM(log n)) worked. :stuck_out_tongue:

Well, Is there anything with my complexity analysis for the solution, or with the test cases were not strong enough?

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.

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.

Both the tester’s and setter’s solution are exactly same?
Btw… Excellent editorial :slight_smile:

why at last u did ans+2 in output??

For each query:
Getting R: logN
Checking G(X) and getting L : logN
Total Queries: M
TC for Sparse Table: NlogN

Total Complexity: NlogN + M(logN + logN) = (N+2M)logN