LOWSUM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang

DIFFICULTY:

EASY

PREREQUISITES:

Sort, Priority Queue, Binary Search

PROBLEM:

Given two arrays A[1…K], B[1…K], deal with Q queries of finding the n-th smallest pair sum in all K^2 pair sums (A[i] + B[j]).

EXPLANATION:

A brute force enumeration can give us an O(K^2 logK) - O(1) algorithm: just simply store all possible sums and use the some sorting algorithm such as quick sort. And then, for each query, return the n-th number of the stored sorted array. This brute force algortihm’s time complexity is O(K^2 + Q). Also, it needs O(K^2) space. Both time and memory are exceeded.

There are 2 ways to improve this brute force algorithm. The common key point to improve this brute force algorithm is as following: Suppose A[] and B[] are sorted ascendingly, A[i] + B[j] is smaller than or equal to any A[i] + B[k] if k > j.

For instance, we use quick sort to sort A[] and B[] in O(K logK) time. And then, 2 possible solutions are here.

The first solution is that we can find the smallest sum among at most K candidates (one for each A[i]) and remove it. After n removes, the n-th smallest sum is found. More specifically, we can maintain K pointers for each A[i]. Let’s say ptr[1…K] (equals 1 initially). First, we can use a binary heap (or other priority queues, balanced binary search trees, etc…) to find the smallest sum among A[i] + B[ptr[i]]. Second, suppose the smallest is A[p] + B[ptr[p]]. We remove it from the heap, then increase the pointer ptr[p] by 1 and insert a new element A[p] + B[ptr[p]] if it exists. Repeat this process n times, the n-th smallest sum is got. This algorithm’s time complexity is O(n log K) for each query, and thus O(K logK + Q n logK) in total.

The second solution is more tricky and useful. Consider the dual problem: given a number X, find how many pair sums are smaller than or equal to X (The answer of the original problem is that the smallest X such that there are at least n pair sums smaller than or equal to X). To solve the dual problem, based on the previous observation, there exists limit[i] such that A[i] + B[1…limit[i]] are all smaller than or equal to X while A[i] + B[limit[i] + 1 … K] are all greater than X. Furthermore, limit[i] >= limit[i + 1] since A[i] <= A[i + 1]. Using these two properties, we can simply get the rank of X in O(K) time. Through binary search, we can get the answer of original problem in O(K logAnswer), and thus O(K logK + Q K logAnswer) in total.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

7 Likes

Hmm, I tried both approach in the contest. However, only the first one get AC (CodeChef: Practical coding for everyone ). The second solution gave me TLE (CodeChef: Practical coding for everyone ). Is the time limit too strict for the second solution or it is just me that didn’t implement the algorithm efficiently?

1 Like

@arcturus I used binary search to search for X and then binary search to count the pairs, but also a trick (when count exceeds 10.000 break, since qi is maximum 10.000). Without the trick it gave TLE.

4 Likes

I solved this after the contest and used a very simple approach. First sort both the arrays. Since the limit on q is 10000, this can be done with the following code.

    for(j=1;j<=n;++j)
    {
      k=10001/j;
      ind=min(k,n);
      num=a[j];
      for(k=1;k<=ind;++k)
           v.pb(num+b[k]);
    }

This will ensure that atleast the first 10000 sums will be stored in v.
Then we just have to sort the vector v and print the answer of every query.

5 Likes

can anybody please explain me the first approach?
not getting it :frowning:

2 Likes

though editorial has been provided for this problem but still i am not able to understand it.
it would be great if someone explain me the correct approach to solve this problem…

3 Likes

I’m getting wrong answer for this solution. Can someone help me out?
http://www.codechef.com/viewsolution/3718821

Why am i getting NZEC? My approach is based on solution 2 - https://www.codechef.com/viewsolution/20452934

Ah, I see. But I guess if the testcase was really evil, the second solution will also get TLE even with that trick. Probably it was not the intended way, as both tester and setter used the first approach.

1 Like

can u please explain me ur approach?

well,i am requesting again especially to the editorialist of this problem to explain his solution given above…

@sikander_nsit please explain your solution more. It would be great for us to get a solution which is very simple and sweet.

Thanks,

your trick is great …

can you give proof of correctness of your algo…please??

Where am I doing wrong in my solution? CodeChef: Practical coding for everyone
I am not able to follow up the approach in editorial. Can anyone explain it in more elegant manner.

https://www.codechef.com/viewsolution/27193268
can anyone explain me ???

Easy and better to understand

// Created by Manmeet Singh Parmar
// name of snippet-> temp.sublime-snippet
// path -> sublime text 3/packages/user/temp.sublime-snippet

#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;

#define FOR(i, n)  for(int i=0; i<(n); i++)
#define FORA(i, a, n) for(int i = a; i <= (n); ++i)
#define FORD(i, a, n) for(int i = a; i >= (n); --i);
#define mod 1000000007
#define pi 2acos(0.0)
#define MP make_pair
#define PB push_back
#define EB emplace_back // its's faster than push_back
#define F first
#define S second
#define sz(x) (int)(x).size()
#define what_is(x) cerr << #x << "is" << x << endl;
#define gcd(a, b) __gcd(num1 , num2)

int32_t main()
{
   	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin>>t;
    while(t--){
    	int k,q;
        cin>>k>>q;
        vi A(k), B(k);
        FOR(i,k) cin >> A[i];
        FOR(i,k) cin >> B[i];
        sort(A.begin(), A.end());
        sort(B.begin(), B.end());
        vi ans;
        priority_queue<int> pq;
        for(int i=0; i<k; i++) {
        	for(int j=0; j<k; j++) {
        		if(pq.size() < 10000) {
        			pq.push(A[i]+B[j]);
        		}
        		else if(A[i]+B[j] < pq.top()) {
        			pq.pop();
        			pq.push(A[i]+B[j]);
        		}
        		else
        			break;
        	}
        }
        while(!pq.empty()) {
        	ans.push_back(pq.top());
        	pq.pop();
        }
        reverse(ans.begin(),ans.end());
        int idx;        
        while(q--) {
        	cin >>idx;
        	cout <<ans[idx-1]<<'\n'; 
        }
    }
    return 0;
}
6 Likes

It is a simple implementation of priority queue. priority_queue<ll, pair<ll,ll>>pq.
-> Use long long int
->maintain a priority queue, with first element as sum
-> refer this code

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t–)
{
ll n,q;
cin>>n>>q;
ll a[n];
ll b[n];
for(ll i=0;i<n;i++)
{
cin>>a[i];
}

for(ll i=0;i<n;i++)
{
  cin>>b[i];
}
sort(a,a+n);
sort(b,b+n);
vector<ll> final;
priority_queue<pair<ll,pair<ll,ll> >> pq;  // (a,(b,c))-->a for priority, b for a[i] and c for b[i];
for(ll i=0;i<n;i++)
{
  ll jod=a[i]+b[0];
  pq.push({-jod,{i,0}});
}

while(final.size()!=10000 && !pq.empty())
{
  pair<ll,pair<ll,ll> > g= pq.top();
  //cout<<g.first<<endl;
  final.push_back(g.first);
  pq.pop();
  if(g.second.second==n-1)
  {
    //continue;
  }
  else
  {
    g.second.second+=1;
    g.first= -(a[g.second.first]+b[g.second.second]);
    pq.push(g);
  }

}

while(q--)
{
  ll value;
  cin>>value;
  cout<<-final[value-1]<<endl;
}

}
}

just awesome man !! thank u helped me out :wink:

Simple Java Solution
click to view my solution

doesnt it give tle