ZCO 2013 problem

general
1

http://www.iarcs.org.in/inoi/2013/zco2013/zco2013-2a.php

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 (30 marks) : 2 ≤ N ≤ 2,000.

Subtask 2 (70 marks) : 2 ≤ N ≤ 100,000.

Limits

Time limit : 3s

Am not able to come up with an efficient solution.
Could someone suggest some solution?

2

Try to make a data structure such that it holds the index(chewing gum type) and the hardness quotient.
struct gum{
int index, value;
}
declare an array of scanned gums.

i.e. gum gumregister[NUMBEROFGUMS]

Now using sort function sort it by value(hardness quotient).

-> sort(dumregister, gumregister + NUMBEROFGUMS, compararison)

Write a comparison function which compares values of the 2 given gums.
Now iteration through all possible solutions should become easy. Start from the first value and iterate until K is reached, start iteration again from the next position.
Please follow up. Is this efficient enough or is there a way to make it more efficient ?

3

it’s not efficient enough for the second sub-task

4

Modify the data structure so that it holds the number of occurrences of a type of gum. Make a set first so that you get an ordered sequence then copy it to an array so that index you get the element in constant time.

5

Here is my solution :-
even though it is heavily commented, I will explain in brief. We take input in an array and sort it (so we can perform binary search on it), for every element i in array we binary search highest element less than k and update ans with += the binary search answer - i.
https://www.codechef.com/viewsolution/41709079