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

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}\}$ $max_{1 \leq i \leq M} {last (b_{i}) - first (a_{i}) ∣ b_{i} and a_{i} are colours that exist in the scarf}$ .

Time complexity: $\mathcal O(NM)$ $O (N M)$

Subtask 2

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

Time complexity: $\mathcal O(NM)$ $O (N M)$

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

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

Comments

There are no comments at the moment.