Can anybody please explain this? (LOWSUM)

general
, ,
1

Here’s the problem CodeChef: Practical coding for everyone
I have gone through the editorial (and the hints) and I do understand the method provided over their, “count the pairs with sum less than or equal to X, then binary search over all the X for which the count of pairs is less than the one asked in the query”. But the problem is that I don’t understand how to choose those X’s and implement this idea. Can anybody please help?

2
My Commented code 
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
void solve(){
    int n, Q;
    cin>>n>>Q;
    vector<ll> seq1(n);
    vector<ll> seq2(n);
    for(auto &x : seq1){
        cin>>x;
    }
    for(auto &x : seq2){
        cin>>x;
    }
    sort(seq1.begin(), seq1.end());//Sort the sequences.
    sort(seq2.begin(), seq2.end());
    const int MAXQ = 10007;
    ll mn=0, mx=2e18 + 7;
    while(mn<mx){//Binary search for a sum that has MAXQ pairs less than it.
        ll ans=0;
        ll mid= mn + ((mx - mn + 1)>>1); 
        for(int i=0,j=n-1;i<n;i++){
            //Using two pointers to calculate the number
            //of values less than mid when first term is seq1[i]
            while(j>=0 && seq1[i] + seq2[j]>mid){
                --j;
            }
            ans+=j+1;
        }
        if(ans>MAXQ){
            mx=mid-1;
        }
        else{
            mn=mid;
        }
    }
    ll ans=mn;
    vector<ll> sums;
    //Now store all the sums less than our answer from the binary search
    for(int i=0, j=n-1;i<n;i++){
        //Using the same two pointers
        while(j>=0 && seq1[i] + seq2[j]>ans){
            --j;
        }
        for(int k=0;k<=j;k++){
            //We know that only these sums are less than ans
            //And they don't exceed MAXQ in number 
            sums.pb(seq1[i] + seq2[k]);
        }        
    }
    sort(sums.begin(), sums.end());
    //Ths sums may not neccesarily be sorted
    while(Q--){
        int q;
        cin>>q;
        cout<<sums[q-1]<<'\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
1 Like