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$ ~a_i~ and the last occurrence of $b_i$ ~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)$ ~\mathcal O(NM)~

Subtask 2

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

Time complexity: $\mathcal O(NM)$ ~\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)$ ~\mathrm{first}(i)~ and $\mathrm{last}(i)$ ~\mathrm{last}(i)~ in $\mathcal O(1)$ ~\mathcal O(1)~. The rest of the solution follows from Subtask 1.

Time complexity: $\mathcal O(N+M)$ ~\mathcal O(N+M)~

Comments

There are no comments at the moment.