PREFSUFREC - 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’re given an array F of length N, that satisfies F_1 + F_2 + \ldots + F_N = 2N and F_1 \ge N.
Find any array A of length N such that:

  • Let P_i = \max(A_1, \ldots, A_i)
  • Let S_i = \min(A_i, \ldots, A_N)
  • F_i equals the total number of times i appears in P and S.

EXPLANATION:

The F_1 \ge N condition is quite important here - in particular, it implies that 1 must certainly appear in A (and hence be the minimum element of A).

Let i_0 be the index of the rightmost appearance of 1 in A.
Observe that all suffix minimums at indices 1, 2, \ldots, i_0 are then forced to be 1.
So, we obtain i_0 copies of 1 already.

Since F_1 \ge N, a reasonable thing to try is to just choose i_0 = N, i.e. set the last element to 1.
This will give us N copies of 1, and we now only need to worry about prefix maximums.

Observe that we now have N-1 free positions (everything from 1 to N-1), and N elements that must appear as prefix maxima.
Further, by choosing A_N = 1, the only prefix maximum we have no control over is P_N, because we’ll surely have P_N = \max(1, P_{N-1}) = P_{N-1}.

Now, let M be the largest element such that F_M \gt 0. M is hence the largest element that can appear in A.
Suppose F_M \ge 2. Then, it turns out to always be possible to create a valid array: a simple construction is to just place the remaining elements in ascending order from positions 1 to N-1.

That is, place (F_1 - N) copies of 1, then F_2 copies of 2, F_3 copies of 3, and so on till we place (F_M - 1) copies of M.
Since we’re placing them in ascending order, all these elements will be prefix maxima; exactly as we desired.
Further, because F_M \ge 2, we’ll place at least one copy of M. This means the final prefix maximum (which we had no control over) will also be M; which accounts for the last remaining value.

So, as long as F_M \ge 2, we have a valid solution: set A_N = 1 and then just place the remaining elements in ascending order.

That leaves us with the case of F_M = 1, i.e. there’s only one copy of the maximum.
However, quite nicely, this case has no solution!
To see why: F_M = 1 means that M must definitely appear somewhere in A (and be the largest element to appear in A); suppose it appears first at position i.
Then, it can be seen that:

  1. If i \lt N, then the prefix maximums at positions i, i+1, \ldots, N will all equal M for sure.
    Since i \lt N, this would mean a frequency of at least 2, which is not what we want.
    So, i \lt N is impossible.
  2. This leaves i = N.
    Here, M appears only once as a prefix maximum - but, being the rightmost element, it also appears once as a suffix minimum!
    So, once again we have at least two copies of M, meaning F_M = 1 is impossible.

So, we end up with a very simple construction in the end.
Let M be the largest element such that F_M \gt 0. Then,

  • If F_M = 1, no solution exists.
  • Otherwise, one solution is to set A_N = 1, and then place (F_1 - N) copies of 1, F_2 copies of 2, …, F_{M}-1 copies of M in positions 1, 2, \ldots, N-1 from left to right.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    f = [0] + list(map(int, input().split()))
    mx = n
    while f[mx] == 0: mx -= 1

    if f[mx] == 1:
        print(-1)
        continue

    ans = [1]*n
    f[1] -= n
    p = 0
    for i in range(1,n+1):
        while f[i] > 0:
            ans[p] = i
            f[i] -= 1
            p += 1
    ans[-1] = 1
    print(*ans)