QPAIR - Editorial

animesh_f · November 29, 2015, 4:00am

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Editorialist: Animesh Fatehpuria

DIFFICULTY:

Medium

PREREQUISITES:

Segment Tree

PROBLEM:

Given a sequence P of N pairs of integers and Q queries of the form (a , b) : For each query find an index i in P[] such that P[i].first \ge a , P[i].second \ge b and P[i].first - a + P[i].second - b is minimised. If there exists multiple options print the one which minimises i. If no such indices exist, print -1.

N,Q \le 10^5.
P[i],a,b \le 10^9.

QUICK EXPLANATION:

======================
We process the queries offline. We store all the Q queries in a list and sort the list in descending order of “a” value. Similarly, we sort the array P[] in descending order of P[i].first. We process the queries in the defined order and maintain a segment tree which considers all the indices such that. P[i].first \ge a. Whenever we process a query (a,b), we would have already updated all the indices whose P[i].first \ge a in the segment tree. Now just do a range minimum query for the range [b,10^9] to look for the index which minimises P[i].first + P[i].second.

EXPLANATION:

================

Let us first observe the function we are trying to minimise.
For each query, we need to minimise P[i].first - a + P[i].second - b, and also follow the constraints mentioned on P[i].
It is easy to notice that a,b are constant for each query, so we can rewrite the function as (P[i].first + P[i].second) - ( a + b ).
Now we can see that we just have to minimise P[i].first + P[i].second.

Observe that there are no updates on P. We can use this to re-order the queries in a way which makes our job easier.
According to the question, we must consider only those indices i such that P[i].first \ge a and P[i].second \ge b, and then
try to minimise their sum. Let’s try to get rid of P[i].first \ge a. We can do this by sorting the queries in descending order
of a and sorting the array P[] in descending order of P[i].first. We process the queries in this changed order and maintain
a segment tree. Whenever we process a query (a,b), we would have already updated all the indices whose P[i].first \ge a in the segment tree.
I’ll describe how to implement the segment tree in the next paragraph.

Assume we have done this successfully. Our task now is to find an index i such that P[i].second \ge b and out of all the options that we have, we need to choose the one which minimises P[i].first + P[i].second. In case of ties, we need to pick the one with the lowest index.
We can manage this by implementing a segment tree ordered by P[i].second in which each node( corresponding to [L,R] ) stores the following things:

The best index in that range.
sum = P[index].first + P[index].second.

How will we merge two nodes? The answer to this question lies simply in the function we want to minimise. Our first priority is to minimise P[index].first + P[index].second. After that, we need to try to minimise index. Therefore, our merge function will look something like this:

 // Merges left child and right child

 node merge( node left , node right ):
      if( left.sum < right.sum )
           return left;
      else if( right.sum < left.sum )
           return right;
      else:  // Minimise index
           if( left.index < right.index )
                return left;
           return right;

The answer to each query is now the best index in the range [b,10^9].

We need to handle one more thing. The values can be as large as 10^9, so we can’t implement a segment tree naively. We have two choices here:

Compress the values to cover a smaller range i.e [1,N].
Implement an Implicit Segment Tree.

Either of these ways would suffice and pass easily within the time limits. The complexity of this solution would be \mathcal{O}(N\log{}N) or \mathcal{O}(N\log{}10^9) depending on which way you prefer.
For implementation and clarity, see setter’s and editorialist’s commented code.