# Help me in solving TRIPLETMIN problem

### My issue

i couldn’t find the error according to me logic seems to be right .if some one is using premium pls tell me atleast where my code is failed

### My code

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

int main() {
int t;
cin>>t;
for (int p=0;p<t;p++)
{
int n,q;
cin>>n;
cin>>q;
int arr[n];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
vector<int> query(n-2);
for(int i=0;i<n-2;i++)
{

query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}
for (int i=0;i<q;i++)
{
int a;
cin>>a;
cout<<arr[lower_bound(query.begin(),query.end(),a)-query.begin()]<<endl;
}
}
return 0;
}

``````

Problem Link: TRIPLETMIN Problem - CodeChef

@ramteja1937
U r getting error bcoz of integer overflow . just take all as long long int .
include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
for (int p=0;p<t;p++)
{
long long int n,q;
cin>>n;
cin>>q;
long long int arr[n];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
vector query(n-2);
for(int i=0;i<n-2;i++)
{

``````        query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}
for (int i=0;i<q;i++)
{
long long int a;
cin>>a;
cout<<arr[lower_bound(query.begin(),query.end(),a)-query.begin()]<<endl;
}
}
return 0;
``````

}

Hi, I actually also solved this just now but i didnt get the optimal solution i.e., i couldnt speed it up and it gave me “TLE”. If u dont mind can you look at my code and guide me how i can optimize my code. Thank you.

include <stdio.h>
int min_oftriplet(int index,int ar[], int size)
{
//first we sort the arrAY.
int n=size;
for(int i=1;i<=n;i++)
{
int temp;
for(int j=i+1;j<=n;j++)
{
if(ar[i]>=ar[j])
{
temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}
}
if(index>n){

``````       return ar[1];  //if query is greater than the size                 of array return the smallest                       number .
}else
{
for(int i=1;i<=index;i++)
{
if(i+2>=index)
{
return ar[i];
}
}
}
}
``````

int main(void) {

``````int t;
scanf("%d",&t);

while(t--)
{
int n,q;
scanf("%d %d",&n,&q);
int ar[n],quer[q];

for(int i=1;i<=n;i++)
{
scanf("%d",&ar[i]);
}
for(int i=1;i<=q;i++)
{
scanf("%d",&quer[i]);
}
for(int i=1;i<=q;i++)
{
printf("%d\n",min_oftriplet(quer[i],ar,n));
}
}

return 0;
``````

}

@d_d26 u r getting tle bcoz your code complexity is O(n^2) and u have to do it in O(nlogn)
so to do so we have used binary search along with prefix precomputation which will be the optimal solution for the problem

what is prefix precomputation ?

@d_d26 actually its like we precompute some values and store it in some data structure from the prefix or suffix of the array to use it in future.
like in this prb precomputation part is this
for(int i=0;i<n-2;i++)
{

``````        query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}``````

ohh i think i get it. Thank you

1 Like