Help me in solving TRIPLETMIN problem. it is giving wa on submission

help
,
1

My issue

My code

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

int main() {
	// your code goes here
	int t ;
	cin>>t;
	while(t--){
	    int n ,q;
	    cin>>n>>q;
	    
	    vector<int>v(n);
	    for(int i=0;i<n;i++){
	        cin>>v[i];
	    }
	    vector<int>queries(q);
	    for(int i =0;i<q;i++){
	        int x;
	        cin>>x;
	        queries[i] = x;
	    }
	    sort(v.begin(),v.end());
	    vector<int>tmp(n);
	     for(int i =0;i<n;i++){
	        tmp[i] = ((n-i-1)*(n-i-2))/2;
	        if(i!=0){
	            tmp[i] = tmp[i] + tmp[i-1];
	        }
	    }
	    for(int j =0;j<q;j++){
	    int ind = lower_bound(tmp.begin(),tmp.end(),queries[j]) - tmp.begin();
	    cout<<v[ind]<<endl;
	    }
	}
	return 0;
}

Problem Link: TRIPLETMIN Problem - CodeChef

2

Hey you made a similar error to what I did.

You need to declare n of type long long as the line :
"tmp[i] = ((n-i-1)(n-i-2))/2;"
can actually lead to very larger numbers (n is 10^5 and hence n^2 = 10^10)
If n is int then (n-i-1)(n-i-2) can lead to an overflow.

For the same reason tmp also has to be declared as long long.

Since K is NC3, queries also has to be made long long.

After making all these changes in your code, I got an AC.

using namespace std;

int main() {
	// your code goes here
	int t ;
	cin>>t;
	while(t--){
	    long long n ,q;
	    cin>>n>>q;
	    
	    vector<int>v(n);
	    for(int i=0;i<n;i++){
	        cin>>v[i];
	    }
	    vector<long long>queries(q);
	    for(int i =0;i<q;i++){
	        long long x;
	        cin>>x;
	        queries[i] = x;
	    }
	    sort(v.begin(),v.end());
	    vector<long long>tmp(n);
	     for(int i =0;i<n;i++){
	        tmp[i] = ((n-i-1)*(n-i-2))/2;
	        if(i!=0){
	            tmp[i] = tmp[i] + tmp[i-1];
	        }
	    }
	    for(int j =0;j<q;j++){
	    int ind = lower_bound(tmp.begin(),tmp.end(),queries[j]) - tmp.begin();
	    cout<<v[ind]<<endl;
	    }
	}
	return 0;
}
3

thank you so much

4

still it is giving wrong answer

5

Umm you haven’t changed anything to long long like I mentioned in the previous post :sweat_smile:

I have sent the code there.