Help me in solving TRIPLETMIN problem

help
,
1

My issue

I referred the solution given by author and tester. Both of their solutions are logically the same as mine however when I submit my code I get a TLE and WA.
I can’t find the error, can someone please help me out?

My code

// #pragma GCC optimize("Ofast", "unroll-loops")
// #pragma GCC target("avx2", "tune=native")

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define what(x) cerr << #x << " is " << x << endl;
#define endl "\n"

typedef long long ll;

using namespace std;
 
int main()
{ 
    
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    fastio;
    
    int t = 1;
    cin>>t;

    while(t--){
        int n, q; 
        cin>>n>>q; 

        vector<ll> v(n); 
        for(int i = 0; i<n; i++){
            cin >> v[i]; 
        }

        sort(v.begin(), v.end());

        vector<ll> lieIN(n-2); 

        for(int i = 0; i<v.size()-2; i++){
            lieIN[i] = ((n-i-1)*(n-i-2))/2; 
            if(i != 0)
                lieIN[i]+=lieIN[i-1]; 
        }
        
        while(q--){
            int a; 
            cin>>a; 

            int index = lower_bound(lieIN.begin(), lieIN.end(), a)-lieIN.begin(); 
            cout << v[index] << endl; 
        }
    }
    
    return 0;
}

Problem Link: TRIPLETMIN Problem - CodeChef

2

Oh you have the same error with me, but I fixed it. I think your ‘int a’ should be long long, ‘int index’ as well as. This is your code that I fixed and got AC.

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define what(x) cerr << #x << " is " << x << endl;
#define endl "\n"

typedef long long ll;

using namespace std;
 
int main()
{ 
    
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    fastio;
    
    int t = 1;
    cin>>t;

    while(t--){
        ll n, q; 
        cin>>n>>q; 

        vector<ll> v(n); 
        for(int i = 0; i<n; i++){
            cin >> v[i]; 
        }

        sort(v.begin(), v.end());

        vector<ll> lieIN(n-2); 

        for(int i = 0; i<v.size()-2; i++){
            lieIN[i] = ((n-i-1)*(n-i-2))/2; 
            if(i != 0)
                lieIN[i]+=lieIN[i-1]; 
        }
        
        while(q--){
            ll a; 
            cin>>a; 

            ll index = lower_bound(lieIN.begin(), lieIN.end(), a)-lieIN.begin(); 
            cout << v[index] << endl; 
        }
    }
    
    return 0;
}
3

Hey! Thank you so much for helping me out.

I completely missed the fact that K <= NC3 and could be a very large number and hence has to be long long.
There isn’t a need to make index long long but since index < n = 100000.

However another thing i missed was that I declared n as int and the line
"lieIN[i] = ((n-i-1)*(n-i-2))/2; "
can lead to a overflow.

After fixing these issues my code worked.

Thank you once again :slight_smile: