Editorial for Mock CCC '23 Contest 1 J3 - Pairing Gifts

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Marshmellon

For this problem, we need to count the number of pairs (a_i, b_j) such that a_i + b_j = M and |i-j| \ge K.

Subtask 1

Subtask 1 is created to reward full solutions that incorrectly handle the |i-j| \ge K condition.

Subtask 2

Firstly, observe that since all a_i are distinct and all b_j are distinct, each a_i can only have one b_j that forms a valid bundle. For this subtask, we can loop through all b_j for each a_i and check if there exists a pair that satisfies the conditions provided.

Time Complexity: \mathcal O(N^2)

Subtask 3

For full marks, the look-up for b_j must be made more efficient. We can maintain a map that maps the value of each gift in b to its index. Then for each a_i, we can check if there exists a b_j with value M-a_i at a valid index.

Time Complexity: \mathcal O(N) or \mathcal O(N \log N)


There are no comments at the moment.