codeforces-scrape

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

2117C.md (2482B)


      1 Source: https://codeforces.com/problemset/problem/2117/C
      2 
      3 C. Cool Partition
      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 an array $a$ of size $n$. He wants to partition the array into one or more contiguous segments such that each element $a_i$ belongs to exactly one segment.
     22 
     23 A partition is called cool if, for every segment $b_j$, all elements in $b_j$ also appear in $b_{j + 1}$ (if it exists). That is, every element in a segment must also be present in the segment following it.
     24 
     25 For example, if $a = [1, 2, 2, 3, 1, 5]$, a cool partition Yousef can make is $b_1 = [1, 2]$, $b_2 = [2, 3, 1, 5]$. This is a cool partition because every element in $b_1$ (which are $1$ and $2$) also appears in $b_2$. In contrast, $b_1 = [1, 2, 2]$, $b_2 = [3, 1, 5]$ is not a cool partition, since $2$ appears in $b_1$ but not in $b_2$.
     26 
     27 Note that after partitioning the array, you do not change the order of the segments. Also, note that if an element appears several times in some segment $b_j$, it only needs to appear at least once in $b_{j + 1}$.
     28 
     29 Your task is to help Yousef by finding the maximum number of segments that make a cool partition.
     30 
     31 Input
     32 
     33 The first line of the input contains integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print one integer — the maximum number of segments that make a cool partition.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 8
     51 
     52 6
     53 
     54 1 2 2 3 1 5
     55 
     56 8
     57 
     58 1 2 1 3 2 1 3 2
     59 
     60 5
     61 
     62 5 4 3 2 1
     63 
     64 10
     65 
     66 5 8 7 5 8 5 7 8 10 9
     67 
     68 3
     69 
     70 1 2 2
     71 
     72 9
     73 
     74 3 3 1 4 3 2 4 1 2
     75 
     76 6
     77 
     78 4 5 4 5 6 4
     79 
     80 8
     81 
     82 1 2 1 2 1 2 1 2
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 2
     89 3
     90 1
     91 3
     92 1
     93 3
     94 3
     95 4
     96 ```
     97 
     98 Note
     99 
    100 The first test case is explained in the statement. We can partition it into $b_1 = [1, 2]$, $b_2 = [2, 3, 1, 5]$. It can be shown there is no other partition with more segments.
    101 
    102 In the second test case, we can partition the array into $b_1 = [1, 2]$, $b_2 = [1, 3, 2]$, $b_3 = [1, 3, 2]$. The maximum number of segments is $3$.
    103 
    104 In the third test case, the only partition we can make is $b_1 = [5, 4, 3, 2, 1]$. Any other partition will not satisfy the condition. Therefore, the answer is $1$.