DISTARR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

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

Author: bitwizz
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, elementary combinatorics

PROBLEM:

You’re given an array A of length N.
Count the number of arrays B such that:

  1. 1 \leq B_i \leq A_i for each i.
  2. B_i \neq B_j for any i \neq j.

EXPLANATION:

A first attempt to solve the problem might be to try and build B from left to right.
That will lead to the following algorithm:

  • Choose B_1 to be any integer in [1, A_1]. There are A_1 choices.
  • Next, choose B_2 to be any integer in [1, A_2] that’s not B_1.
    This is immediately a bit harder to do: if B_1 \leq A_2 then there are A_2 - 1 choices (since B_1 is banned), and if B_1 \gt A_2 there are A_2 choices instead since nothing is banned.
  • Moving to B_3 makes things even harder: there can be anywhere between zero and two previously chosen elements that are \leq A_3, and each case requires a different multiplier.

Let’s set this aside for now, and try to simplify the problem a bit.

Observe that the answer doesn’t change if we rearrange the elements of array A (since each corresponding B can be rearranged in the exact same way).
This means we can look at A in whichever order is favorable to us: so let’s look at it in sorted order.

So, suppose A_1 \leq A_2 \leq \ldots \leq A_N.
Let’s attempt to construct B now, using the initial algorithm.

  • B_1 can be any integer in [1, A_1], and so has A_1 choices.
  • B_2 can be any integer in [1, A_2], but should not be B_1.
    However, B_1 \leq A_1 and A_1 \leq A_2, so definitely B_1 \leq A_2.
    This means B_1 is always banned, and so there are A_2 - 1 choices for B_2.
  • B_3 can be any integer in [1, A_3] other than B_1 or B_2.
    It’s easy to see that once again, sortedness guarantees that both B_1 and B_2 are \leq A_3, so there are always two banned choices.
    This means there are A_3 - 2 choices for B_3.
  • The exact same logic holds for any index, in fact.
    That is, B_i can be anything in [1, A_i], except B_1, B_2, \ldots, B_{i-1}.
    However, these first i-1 elements will all be \leq A_i, so there are exactly A_i - (i-1) choices for B_i.

This means the answer is simply

\prod_{i=1}^N (A_i - i + 1)

Note that if any A_i - i + 1 term is not positive, there are in fact no choices for that index and the answer should be 0.
However, this doesn’t need to be explicitly checked for: since the A_i are sorted, if any term is negative then there will definitely be a term that’s 0; and since we have a product the product will end up being 0 in the end anyway.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    ans = 1
    for i in range(n):
        ans = ans * (a[i] - i) % mod
    print(ans)