@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 
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.
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 
doesnt it give tle
Easy to understand implementation of first approach (accepted code).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n,Q;
cin >> n >> Q;
ll a[n],b[n];
for(int i = 0; i<n; i++)
cin >> a[i];
for(int i = 0; i<n; i++)
cin >> b[i];
sort(a,a+n);
sort(b,b+n);
priority_queue <ll> pq;
for(ll i = 0; i<n; i++)
{
for(ll j = 0; j<n; 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;
}
}
vector <ll> ans;
while(!pq.empty())
{
ans.emplace_back(pq.top());
pq.pop();
}
reverse(ans.begin(), ans.end());
while(Q--)
{
int q;
cin >> q;
cout << ans[q-1] <<endl;
}
}
return 0;
}It’s a very elegant problem. My solution executed in 0.04 seconds. The key to solving it is:
1 ≤ qi ( for i = 1 to Q ) ≤ 10000
This means NO query will be for something greater than 10000 position. Note, it is possible to generate 20000*20000 = 400000000 possible values. We are only interested in the first 10000 or so.
So here is how we proceed.
Step 1: Sort both Inputs.
Step 2: What is the minimum possible number that can be generated - A[0] +B[0]. Max is A[n-1]+B[n-1].
Step 3: Now for a given sum S, try to binary search down the possible ways to generate a number below it. So if we are trying to generate the number 100 or lesser, and the first five elements of array A are 10, 20, 30, 40, 50… we can find out the number of elements in array B less than 90,80,70,60 etc. Add these counts. The moment this count exceeds 10000, we can safely say that “100” is too large and lower our search range.
Step 4: Based on above analysis, let us say we have narrowed down 60 that produces over 10000 numbers - but not MUCH more than that. So now go ahead and generate those 10000 numbers and store them ina vector.
Step 5. Do offline queries to get answers.
Operative part of code below:
#define int long long int
pair<int,int> number_elements(int A[], int B[], int n, int qry, int targ, int old_targ)
{
int ans = 0;
int A_lt = lower_bound(A, A+n, targ) - A;
for (int i = 0; i < A_lt; ++i)
{
ans += lower_bound(B, B+n, targ-A[i]) - B;
if(ans > qry)
{
return (number_elements(A, B, n, qry, targ/2, targ));
break;
}
}
return(make_pair(targ, old_targ));
}
vector<int> enumerate_solve(int A[], int B[], int n, int targ, int qry)
{
vector<int> ans;
for(int i = 0; i < n; ++i)
{
if(A[i] > targ)
{
break;
}
for(int j = 0; j <n ; ++j)
{
if(A[i]+B[j] <= targ)
{
ans.push_back(A[i]+B[j]);
}
else
{
break;
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
vector<int> solve(int A[], int B[], int n, int qry)
{
int minv = A[0] + B[0];
int maxv = A[n-1] + B[n-1];
int midv = minv + (maxv-minv)/2;
pair<int,int> ans = number_elements(A, B, n, qry, maxv, maxv);
return(enumerate_solve(A, B, n, ans.ss, qry));
}
int32_t main()
{
kpr; int t; cin >> t;
while(t--)
{
int k, q; cin >> k >> q; int A[k], B[k];
for (int i = 0; i < k; ++i)
{
cin >> A[i];
}
for (int i = 0; i < k; ++i)
{
cin >> B[i];
}
sort(A, A+k); sort(B, B+k);
int queries[q];
int maxQ = 0;
for (int i = 0; i < q; ++i)
{
cin >> queries[i];
maxQ = max(maxQ, queries[i]);
}
vector<int> precomp = solve(A, B, k, maxQ);
for (int i = 0; i < q; ++i)
{
print(precomp[queries[i]-1]);
}
}
return 0;
}
6 Likes