Improving efficiencey of Pairing Program.

general
, , ,
1

I was going through some sample questions on the net. I found a question where you have to count the number of pairs that can be formed according to the info given below:

Hobbes has challenged Calvin to
display his chewing skills and chew
two different types of Chewing
Magazine’s Diabolic Jawlockers chewing
gum at the same time. Being a generous
sort of tiger, Hobbes allows Calvin to
pick the two types of gum he will
chew.

Each type of chewing gum has a
hardness quotient, given by a
non-negative integer. If Calvin chews
two pieces of gum at the same time,
the total hardness quotient is the sum
of the individual hardness quotients
of the two pieces of gum.

Calvin knows that he cannot chew any
gum combination whose hardness
quotient is K or more. He is given a
list with the hardness quotient of
each type of gum in the Diabolic
Jawlockers collection. How many
different pairs of chewing gum can
Calvin choose from so that the total
hardness quotient remains strictly
below his hardness limit K?

For instance, suppose there are 7
types of chewing gum as follows:
Chewing gum type 1 2 3 4 5 6 7
Hardness quotient 10 1 3 1 5 5
0

If Calvin’s hardness limit is 4, there
are 4 possible pairs he can choose:
type 2 and 7 (1+0 < 4), type 3 and 7
(3+0 < 4), type 2 and 4 (1+1 < 4) and
type 4 and 7 (1+0 < 4).

Input format

Line 1 : Two space separated integers
N and K, where N is the number of
different types of chewing gum and K
is Calvin’s hardness limit.

Line 2: N space separated non-negative
integers, which are the hardness
quotients of each of the N types of
chewing gum.

Output format

The output consists of a single
non-negative integer, the number of
pairs of chewing gum with total
hardness quotient strictly less than
K.

Sample Input

7 4 10 1 3 1 5 5 0

Sample Output

4

Test data

In all subtasks, you may assume that
all the hardness quotients as well as
the hardness limit K are between 0 and
1,000,000, inclusive.

Subtask 1 : 2 ? N ? 2,000.

Subtask 2 : 2 ? N ? 100,000.

Live evaluation data

Subtask 1: Testcases 0,1,2,3.

Subtask 2: Testcases 4,5,6.

Limits

Time limit : 3s

Memory limit: 64 MB

I used a code which has 2 for loops going through to make a pair. But it is very inefficient since the time would be N*N times which would be too much if N goes upto 100,000. SO I was wondering if there’s any other method? Here is my code:

#include “iostream” using namespace std; int main() {
unsigned long int N,i,j;
int K, *arr,cnt=0;
cin>>N;
cin>>K;
arr = new int [N];

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

    for(i=0;i<N;i++)
    {
            if(arr[i]>=K)
            {
                    continue;
            }
            for(j=i+1;j<N;j++)
            {
                    if((arr[i]+arr[j])<K)
                    {
                            cnt++;
                    }
            }
    }
    cout<<cnt;
    return 0; }

I would appreciate any help. Thanks.

2

Since any chewing gum with hardness greater than or equal to K, will not be in the list, you can sort the array and run the for loops only till the index of the first K.

So, the code you need to add should be like

sort(arr, arr+N);
int index = find(arr, arr+N, K);

And the for loop should be till index.

Also remember to include the algorithm library.

3

Here is a similar problem

And the solution

1 Like
4

That’s exactly what I did over here, it’s still timing out for the last test case in subtask 2 :frowning:

5

This algorithm is still O(N^2), because it is possible that everything is less K. Here is my code for CHEWING: http://pastebin.com/xvYpJG1Z

1 Like
6

Whoa! I was just trying to write lines and lines of code to implement binary search and was messing everything up, thank you so much @superty for your timely help :slight_smile:

1 Like
7

You’re welcome.

Before using it, make sure you understand how lower_bound works.

Also it’s still good to know how to implement binary search on your own, in some situations you may not be able to use builtin functions.

1 Like