codeforces-scrape

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

1831B.md (2043B)


      1 Source: https://codeforces.com/problemset/problem/1831/B
      2 
      3 B. Array merging
      4 
      5 time limit per test
      6 
      7 1 second
      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 arrays $a$ and $b$ both of length $n$.
     22 
     23 You will merge$^\dagger$ these arrays forming another array $c$ of length $2 \cdot n$. You have to find the maximum length of a subarray consisting of equal values across all arrays $c$ that could be obtained.
     24 
     25 $^\dagger$ A merge of two arrays results in an array $c$ composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of $c$. We repeat this operation as long as we can (i.e. at least one array is nonempty).
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$ and $b$.
     32 
     33 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 2 \cdot n$) — the elements of array $a$.
     34 
     35 The third line of each test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($1 \le b_i \le 2 \cdot n$) — the elements of array $b$.
     36 
     37 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output the maximum length of a subarray consisting of equal values across all merges.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 1
     51 
     52 2
     53 
     54 2
     55 
     56 3
     57 
     58 1 2 3
     59 
     60 4 5 6
     61 
     62 2
     63 
     64 1 2
     65 
     66 2 1
     67 
     68 5
     69 
     70 1 2 2 2 2
     71 
     72 2 1 1 1 1
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 2
     79 1
     80 2
     81 5
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, we can only make $c=[2,2]$, thus the answer is $2$.
     87 
     88 In the second test case, since all values are distinct, the answer must be $1$.
     89 
     90 In the third test case, the arrays $c$ we can make are $[1,2,1,2]$, $[1,2,2,1]$, $[2,1,1,2]$, $[2,1,2,1]$. We can see that the answer is $2$ when we choose $c=[1,2,2,1]$.