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

Dynamic Programming

PROBLEM:

You’re given a permutation P.
Define f(P) to be the length of the longest subsequence of the form [x, x+1, \ldots, y] in P.

You are allowed to swap adjacent elements of P however many times you like.
Find the maximum possible value of f(P) - \text{swaps}.

In this version of the problem, N \le 600.

EXPLANATION:

Recall from the easy version of the problem that our algorithm was as follows:

  • Fix x and y, saying we want to obtain [x, \ldots, y] as a subsequence.
  • The cost of swaps for this equals inversions in [x, y], plus the cost of swaps between elements of [x, y] and elements outside.
  • To compute the latter, we fixed an outside element, and then found the minimal cost for it to end up between i and i+1 for each i = x-1, \ldots, y, and then took the minimum of these all.

Both parts of the algorithm were \mathcal{O}(N^4), so we need to improve both.
We’ll do that separately.

First, let’s work on inversions.

Define \text{inv}[x][y] to be the number of inversions among elements [x, x+1, \ldots, y].

Observe that \text{inv}[x][y] can be computed from \text{inv}[x][y-1] in linear time, since we only need to check for inversions involving y against all of the other elements in [x, y-1].
This immediately improves the complexity of computing all-pairs of inversions to \mathcal{O}(N^3), so this part is now fine.

This can be further improved to \mathcal{O}(N^2) using 2D prefix sum-based updates, though that’s not needed for this problem.

Next, we look at the elements outside [x, y].

Let \text{cost}[x][y][a][i] denote the minimum number of swaps needed to place a between i and i+1, and let \text{opt}[x][y][a] = \min_i(\text{cost}[x][y][a][i]).

Our \mathcal{O}(N^4) algorithm was to compute \text{cost}[x][y][a][i] from \text{cost}[x][y][a][i-1] in constant time, and then compute \text{opt}[x][y][a] once all costs were known.

Let’s instead look at changing a different index: specifically, consider \text{cost}[x][y+1][a][i].
Here, note that:

  • If y+1 appears after a, then for any i \le y it’s never needed to swap a with y+1 anyway.
    So, we simply have \text{cost}[x][y+1][a][i] = \text{cost}[x][y][a][i] for i \le y.
    Thus, only \text{cost}[x][y+1][a][y+1] needs to be computed separately.
  • If y+1 appears before a, then for any i \le y it’s always needed to swap y+1 with a.
    So, we have \text{cost}[x][y+1][a][i] = \text{cost}[x][y][a][i]+1 for i \le y.
    Again, \text{cost}[x][y+1][a][y+1] needs to be computed separately.

In particular, since the costs for all y \le a change by the same delta, we have:

  • If y+1 appears after a, then \text{opt}[x][y+1][a] = \min(\text{opt}[x][y+1][a], \text{cost}[x][y+1][a][y+1])
  • If y+1 appears before a, then \text{opt}[x][y+1][a] = \min(\text{opt}[x][y+1][a]+1, \text{cost}[x][y+1][a][y+1])

In particular, if we’re able to compute \text{cost}[x][y+1][a][y+1] quickly, we can in fact update \text{opt}[x][y+1][a] in constant time.
This is not hard: note that \text{cost}[x][y+1][a][y+1] simply equals the number of elements in [x, y+1] that appear after a, which can be updated in constant time when moving from (x, y) to (x, y+1) just as we did with the inversions (since only the relative position of y+1 and a matters).

This optimizes the algorithm to \mathcal{O}(N^3), which is now fast enough.

This algorithm can be implemented using \mathcal{O}(N) space - see the code below.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
import sys
input = sys.stdin.readline
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

    ans = 0
    opt = [0]*(n+1)
    right = [0]*(n+1)
    for x in range(1, n+1):
        invs = 0
        for i in range(n+1): opt[i] = right[i] = 0

        for y in range(x, n+1):
            
            for i in range(1, n+1):
                if x <= i < y: invs += pos[i] > pos[y]
                right[i] += pos[y] > pos[i]
            
            for a in range(1, n+1):
                if x <= a <= y: continue
                if pos[a] > pos[y]: opt[a] += 1
                opt[a] = min(opt[a], right[a])

            ans = max(ans, y-x+1 - invs - sum(opt[:x]) - sum(opt[y+1:]))
    print(ans)