codeforces-scrape

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

1842C.md (1698B)


      1 Source: https://codeforces.com/problemset/problem/1842/C
      2 
      3 C. Tenzing and Balls
      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 Enjoy erasing Tenzing, identified as Accepted!
     22 
     23 Tenzing has $n$ balls arranged in a line. The color of the $i$-th ball from the left is $a_i$.
     24 
     25 Tenzing can do the following operation any number of times:
     26 
     27 * select $i$ and $j$ such that $1\leq i \lt j \leq |a|$ and $a_i=a_j$,
     28 * remove $a_i,a_{i+1},\ldots,a_j$ from the array (and decrease the indices of all elements to the right of $a_j$ by $j-i+1$).
     29 
     30 Tenzing wants to know the maximum number of balls he can remove.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1\leq t\leq 10^3$) — the number of test cases. The description of test cases follows.
     35 
     36 The first line contains a single integer $n$ ($1\leq n\leq 2\cdot 10^5$) — the number of balls.
     37 
     38 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq n$) — the color of the balls.
     39 
     40 It is guaranteed that sum of $n$ of all test cases will not exceed $2\cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, output the maximum number of balls Tenzing can remove.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 2
     52 
     53 5
     54 
     55 1 2 2 3 3
     56 
     57 4
     58 
     59 1 2 1 2
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 4
     66 3
     67 ```
     68 
     69 Note
     70 
     71 In the first example, Tenzing will choose $i=2$ and $j=3$ in the first operation so that $a=[1,3,3]$. Then Tenzing will choose $i=2$ and $j=3$ again in the second operation so that $a=[1]$. So Tenzing can remove $4$ balls in total.
     72 
     73 In the second example, Tenzing will choose $i=1$ and $j=3$ in the first and only operation so that $a=[2]$. So Tenzing can remove $3$ balls in total.