MINDSTC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have an array A of length N.
Define:

  • For a pair (L, R), f(L, R) is an array B of length N such that:
    • If L \le A_i \le R then B_i = A_i + 1.
    • Otherwise B_i = A_i - 1.
  • \text{distinct}(B) denotes the number of distinct elements in array B.

For each L = 1, 2, \ldots, N, compute the minimum value of \text{distinct}(f(L, R)) across all L \le R \le N.

EXPLANATION:

Let’s understand what \text{distinct}(f(L, R)) looks like for a fixed R.

Let c_x denote the number of occurrences of x in the array A, and d_x denote the number of occurrences of x in the array f(L, R).
To obtain d_x from the array c, we have the following:

  • For each 1 \le x \lt L, add c_x to d_{x-1}.
  • For each L \le x \le R, add c_x to d_{x+1}.
  • For each R \lt x \le N, add c_x to d_{x-1}.

In particular, note that the only “overlap” happens near the value R.
Specifically, we have:

  • d_{R+1} = c_R + c_{R+2}
  • d_R = c_{R-1} + c_{R+1}
    (Note that this only happens when L \lt R).

For everything else, each element of d derives from only a single element of c: we have
d_x = c_{x+1} for all x \gt R+1 and also for all x \lt L, while d_x = c_{x-1} for all L \lt x \lt R.

The number of distinct elements in f(L, R) equals the number of x such that d_x \gt 0.
Observe that this is almost equal to the number of x such that c_x \gt 0.
The only difference is that:

  • If both c_R and c_{R+2} are positive, then the occurrences of R and R+2 will merge into occurrences of R+1 in the transformed array.
    This will cause us to lose one distinct element.
  • Similarly, if both c_{R-1} and c_{R+1} are positive, we’ll lose one distinct element (though only when L \lt R.)

In particular, note that the number of distinct elements can fall by at most 2.

We can use this characterization to solve the problem at hand.

Let’s fix the left endpoint L.
Also let D denote the number of distinct elements in the array A.

Then,

  • If there exists an integer R \gt L such that all of \{c_{R-1}, c_R, c_{R+1}, c_{R+2}\} are positive, then choosing this R gives us D-2 distinct elements.
    This is clearly optimal.
  • If that doesn’t happen, we can still try for D-1 distinct elements by satisfying only one of the two conditions:
    • Find some R \ge L such that c_R \gt 0 and c_{R+2} \gt 0; or
    • Find some R \gt L such that c_{R-1} \gt 0 and c_{R+1} \gt 0.
    • Note that the second condition is basically equivalent to the first, so we don’t even need to bother checking it.
  • If the check for D-1 also fails, then the answer must be D.

How do we find such an R, given that L is fixed?
Well, we only care about the fact that R \ge L.
So, it’s enough to find the rightmost R that satisfies each condition - which is easy to do in linear time.
Then, for each L simply check if precomputed values of R lie beyond it or not, giving a constant-time check per index.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    freq = [0]*(n+5)
    for x in a: freq[x] += 1
    
    R4, R2 = -1, -1
    D = 0
    for i in range(1, n+1):
        D += freq[i] > 0
        if freq[i] > 0 and freq[i+2] > 0: R2 = i
        if min(freq[i:i+4]) > 0: R4 = i
    
    ans = [D]*(n+1)
    for L in range(1, n+1):
        if R4 >= L: ans[L] -= 2
        elif R2 >= L: ans[L] -= 1
    print(*ans[1:])
2 Likes