2117E.md (3321B)
1 Source: https://codeforces.com/problemset/problem/2117/E 2 3 E. Lost Soul 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 two integer arrays $a$ and $b$, each of length $n$. 22 23 You may perform the following operation any number of times: 24 25 * Choose an index $i$ $(1 \le i \le n - 1)$, and set $a_i := b_{i + 1}$, or set $b_i := a_{i + 1}$. 26 27 Before performing any operations, you are allowed to choose an index $i$ $(1 \le i \le n)$ and remove both $a_i$ and $b_i$ from the arrays. This removal can be done at most once. 28 29 Let the number of matches between two arrays $c$ and $d$ of length $m$ be the number of positions $j$ $(1 \le j \le m)$ such that $c_j = d_j$. 30 31 Your task is to compute the maximum number of matches you can achieve. 32 33 Input 34 35 The first line of the input contains an integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. The description of each test case follows. 36 37 The first line contains an integer $n$ $(2 \le n \le 2 \cdot 10^5)$ — the length of $a$ and $b$. 38 39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$ — the elements of $a$. 40 41 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ $(1 \le b_i \le n)$ — the elements of $b$. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, print a single integer — the answer for the test case. 48 49 Example 50 51 Input 52 53 ``` 54 10 55 56 4 57 58 1 3 1 4 59 60 4 3 2 2 61 62 6 63 64 2 1 5 3 6 4 65 66 3 2 4 5 1 6 67 68 2 69 70 1 2 71 72 2 1 73 74 6 75 76 2 5 1 3 6 4 77 78 3 5 2 3 4 6 79 80 4 81 82 1 3 2 2 83 84 2 1 3 4 85 86 8 87 88 3 1 4 6 2 2 5 7 89 90 4 2 3 7 1 1 6 5 91 92 10 93 94 5 1 2 7 3 9 4 10 6 8 95 96 6 2 3 6 4 10 5 1 7 9 97 98 5 99 100 3 2 4 1 5 101 102 2 4 5 1 3 103 104 7 105 106 2 2 6 4 1 3 5 107 108 3 1 6 5 1 4 2 109 110 5 111 112 4 1 3 2 5 113 114 3 2 1 5 4 115 ``` 116 117 Output 118 119 ``` 120 3 121 3 122 0 123 4 124 3 125 5 126 6 127 4 128 5 129 2 130 ``` 131 132 Note 133 134 In the first test case, we can do the following: 135 136 * We will choose not to remove any index. 137 * Choose index $3$, and set $a_3 := b_4$. The arrays become: $a = [1, 3, 2, 4]$, $b = [4, 3, 2, 2]$. 138 * Choose index $1$, and set $a_1 := b_2$. The arrays become: $a = [3, 3, 2, 4]$, $b = [4, 3, 2, 2]$. 139 * Choose index $1$, and set $b_1 := a_2$. The arrays become: $a = [3, 3, 2, 4]$, $b = [3, 3, 2, 2]$. Notice that you can perform $a_i := b_{i + 1}$ and $b_i := a_{i + 1}$ on the same index $i$. 140 141 The number of matches is $3$. It can be shown that this is the maximum answer we can achieve. 142 143 In the second test case, we can do the following to achieve a maximum of $3$: 144 145 * Let's choose to remove index $5$. The arrays become: $a = [2, 1, 5, 3, 4]$, $b = [3, 2, 4, 5, 6]$. 146 * Choose index $4$, and set $b_4 := a_5$. The arrays become: $a = [2, 1, 5, 3, 4]$, $b = [3, 2, 4, 4, 6]$. 147 * Choose index $3$, and set $a_3 := b_4$. The arrays become: $a = [2, 1, 4, 3, 4]$, $b = [3, 2, 4, 4, 6]$. 148 * Choose index $2$, and set $a_2 := b_3$. The arrays become: $a = [2, 4, 4, 3, 4]$, $b = [3, 2, 4, 4, 6]$. 149 * Choose index $1$, and set $b_1 := a_2$. The arrays become: $a = [2, 4, 4, 3, 4]$, $b = [4, 2, 4, 4, 6]$. 150 * Choose index $2$, and set $b_2 := a_3$. The arrays become: $a = [2, 4, 4, 3, 4]$, $b = [4, 4, 4, 4, 6]$. 151 * Choose index $1$, and set $a_1 := b_2$. The arrays become: $a = [4, 4, 4, 3, 4]$, $b = [4, 4, 4, 4, 6]$. 152 153 In the third test case, it can be shown that we can not get any matches. Therefore, the answer is $0$.