RNMAXEV - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy-Med

PREREQUISITES:

Elementary combinatorics

PROBLEM:

For an array A, we generate a new array B as follows:

  • For each i, let k = \min(i, N+1-i).
  • Set B_i = \min(B[i-k+1 : i+k-1])

You’re given B, count the number of A that result in this B.
The length of the array is even.

EXPLANATION:

To understand what constraints B puts on A, let’s look at elements from left to right.

  • B_1 corresponds to the subarray [1, 1] of A.
    So, A_1 = B_1 must be fixed.
  • B_2 corresponds to the subarray [1, 3] of A.
    So, we want \max(A_1, A_2, A_3) = B_2.
    This means that each of A_1, A_2, A_3 must be \leq B_2, and also at least one of them must equal B_2.
  • B_3 corresponds to subarray [1, 5] of A.
    Again, this means all of A_1, \ldots, A_5 must be \leq B_3, and at least one of them must equal B_3.

It’s easy to see that this pattern continues till we reach the middle of the array.
That is, for each i \leq \frac{N}{2}, we have:

  • Each of A_1, A_2, \ldots, A_{2i - 1} must be \leq B_i.
  • At least one of 2i-1 elements must be equal to B_i.

Now, consider some adjacent pair of elements B_{i-1} and B_i (we’re still working with i \leq \frac{N}{2}).
Observe that:

  • If B_i \lt B_{i-1}, no solution can exist.
    This is because we want the maximum of the first 2\cdot i - 1 elements of A to be smaller than the maximum of the first 2\cdot (i-1) - 1 elements, which is absurd.
  • If B_i \gt B_{i-1}, then the value B_i cannot appear among the first 2\cdot (i-1) - 1 elements (since otherwise it would become their maximum).
    So, B_i must appear at either index 2i-1 or 2i-2 of A; and of course the other element in this pair must be \leq B_i as well.
    Note that we don’t really need to care about elements before index 2i-2 anymore: they must be \leq B_{i-1}, so they’re certainly \leq B_i as well.
  • If B_i = B_{i-1}, then we only need to ensure that the two “new” elements (at indices 2i-2 and 2i-1) aren’t too large, i.e. are both \leq B_i.

Essentially, we have a few constraints on each pair of indices (2i-2, 2i-1):

  • Both these values should be \leq B_i.
  • Depending on the relation between B_i and B_{i-1}, possibly (at least) one of these two should equal B_i.

Earlier, we looked at only the first half of the array.
Now, we look at the second half.
The situation is clearly symmetric: A_N is fixed to B_N, and then each other B_i
(for \frac{N}{2} \lt i \lt N) gives a couple of constraints on a pair of adjacent elements: an upper bound on their values, and maybe a constraint on what one of them should be.

Here’s where we use the fact that N is even: the pairs of indices affected by the first half and second half will be the same!
For example, consider N = 8.

  • Indices 2, 3, 4 of B impose conditions on index pairs (2, 3), (4, 5), (6, 7) of A respectively.
  • Indices 5, 6, 7 of B impose conditions on index pairs (2, 3), (4, 5), (6, 7) of A respectively.

As you can see, the pairs are the same: just that for each pair, it’s affected by one element from the first half of B and one element from the second half.

Thus, each of the \frac{N-2}{2} index pairs obtained this way are completely independent!
We can hence solve for each one separately, and then multiply all their answers together to obtain the final answer.

So, consider some index pair (2i, 2i+1).
First off, it will always receive two upper limits on its values: obviously, only the smaller one among them is relevant.
Let U denote this smaller upper bound.

Then, it’s possible there are constraints of the form “at least one of the elements in this pair should be x”.
Let’s analyze this.

  • If there are no such constraints at all, we only need to ensure that both elements are \leq U.
    Clearly, there are U^2 ways to choose the elements.
  • Suppose there’s one such constraint, and it requires an element equal to x.
    Then,
    • If x \gt U we have a contradiction and the answer is 0.
    • Otherwise we’ll always have x = U because of how the constraints are created.
      Here, there are 2U - 1 ways to assign values such that at least one of them is U.
  • Suppose there are two such constraints, say with values x and y.
    Then,
    • If x = y this is functionally equivalent to having only one constraint; so just as in the previous case the count is either 2U-1 or 0, depending on how x compares to U.
    • If x \neq y then there’s in fact no valid configuration! Do you see why?

Each pair can thus be solved in constant time once the upper bounds and constraints on pairs are known.
This results in a fairly simple \mathcal{O}(N) solution.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3)