codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1778B.md (3712B)


      1 Source: https://codeforces.com/problemset/problem/1778/B
      2 
      3 B. The Forbidden Permutation
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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$.
     22 
     23 Let $\mathrm{pos}(x)$ be the index of $x$ in the permutation $p$. The array $a$ is not good if
     24 
     25 * $\mathrm{pos}(a_{i}) \lt \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$ for all $1 \le i \lt m$.
     26 
     27 For example, with the permutation $p = [4, 2, 1, 3, 6, 5]$ and $d = 2$:
     28 
     29 * $a = [2, 3, 6]$ is a not good array.
     30 * $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.
     31 * $a = [1, 6, 3]$ is good because $\mathrm{pos}(a_2) = 5$, $\mathrm{pos}(a_3) = 4$, so the condition $\mathrm{pos}(a_2) \lt \mathrm{pos}(a_3)$ is not satisfied.
     32 
     33 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.
     34 
     35 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).
     36 
     37 Input
     38 
     39 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.
     40 
     41 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$.
     42 
     43 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$).
     44 
     45 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$).
     46 
     47 The sum of $n$ over all test cases doesn't exceed $5 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, print the minimum number of moves needed such that the array $a$ becomes good.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 5
     59 
     60 4 2 2
     61 
     62 1 2 3 4
     63 
     64 1 3
     65 
     66 5 2 4
     67 
     68 5 4 3 2 1
     69 
     70 5 2
     71 
     72 5 3 3
     73 
     74 3 4 1 5 2
     75 
     76 3 1 2
     77 
     78 2 2 1
     79 
     80 1 2
     81 
     82 2 1
     83 
     84 6 2 4
     85 
     86 1 2 3 4 5 6
     87 
     88 2 5
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 1
     95 3
     96 2
     97 0
     98 2
     99 ```
    100 
    101 Note
    102 
    103 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.
    104 
    105 In the second case, $pos(a_1)=1$, $pos(a_2)=4$. The $3$ moves could be:
    106 
    107 1. Swap $p_3$ and $p_4$.
    108 2. Swap $p_2$ and $p_3$.
    109 3. Swap $p_1$ and $p_2$.
    110 
    111 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) \lt \mathrm{pos}(a_2)$ won't be satisfied. It can be shown that you can't make the array $a$ good with fewer moves.
    112 
    113 In the third case, $pos(a_1)=1$, $pos(a_2)=3$, $pos(a_3)=5$. The $2$ moves can be:
    114 
    115 1. Swap $p_4$ and $p_5$.
    116 2. Swap $p_3$ and $p_4$.
    117 
    118 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) \lt \mathrm{pos}(a_3)$ won't be satisfied. It can be shown that you can't make the array $a$ good with fewer moves.
    119 
    120 In the fourth case, $pos(a_1)=2$, $pos(a_2)=1$. The array $a$ is already good.
    121 
    122 In the fifth case, $pos(a_1)=2$, $pos(a_2)=5$. The $2$ moves are:
    123 
    124 1. Swap $p_1$ and $p_2$.
    125 2. Swap $p_5$ and $p_6$.