Virus Virus - 1 month ago 16
C++ Question

Time Limit Error On CodeChef

This Is The Question

Here is my solution:

#include <iostream>

using namespace std;

int main(){
unsigned long numberOfGums;
unsigned long hardnessLimit;
unsigned long counter = 0;

cin >> numberOfGums;
cin >> hardnessLimit;

unsigned long gums[numberOfGums];

for(unsigned long i=0; i<numberOfGums; i++){
cin >> gums[i];
}

for(unsigned long i=0; i<numberOfGums; i++){
if(gums[i] < hardnessLimit){
for(unsigned long j=i+1; j<numberOfGums; j++){
if((gums[i] + gums[j]) < hardnessLimit){
counter++;
}
}
}
}

cout << counter << endl;

return 0;
}


This program is giving me TLE(Time Limit Exceeded) error, due to which i am getting only 30 points out of 100. To be specific, this program is unable to complete subtask-2 worth the rest 70 marks (given on the problem page).

I have tried stuff like using printf and scanf instead of cin and cout, but the program still isn't fast enough.

What can i do to improve this program, or what is a better approach to this problem.

I tried this also, but got the same error:

#include <iostream>

using namespace std;

int main(){
long numberOfGums;
long hardnessLimit;
long counter = 0;
long temp = 0;

cin >> numberOfGums;
cin >> hardnessLimit;

long gums[numberOfGums];

for(long i=0; i<numberOfGums; i++){
cin >> temp;
if(temp < hardnessLimit){
gums[i] = temp;
}
}

for(long i=0; i<numberOfGums; i++){
if(gums[i] != -1){
for(long j=i+1; (j<numberOfGums); j++){
if(((gums[i] + gums[j]) < hardnessLimit) && gums[j] != -1){
counter++;
}
}
}
}

cout << counter << endl;

return 0;
}

Answer

Your solution is O(N^2) which will definitely time out given the constraints.

A more efficient solution is an O(NlogN) solution. This is the basic outline of the algorithm:

  • Sort the array. This takes O(NlogN) time.

  • Now for each element in the sorted array, say p, search for an element index(right of the element p) in the array such that the value at that index is less than k - p. Use binary search for this. After finding this index, you can easily calculate the number of such pairs associated with the element p. This complete step takes O(logN) time for each element

  • Do the above process for all elements in the array except for the last element as there is no array left to its right.

You will get the answer by summing up all the pairs for each element p that you have obtained

Hope it helps!!!

Edit: I am adding the C++ implementation of the above algorithm. This solution passes all the test cases on CodeChef.

#include <iostream>
#include <algorithm>
using namespace std;
int binsearch(int a[],int n, int x)
{
    int low, high, mid, k=-1;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid] <= x-1){
            k = mid;
            low = mid+1;
        }
        else{
            high = mid-1;
        }

    }
    return k;
}
int main() 
{
    int n, k, i, j;
    long long ans = 0;
    cin>>n>>k;
    int arr[n];

    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    sort(arr,arr+n);

    j = 0;

    while(j<n-1)
    {
        if(k-arr[j] > 0)
        {
            int ind = binsearch(arr,n,k-arr[j]);
            ans = ans + (ind-j>=0 ? (ind-j):0);
        }
        j++;
    }
    cout<<ans<<endl;
    return 0;

}
Comments