Editorial for CCO '22 P1 - Alternating Heights

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, a subarray is valid if and only if it is alternating between $1$ ~1~ and $2$ ~2~.

Preprocess by marking positions where we have adjacent $1$ ~1~s or adjacent $2$ ~2~s, and then use a PSA to check queries.

Time Complexity: $\mathcal O(N + Q)$ ~\mathcal O(N + Q)~

Hint

Graph Theory?

Subtask 2

Represent the problem as a graph, numbers from $1$ ~1~ to $K$ ~K~ being nodes and adjacent elements being edges.

A graph is valid iff it has no directed cycles.

Preprocess all subarrays.

Time Complexity: $\mathcal O(N^3 + Q)$ ~\mathcal O(N^3 + Q)~

Subtask 3

Process all queries in linear time.

Time Complexity: $\mathcal O(NQ)$ ~\mathcal O(NQ)~

Subtask 4

If a subarray is invalid, any subarray containing it is invalid. Use two-pointer to preprocess all subarrays.

Time Complexity: $\mathcal O(N^2 + Q)$ ~\mathcal O(N^2 + Q)~

Comments

There are no comments at the moment.