codeforces-scrape

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

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$.