PRIOC - 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:

Medium

PREREQUISITES:

Combinatorics

PROBLEM:

There are N people, initially standing in the order [1, 2, \ldots, N].
Some of them are priority customers.

You will call some of them several times. If x is called,

  • If x is a priority customer, x will move to the front of the line.
  • If x is not a priority customer, x will move to the front of the line, but then move behind any existing prefix of priority customers.

You’re given the final order of people after some calls have been made.
How many possible subsets of people could have been priority customers?

EXPLANATION:

Observing the process, we can see that at any point of time, the line will look as follows:

  • Some prefix of people who will all be priority customers.
    Specifically, this includes all priority customers who have been called at least once, and also all priority customers who were initially standing at the front of the line.
  • Next, there will be several non-priority customers - specifically, those who have been called at least once.
  • Finally, there will be a suffix of people who have not been called at all.
    These can be priority or non-priority.

This is because a non-priority customer will always be behind a priority customer who was called (or who was initially at the start of the line).

The people who haven’t been called at all, and form the suffix, must be in sorted order.
So, let r be the largest index such that P_r \lt P_{r-1}.
The suffix of not-called people must then be in indices [r, N].

Let’s try to fix the prefix of priority people who were called.
Say, the prefix has length i.
We then have a couple of cases.

First, suppose i \lt r-1.
Then, we surely know that everyone before index r (apart from the length i prefix) cannot have priority; since they must be part of the middle “non-priority people who were called” segment.
Thus, we only need to decide what happens to people at indices \geq r.

It’s tempting to say that any subset of them will be valid, but that’s not always true.

Example

For example, consider A = [1, 4, 2, 3], with the prefix [1] being fixed.
For this array, we have r = 3, with the relevant suffix being [2, 3].
Note that 4 is explicitly not a priority customer here.

Now, observe that if 2 is also a priority customer, then it’s in fact impossible to obtain this ordering.
This is because, starting with [1, 2, 3, 4], 4 will never be able to cross 2.

So, 2 must be a non-priority customer.
3 however can be either priority or non-priority - both are acceptable.

In particular, it can be seen that:

  • If the chosen prefix contains all the values 1, 2, 3, \ldots, A_r - 1, then A_r cannot be a priority customer, since it’ll be impossible for non-priority customers \gt A_r to cross A_r in this case (and i \lt r-1 means such customers do exist).
  • If the chosen prefix doesn’t contain all these values, then A_r can be a priority customer (or not, either is fine).
  • Elements at indices \gt r can freely be priority or non-priority.

So, for a fixed prefix, the number of ways is either 2^{N-r} or 2^{N-r+1}, depending on whether A_r is allowed to be a priority element or not.
This depends only on the number of elements \lt A_r seen so far, which is easily maintained while iterating through the prefix.

That takes care of i \lt r-1.
Next, let’s look at i = r-1, i.e. every element before r-1 is a priority element.

In this case, it’s easy to see that any subset of the last N-r+1 elements can be a priority element, so we add 2^{N-r+1} to the answer.

Finally, we have i \gt r-1.
However, we don’t actually need to process this at all: the i = r-1 case already accounted for all possible subsets of the next N-r+1 elements anyway, which of course includes prefixes extending beyond r.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    ans = 0
    r = 0
    for i in range(n-1):
        if a[i] > a[i+1]: r = i+1
    
    # i < r
    less = 0
    for i in range(r):
        if less == a[r]-1:
            ans += pow(2, n-1-r, mod)
        else:
            ans += pow(2, n-r, mod)
        if a[i] < a[r]: less += 1
    
    # i = r
    ans += pow(2, n-r, mod)
    print(ans % mod)