PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Segment tree/fenwick tree
PROBLEM:
You have an array A whose elements are distinct.
You can perform the following operation:
- Choose indices i \lt j such that A_i \gt A_j.
Delete either A_i or A_j from A.
An array is said to be terminal if no more operations can be performed on it.
Count the number of terminal arrays that can be reached from A.
EXPLANATION:
Our operation is “pick an inversion, and delete one of its elements”.
Clearly, this means an array is terminal if and only if it doesn’t contain any inversions, i.e. is sorted in ascending order.
Since we’re deleting elements without changing order, we’ll thus end up with some sorted subsequence of A.
However, it’s not really true that any sorted subsequence is reachable: for example, if A = [1, 2, 3], then we cannot perform any moves at all, so we can’t end up with [1, 2] or [1, 3] for example (even though they’re sorted subsequences).
Let’s make a couple of observations.
First, a rather obvious one is that it’s not possible to make A empty: there will always be at least one element remaining.
This of course is because an operation needs two elements to exist and deletes one of them.
Next, we can see that some elements can’t be deleted no matter what.
Specifically, if A_i is such that:
- A_i \gt A_j for all j \lt i, and
- A_i \lt A_j for all j \gt i
then it’s impossible to delete A_i, since it’s not part of an inversion at all (and deleting other elements won’t change that.)
Now, since A is a permutation, this is only possible when A_i = i, so that the elements [1, i-1] appear in positions [1, i-1] (in some order), and similarly elements [i+1, N] appear in positions [i+1, N] in some order.
Let’s now look at the prefix [1, i-1] (we’re still under the assumption that A_i is undeletable).
Observe that every element in this prefix is smaller than every element after it. So, it’s surely impossible to perform any move using an element from here and an element from outside.
But then this means this prefix is essentially an independent subproblem (and so is the remaining suffix, for that matter).
That is, we can just take any reachable array from the prefix, and combine it with any reachable array from the suffix.
In fact, note that this is not really dependent on the A_i = i assumption at all - as long as we have some prefix [1, i] such that \max(A_1, A_2, \ldots, A_i) \lt \min(A_{i+1}, \ldots, A_N), the prefix and suffix become independent subproblems, and we can multiply their answers together.
Let’s call a permutation irreducible, if it doesn’t contain an index i such that 1 \leq i \lt N and
\max(A_1, A_2, \ldots, A_i) \lt \min(A_{i+1}, \ldots, A_N).
A permutation that’s not irreducible is called reducible instead.
We’ve already seen that if a permutation is reducible, it can be broken up into two disjoint independent problems, whose answers can then be multiplied.
So, suppose we’re able to solve the problem for an irreducible permutation.
For an arbitrary permutation, we then obtain the following solution:
- Let i_1, i_2, \ldots, i_K be the indices such that \max(A_1, \ldots, A_{i_j}) \lt \min(A_{i_j+1}, \ldots, A_N).
For simplicity, take i_K = N. - Then, each of the sections A[1, i_1], A[i_1+1, i_2], \ldots, A[i_{K-1}+1, i_K] are irreducible, and they’re all disjoint.
So, we can compute the answers for each of them individually, and multiply everything together to obtain the overall answer.
All that remains is to solve for an irreducible permutation.
However, that turns out to be pretty simple: if A is an irreducible permutation, any non-empty sorted subsequence of A is reachable!
Proof
It’s enough to show that any singleton element can be obtained - any larger subsequence can then be obtained by just skipping a couple of deletions.
Consider a graph such that there’s an edge between i and j if and only if i \lt j and A_i \gt A_j.
Note that deleting an element from A is equivalent to deleting a vertex from this graph; and we can only delete a vertex if it has at least one edge incident to it.Suppose we want to have only the element at index k remaining.
Perform a BFS/DFS on the graph starting at k. Then, we can simply delete vertices in reverse order of visit time.
Note that this ensures every remaining vertex will always have an edge incident to it; because at the very least it will remain connected to its “parent”.The only consideration now is connectedness: if the graph is connected we’ll certainly be left with only k, while if it’s not connected we’ll have other connected components (and hence elements remaining in those components, which we do not want).
This is where we use the fact that the permutation is irreducible: the graph of an irreducible permutation will always be connected!
To see why: suppose the graph isn’t connected.
Let i be the smallest index such that i and i+1 are in different components.
This means A_{i+1} must be larger than all of A_1, A_2, \ldots, A_i.Now, observe that it’s impossible for \{1, 2, \ldots, i\} to be a single connected component: if it was, it means all the elements at these indices are smaller than everything after them; which contradicts A being irreducible.
So, there are some indices \gt i which are included in the component of \{1, 2, \ldots, i\}.
However, since this is a connected component, there must be an edge between one of them and \{1, 2, \ldots, i\}.Let this edge be (j, k), where j \leq i and k \gt i.
Note that this implies A_j \gt A_k.
However, since A_{i+1} is larger than the first i elements, we also have A_{i+1} \gt A_k, so the edge (i+1, k) must also exist - meaning i+1 is in the same connected component too, a contradiction!This proves that there can only be a single connected component, so we’re done.
So, for an irreducible permutation, we only need to count the number of sorted subsequences.
That’s a fairly standard problem, and can be solved quickly using a segment tree/fenwick tree using the following algorithm:
- Define c_x to be the number of sorted subsequences ending with the value x.
Initially, c_x = 0 for all x. - Now, for each i = 1, 2, 3, \ldots, N in order:
- Let x = A_i be the current element.
- We then have c_x = c_1 + c_2 + \ldots + c_{x-1} + 1, since we can extend any existing subsequence ending with a smaller element to include x; or we can have the singleton subsequence x itself.
- Compute this sum and update c_x to it, for the sake of future indices.
- The final answer is c_1 + c_2 + \ldots + c_N.
- At each index, we required one range sum query and one point update on the c array.
This is easily handled in logarithmic time by a fenwick tree or segment tree.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/FenwickTree.py
mod = 10**9 + 7
class FenwickTree:
def __init__(self, x):
"""transform list into BIT"""
self.bit = x
for i in range(len(x)):
j = i | (i + 1)
if j < len(x):
x[j] += x[i]
def update(self, idx, x):
"""updates bit[idx] += x"""
while idx < len(self.bit):
self.bit[idx] += x
idx |= idx + 1
def query(self, end):
"""calc sum(bit[:end])"""
x = 0
while end:
x += self.bit[end - 1]
end &= end - 1
return x
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
L, curmx = 0, 0
ans = 1
fen = FenwickTree([0]*(n+1))
for i in range(n):
curmx = max(curmx, a[i])
if curmx != i+1: continue
# solve for [L, i]
sub = fen.query(L+1) % mod
for j in range(L, i+1):
val = fen.query(a[j]) - sub + 1
fen.update(a[j], val % mod)
ans = ans * (fen.query(n+1) - sub) % mod
L = i+1
print(ans)