The Forbidden Permutation (Codeforces 1778B)
Tags: Greedy, math

You are given a permutation $$$p$$$ of length $$$n$$$, an array of $$$m$$$ distinct integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le n$$$), and an integer $$$d$$$.Let $$$\mathrm{pos}(x)$$$ be the index of $$$x$$$ in the permutation $$$p$$$. The array $$$a$$$ is not good if   $$$\mathrm{pos}(a_{i}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$$$ for all $$$1 \le i < m$$$. For example, with the permutation $$$p = [4, 2, 1, 3, 6, 5]$$$ and $$$d = 2$$$:   $$$a = [2, 3, 6]$$$ is a not good array.  $$$a = [2, 6, 5]$$$ is good because $$$\mathrm{pos}(a_1) = 2$$$, $$$\mathrm{pos}(a_2) = 5$$$, so the condition $$$\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$$$ is not satisfied.  $$$a = [1, 6, 3]$$$ is good because $$$\mathrm{pos}(a_2) = 5$$$, $$$\mathrm{pos}(a_3) = 4$$$, so the condition $$$\mathrm{pos}(a_2) < \mathrm{pos}(a_3)$$$ is not satisfied. In one move, you can swap two adjacent elements of the permutation $$$p$$$. What is the minimum number of moves needed such that the array $$$a$$$ becomes good? It can be shown that there always exists a sequence of moves so that the array $$$a$$$ becomes good.A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but there is $$$4$$$ in the array).

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$d$$$ ($$$2\leq n \leq 10^5$$$, $$$2\leq m\leq n$$$, $$$1 \le d \le n$$$), the length of the permutation $$$p$$$, the length of the array $$$a$$$ and the value of $$$d$$$. The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1\leq p_i \leq n$$$, $$$p_i \ne p_j$$$ for $$$i \ne j$$$). The third line contains $$$m$$$ distinct integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1\leq a_i \leq n$$$, $$$a_i \ne a_j$$$ for $$$i \ne j$$$).The sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output: For each test case, print the minimum number of moves needed such that the array $$$a$$$ becomes good.

Note: In the first case, $$$pos(a_1)=1$$$, $$$pos(a_2)=3$$$. To make the array good, one way is to swap $$$p_3$$$ and $$$p_4$$$. After that, the array $$$a$$$ will be good because the condition $$$\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$$$ won't be satisfied.In the second case, $$$pos(a_1)=1$$$, $$$pos(a_2)=4$$$. The $$$3$$$ moves could be:   Swap $$$p_3$$$ and $$$p_4$$$.  Swap $$$p_2$$$ and $$$p_3$$$.  Swap $$$p_1$$$ and $$$p_2$$$.  After these moves, the permutation $$$p$$$ will be $$$[2,5,4,3,1]$$$. The array $$$a$$$ will be good because the condition $$$\mathrm{pos}(a_1) < \mathrm{pos}(a_2)$$$ won't be satisfied. It can be shown that you can't make the array $$$a$$$ good with fewer moves.In the third case, $$$pos(a_1)=1$$$, $$$pos(a_2)=3$$$, $$$pos(a_3)=5$$$. The $$$2$$$ moves can be:   Swap $$$p_4$$$ and $$$p_5$$$.  Swap $$$p_3$$$ and $$$p_4$$$.  After these moves, the permutation $$$p$$$ will be $$$[3,4,2,1,5]$$$. The array $$$a$$$ will be good because the condition $$$\mathrm{pos}(a_2) < \mathrm{pos}(a_3)$$$ won't be satisfied. It can be shown that you can't make the array $$$a$$$ good with fewer moves.In the fourth case, $$$pos(a_1)=2$$$, $$$pos(a_2)=1$$$. The array $$$a$$$ is already good.In the fifth case, $$$pos(a_1)=2$$$, $$$pos(a_2)=5$$$. The $$$2$$$ moves are:   Swap $$$p_1$$$ and $$$p_2$$$.  Swap $$$p_5$$$ and $$$p_6$$$. 

Sample Inputs:
5
4 2 2
1 2 3 4
1 3
5 2 4
5 4 3 2 1
5 2
5 3 3
3 4 1 5 2
3 1 2
2 2 1
1 2
2 1
6 2 4
1 2 3 4 5 6
2 5

Sample Outputs:
1
3
2
0
2

Solution (Python):
t = int(input())
for i in range(0, t):
    (n, m, d) = map(int, input().split())
    p = list(map(int, input().split()))
    a = list(map(int, input().split()))
    position_list = []
    for j in range(0, n):
        position_list.append(0)
    for j in range(0, n):
        position_list[p[j] - 1] = j + 1
    diff_list = []
    for j in range(1, m):
        diff_list.append(position_list[a[j] - 1] - position_list[a[j - 1] - 1])
    diff_list.sort()
    if diff_list[0] < 0 or diff_list[m - 2] > d:
        print(0)
        continue
    if d >= n - 1:
        print(diff_list[0])
    else:
        print(min(diff_list[0], d + 1 - diff_list[m - 2]))

Solution (Python):
def Solve(d, permutation, a):
    positions = [-1 for i in range(len(permutation) + 1)]
    for i in range(len(permutation)):
        positions[permutation[i]] = i
    minswaps = float('inf')
    for i in range(len(a) - 1):
        swaps = positions[a[i + 1]] - positions[a[i]]
        if swaps <= 0:
            return 0
        elif swaps < minswaps:
            minswaps = swaps
        swaps = positions[a[i]] + d - positions[a[i + 1]]
        if swaps < 0:
            return 0
        elif swaps + 1 < minswaps:
            if len(permutation) - 1 - positions[a[i + 1]] + positions[a[i]] >= swaps + 1:
                minswaps = swaps + 1
    return minswaps
if __name__ == '__main__':
    t = int(input())
    output = []
    for i in range(t):
        (n, m, d) = list(map(int, input().split()))
        permutation = list(map(int, input().split()))
        a = list(map(int, input().split()))
        output.append(Solve(d, permutation, a))
    for answer in output:
        print(answer)

Solution (Python):
tc = int(input())
for _ in range(tc):
    (n, m, d) = map(int, input().split())
    pos = list(map(int, input().split()))
    cst = list(map(int, input().split()))
    dct = {}
    for i in range(n):
        dct[pos[i]] = i
    mn = 200000000000
    mx = 200000000000
    for i in range(1, m):
        length = dct[cst[i]] - dct[cst[i - 1]]
        if mn > length:
            mn = length
        if mx > d + 1 - length:
            mx = d + 1 - length
    if mn < 0 or mx < 0:
        print(0)
    elif d + 1 >= n:
        print(mn)
    else:
        print(min(mn, mx))