FARSWAP - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Dynamic programming

PROBLEM:

You’re given a permutation P.
You are allowed to swap adjacent elements if they differ by at least 2.
Count the number of reachable permutations.

EXPLANATION:

We can only swap adjacent elements that differ by at least 2, which means that for any 1 \le x \lt N, the relative order of x and x+1 cannot be changed.
That is, if x appears before x+1 in P, then any reachable permutation will also have x appear before x+1, and similar logic holds for when x appears after x+1 in P.

Using this idea, we can try to build up final permutations by placing elements from 1 to N (and not by looking at positions.)

In particular, suppose we’ve already placed the elements 1, 2, \ldots, x in some order, and now want to place the element x+1.
Suppose also that x appears before x+1 in P.

Then, x+1 must be placed after x - but it can be placed in any position after x, since every element after x is smaller than x (recall that we only have 1, 2, \ldots, x currently), and so can be freely swapped with x+1 as we like.

This method of building up permutations leads to a dynamic programming solution.

From the above, we see that to place the next element, we only need to know the number of elements placed so far, and the position of the last placed element.

So, define dp(i, j) to be the number of valid ways of placing the values 1, 2, \ldots, i such that i appears at position j (where 1 \le j \le i).

The base case is obviously dp(1, 1) = 1, so let’s now look at transitions.

The element i must appear at position j. As a result:

  • If i-1 appears before i in P, that must hold true here as well.
    So, i-1 must have been at a position that’s smaller than j; but any such position is fine.
    This gives us a total of
    dp(i-1, 1) + dp(i-1, 2) + \ldots + dp(i-1, j-1)
    possible previous configurations, into which we can insert i to obtain a valid configuration with i at position j.
  • If i-1 appears after i in P, again we must ensure that holds true here as well.
    By the same logic, the number of ways is now
    dp(i-1, j) + dp(i-1, j+1) + \ldots + dp(i-1, i-1)
    or really everything other than the first case.

This gives us \mathcal{O}(N^2) states with \mathcal{O}(N) transitions from each one, for \mathcal{O}(N^3) time overall.

However, observe that the transitions in either case are either prefix sums or suffix sums of dp(i-1, \cdot), so by simply maintaining these we can reduce the transitions to \mathcal{O}(1) time, making the overall algorithm \mathcal{O}(N^2).
In fact, you can even observe that dp(i, \cdot) is itself either just the prefix sums or the suffix sums of dp(i-1, \cdot), so “maintain the prefix/suffix sums” is equivalent to just doing the transitions directly; no extra work needed!

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
mod = 998244353

for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    pos = [0]*(n+1)
    for i in range(n): pos[p[i]] = i
    
    dp = [1]
    for i in range(2, n+1):
        if pos[i] > pos[i-1]:
            dp = [0] + dp
            for j in range(1, i):
                dp[j] = (dp[j] + dp[j-1]) % mod
        else:
            dp = dp + [0]
            for j in reversed(range(i-1)):
                dp[j] = (dp[j] + dp[j+1]) % mod
    print(sum(dp) % mod)
2 Likes