Editorial for Another Contest 3 Problem 1 - Diverse Arrays

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.

If an array is not diverse, it has fewer than $K$ $K$ distinct elements present.

There are $\frac{N^2+N}{2}$ $\frac{N^{2} + N}{2}$ subarrays, so we can enumerate the arrays which are not diverse and then the remaining ones must be diverse.

Lemma: Let $f(i)$ $f (i)$ be the leftmost index such that the subarray from $f(i)$ $f (i)$ to $i$ $i$ is not diverse. If $i \ge j$ $i \geq j$ , then $f(i) \ge f(j)$ $f (i) \geq f (j)$ .

Proof: By contradiction - if $i \ge j$ $i \geq j$ but $f(i) < f(j)$ $f (i) < f (j)$ , then we could extend $f(j)$ $f (j)$ to be at least as small as $f(i)$ $f (i)$ since that subarray would be a subarray of the array defined by $f(i)$ $f (i)$ and $i$ $i$ .

Therefore, if we loop $i$ $i$ from left to right and maintain $f(i)$ $f (i)$ in amortized constant time, we can enumerate all the arrays which are not diverse. To do this, we advance $i$ $i$ by one and maintain a frequency map of numbers to how many times we observe them. If the frequency map is at least $K$ $K$ in size, we remove the leftmost element still present in the subarray and repeat this until the frequency map has size less than $K$ $K$ . The size of the remaining subarray is the number of subarrays ending at that index which are not diverse.

Comments

There are no comments at the moment.