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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For this problem, we need to count the number of pairs such that
and
.
Subtask 1
Subtask 1 is created to reward full solutions that incorrectly handle the condition.
Subtask 2
Firstly, observe that since all are distinct and all
are distinct, each
can only have one
that forms a valid bundle. For this subtask, we can loop through all
for each
and check if there exists a pair that satisfies the conditions provided.
Time Complexity:
Subtask 3
For full marks, the look-up for must be made more efficient. We can maintain a map that maps the value of each gift in
to its index. Then for each
, we can check if there exists a
with value
at a valid index.
Time Complexity: or
Comments