Editorial for Riolku's Mock CCC S2 - Keen Keener Sequence


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: Riolku

Subtask 1

For this subtask, we can brute force all 4-tuples. Make sure that all indices used are distinct for each tuple.

Time Complexity: \mathcal O(N^4)

Subtask 2

For this subtask, we can brute force the first three elements (i, j, k) of the tuple. We can compute d = \frac{a_i \times a_j}{a_k}, and find out how many times d shows up in the array. We need to subtract 1 for each of a_i = d or a_j = d or a_k = d.

Time Complexity: \mathcal O(N^3)

Subtask 3

For this subtask, we can loop through the first two elements (i, j) of the tuple. We can store how many times the product p = a_i \times a_j appears.

Then, we can loop through the first two elements (i, j) again. We can add to the total the number of times a_i \times a_j shows up across all other pairs.

Unfortunately, we might over-count any pairs (i, k) or (j, k), so we can use a frequency array to exclude those.

Also, we have removed the pair (i, j) too many times, so we should add 2 back to our total.

Finally, we also have to add back pairs if a_i = a_j, since then the pairs (i, j) and (j, i) are excluded too many times.

Time Complexity: \mathcal O(N^2)

Note: Although the complexity of this problem is \mathcal O(N^2), most solutions use a map and perform very poorly. A harder version of this problem exists to challenge those who are interested. Hint: don't use a map.


Comments

There are no comments at the moment.