Editorial for DMOPC '20 Contest 2 P2 - Lousy Christmas Presents

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

Subtask 1

For every query, iterate through all the colours and find the first occurrence of a_i and the last occurrence of b_i.

The answer is given by \max_{1 \le i \le M} \{\mathrm{last}(b_i) - \mathrm{first}(a_i) \mid b_i\text{ and }a_i\text{ are colours that exist in the scarf}\}.

Time complexity: \mathcal O(NM)

Subtask 2

There is no intended solution. (Red herring task.)

Time complexity: \mathcal O(NM)

Subtask 3

Keep track of the first and last occurrence of every colour. For every query, it's now possible to query \mathrm{first}(i) and \mathrm{last}(i) in \mathcal O(1). The rest of the solution follows from Subtask 1.

Time complexity: \mathcal O(N+M)


There are no comments at the moment.