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 90
EXPLANATION:
Let’s fix the values x and y, and try to compute the minimum number of swaps needed to make [x, x+1, \ldots, y] appear as a subsequence of P.
If we can do this in reasonable time, applying this to all pairs (x, y) will allow us to easily compute the answer, since it will simply be the maximum of
across all (x, y).
With x and y fixed, observe that any swap we make must be one of two types:
- Swapping two elements that both lie in the range [x, y].
- Swapping an element that is in [x, y] with an element outside this range.
In particular, we never need to swap two elements that both lie outside [x, y].
Let’s work with the two types of swaps separately.
First, consider swaps between two elements of [x, y].
Clearly, such a swap must be done only when the pair of elements forms an inversion, i.e. the smaller one comes after the larger one.
So, the number of such swaps is exactly the number of inversions among elements in [x, y].
This quantity can be easily calculated in \mathcal{O}(N^2) time (or faster, but the brute-force quadratic algorithm is good enough for us here.)
Next, let’s consider swaps between an element of [x, y] and an element not in [x, y].
These are needed to move elements across ‘gaps’: for example, if we have something like [\ldots, 2, a, b, c, 1, \ldots] and want to move the 1 before the 2, we’ll have to perform swaps with all of a, b, c, with at least one of 1 and 2.
To analyze this better, it’s helpful to look at it from an element-wise perspective, and consider the final configuration.
That is, let’s fix some element a \not \in [x, y].
In the final configuration, we’ll have the subsequence [x, x+1, \ldots, y], and then there will be (y-x+2) possible “gaps” between these elements (including before x and after y).
a must then fit into one of these gaps.
Which gap should it go to?
Well, if we want a to end up in the gap between values i and i+1, we see that:
- a must swap once with every value to its right that’s in [x, i].
- a must also swap once with every value to its left that’s in [i+1, y].
- This is necessary, and clearly also sufficient for a to end up between i and i+1 in the end.
If a and i are fixed, this computation can be done easily in linear time.
The optimal swap cost for a is then the minimum of this cost across all i.
Now, observe that since we never need to swap two elements that are both outside [x, y], this optimal cost that we compute for a is in fact completely independent of the optimal costs for any other value.
Thus, we can simply compute the optimal cost for each a \not\in [x, y] independently, and add them all up to get the overall number of swaps needed.
We now have an algorithm that runs in \mathcal{O}(N^5), since we do the following:
- Fix x and y, x \le y
- Compute inversions between elements in [x, y].
- This takes quadratic time.
- Then, fix a value a \not \in [x, y]
- For each i \in [x-1, y], compute the cost of placing a in the gap between i and i+1.
- This takes linear time for a fixed i, leading to \mathcal{O}(N^2) overall (given that x, y, a are fixed.)
- The cost for a is the minimum across all i.
To optimize this to \mathcal{O}(N^4), observe that for a fixed a, if we know the cost for placing it between i and i+1, the cost for placing it between i+1 and i+2 instead can be recomputed quickly; and depends only on the relative position of i+1 compared to a.
This allows us to throw out the innermost loop with a little computation, and hence obtain an algorithm that runs in \mathcal{O}(N^4) which is fast enough.
TIME COMPLEXITY:
\mathcal{O}(N^4) 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
for x in range(1, n+1):
for y in range(x, n+1):
invs = 0
for i in range(x, y+1):
for j in range(i+1, y+1):
invs += pos[j] < pos[i]
outside = 0
for a in range(1, n+1):
if x <= a <= y: continue
curcost = 0
# before
for i in range(x, y+1):
curcost += pos[i] < pos[a]
opt = curcost
for i in range(x, y+1):
# was in [i-1, i]
# now in [i, i+1]
# change only cost of i
if pos[i] < pos[a]: curcost -= 1
else: curcost += 1
opt = min(opt, curcost)
outside += opt
ans = max(ans, y-x+1 - invs - outside)
print(ans)