Problem QPAIR

darkshadows · September 25, 2015, 11:52pm

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.

AUTHOR’S & EDITORIALIST’S SOLUTIONS:

Setter

Editorialist

darkshadows · September 25, 2015, 11:53pm

"Here’s my idea using offline queries:

Sort both A and B array and store two sorted arrays of pair <value,position in original array> for A and B.
Lets say A2 and B2 array.
For every query, use binary search to find position with value just greater than X_i and Y_i in A2 and B2 respectively. Lets say p1 and p2.
Store these p1 and p2 in a new Qarray and sort it by p1 and p2 .Now p1 and p2 denotes a query.
Use two sets for storing positions in A2 and B2(initially empty).
5)Keep 2 pointers I and J initially at N+1.
Process Qarray from reverse direction . If current query is p1 and p2, decrement I and J until they become p1 and p2… and keep adding the respective positions to the sets and keep updating answer(keep minimum A_j+B_j).

I think Medium is appropriate for the problem.
I would like to be tester for this problem if my approach is correct "

-Abhinav

darkshadows · September 26, 2015, 12:00am

My solution is using offline queries. First sort A,B according to A and X,Y according to X. Then start solving queries and inserting (A_i, B_i) in a DS such that while answering $i$’th query, this DS contains all pairs from A, B such that X_i >= A_i. For query, we have to find a value k such that k >= Y_i and there exists a pair (val, k) in A-B and (k+val) is minimum. So, we need range min query and point update.

Can also be solved using Manhattan MST. See here https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/
Level: Medium to Medium-Hard

adurysk · September 28, 2015, 1:59am

I think this can be solved ONLINE using persistant segment trees, will post my solution tomorrow

darkshadows · October 1, 2015, 2:42pm

Test generation plan.

Type1(N, Q):
N Random points, Q random queries.

Type2(N, Q):
    //basic idea is that if someone sorts on basis of x and then applies linear search
    //should time about
    choose N x-coordinates
    sort them
    for last N/10 points give y-coordinate very low
    for all others give y-coordinate high

    Q queries with low x-coordinates and low y-coordinates.

Type3(N, Q):
    simlar to type2 except that roles of x and y are changed

animesh_f · November 28, 2015, 5:10pm

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.

AUTHOR’S & EDITORIALIST’S SOLUTIONS:

Setter

Editorialist