Editorial : Definitely Larger

The following editorial describes the model approach implemented in model_sol.cpp.

Work from $i = N - 1$ down to $0$. Maintain an array Q of integer ranks for already processed positions; larger rank means larger final $q$ (after the last normalization step).

For index $i$, gather Q[j] over all $j > i$ with $p_j > p_i$, sort these numbers in nonincreasing order into vals. If $d_i > |\text{vals}|$, no placement is possible. Otherwise define a new rank nval: if $d_i = |\text{vals}|$, set nval = 0 (as large as possible among processed indices); if $d_i < |\text{vals}|$, set nval = \text{vals}[d_i] + 1 so that exactly $d_i$ gathered indices keep a strictly larger rank than $i$.

Before assigning Q[i], increment every Q[t] that is at least nval by $1$ to keep ranks distinct and mimic inserting $i$ into the total order. Finally set Q[i] = nval. After processing all $i$, print `Q[i] + 1$ for each $i$ to obtain a permutation of $1$ through $N$.

We need a permutation $q$ such that for every index $i$:

So index $i$ only cares about indices to its right.

For fixed $i$, define:

Then the requirement is:

That means: among a specific subset of right-side indices, exactly $d_i$ must be “above” $i$ in $q$-value.

Instead of choosing exact values immediately, we first construct an order of indices by decreasing $q$:

• left in the list = larger $q$,
• right in the list = smaller $q$.

After this order is built, we can assign:

• first gets $q=n$,
• second gets $q=n-1$,
• …
• last gets $q=1$.

So the whole task is reduced to inserting indices into this order correctly.

Process $i=n,n-1,\dots,1$.

When handling $i$, all indices $j>i$ are already inserted, so the whole set $S_i$ is already present in the current list.
Now we just need to place $i$ so that exactly $d_i$ elements of $S_i$ stay before it.

If $d_i>|S_i|$, impossible immediately, answer is -1.

Scan current list from left to right and count only elements with $p_j>p_i$ (these are exactly members of $S_i$).

• If $d_i=0$, put $i$ at the front.
• If $d_i>0$, put $i$ right after the $d_i$-th counted element.

Then exactly $d_i$ members of $S_i$ are before $i$, so exactly $d_i$ of them have larger $q$ than $i$.

After placing $i$, we will only process $ki$.

So future insertions cannot change the count for index $i$.
Hence each index is “fixed forever” at insertion time.

This gives a full correctness argument.

Suppose:

Process from right to left:

• $i=5$: right side empty, $d_5=0$ -> list [5]
• $i=4$: $S_4=\{5\}$, need $1$ before -> list [5,4]
• $i=3$: $S_3=\{4,5\}$ (both have larger $p$), need $1$ before -> list [5,3,4]
• $i=2$: $S_2=\{4,5\}$, need $2$ before -> list [5,4,2,3]
• $i=1$: $S_1=\{2,4,5\}$, need $2$ before -> list [5,4,1,2,3]

Assign values by position: $q_5=5,q_4=4,q_1=3,q_2=2,q_3=1$, so:

For each $i$, we scan at most $O(n)$ current elements.

• Time: $O(n^2)$ per test case.
• Memory: $O(n)$.

Given $\sum n \le 5000$, this is easily fast enough.