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)$ ~(a_i, b_j)~ such that $a_i + b_j = M$ ~a_i + b_j = M~ and $|i-j| \ge K$ ~|i-j| \ge K~.

Subtask 1

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

Subtask 2

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

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 3

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

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

Comments

There are no comments at the moment.