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 distinct elements present.

There are \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) be the leftmost index such that the subarray from f(i) to i is not diverse. If i \ge j, then f(i) \ge f(j).

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

Therefore, if we loop i from left to right and maintain f(i) in amortized constant time, we can enumerate all the arrays which are not diverse. To do this, we advance 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 in size, we remove the leftmost element still present in the subarray and repeat this until the frequency map has size less than 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.