codeforces-scrape

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

2227D.md (2495B)


      1 Source: https://codeforces.com/problemset/problem/2227/D
      2 
      3 D. Palindromex
      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 Yousef has given you an array $a$ of $2n$ integers. Every integer $x \in [0, n - 1]$ appears exactly twice in the array.
     22 
     23 Your task is to find a subarray $a_l, a_{l + 1}, \dots, a_r$ that is a palindrome$^{\text{∗}}$ such that its $\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$$^{\text{†}}$ is maximized. Output this maximum possible value.
     24 
     25 $^{\text{∗}}$A palindrome is a string that reads the same backward as forward, for example, strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.
     26 
     27 $^{\text{†}}$The $\operatorname{mex}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:
     28 
     29 * The $\operatorname{mex}$ of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
     30 * The $\operatorname{mex}$ of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
     31 * The $\operatorname{mex}$ of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).
     38 
     39 The second line of each test case contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($0 \le a_i \le n-1$). It is guaranteed that every integer in the range $[0, n-1]$ appears exactly twice.
     40 
     41 It is guaranteed that the sum of $2n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output a single integer — the maximum $\operatorname{mex}$ of any palindromic subarray.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 
     54 4
     55 
     56 1 2 0 3 3 0 2 1
     57 
     58 2
     59 
     60 0 1 0 1
     61 
     62 2
     63 
     64 1 1 0 0
     65 
     66 3
     67 
     68 2 0 2 1 1 0
     69 
     70 4
     71 
     72 0 1 3 0 3 1 2 2
     73 
     74 3
     75 
     76 0 1 2 1 0 2
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 4
     83 
     84 2
     85 
     86 1
     87 
     88 1
     89 
     90 2
     91 
     92 3
     93 ```
     94 
     95 Note
     96 
     97 In the first test case, the only optimal subarray to choose is $a[1, 8] = [1, 2, 0, 3, 3, 0, 2, 1]$, which is palindromic and has a $\operatorname{mex}$ of $4$.
     98 
     99 In the second test case, one of the optimal subarrays to choose is $a[2, 4] = [1, 0, 1]$, which is palindromic and has a $\operatorname{mex}$ of $2$.
    100 
    101 In the third test case, we can choose $a[3, 3] = [0]$, which is palindromic and has a $\operatorname{mex}$ of $1$. No other palindromic subarray has a $\operatorname{mex}$ greater than $1$.