codeforces-scrape

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

2114C.md (2544B)


      1 Source: https://codeforces.com/problemset/problem/2114/C
      2 
      3 C. Need More Arrays
      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 Given an array $a$ and $n$ integers. It is sorted in non-decreasing order, that is, $a_i \le a_{i + 1}$ for all $1 \le i \lt n$.
     22 
     23 You can remove any number of elements from the array (including the option of not removing any at all) without changing the order of the remaining elements. After the removals, the following will occur:
     24 
     25 * $a_1$ is written to a new array;
     26 * if $a_1 + 1 \lt a_2$, then $a_2$ is written to a new array; otherwise, $a_2$ is written to the same array as $a_1$;
     27 * if $a_2 + 1 \lt a_3$, then $a_3$ is written to a new array; otherwise, $a_3$ is written to the same array as $a_2$;
     28 * $\cdots$
     29 
     30 For example, if $a=[1, 2, 4, 6]$, then:
     31 
     32 * $a_1 = 1$ is written to the new array, resulting in arrays: $[1]$;
     33 * $a_1 + 1 = 2$, so $a_2 = 2$ is added to the existing array, resulting in arrays: $[1, 2]$;
     34 * $a_2 + 1 = 3$, so $a_3 = 4$ is written to a new array, resulting in arrays: $[1, 2]$ and $[4]$;
     35 * $a_3 + 1 = 5$, so $a_4 = 6$ is written to a new array, resulting in arrays: $[1, 2]$, $[4]$, and $[6]$.
     36 
     37 Your task is to remove elements in such a way that the described algorithm creates as many arrays as possible. If you remove all elements from the array, no new arrays will be created.
     38 
     39 Input
     40 
     41 The first line of input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     42 
     43 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array.
     44 
     45 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$, $a_i \le a_{i + 1}$) — the elements of the array.
     46 
     47 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, output one integer — the maximum number of arrays that can be obtained by removing any (possibly zero) number of elements.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 6
     59 
     60 6
     61 
     62 1 2 3 4 5 6
     63 
     64 3
     65 
     66 1 2 3
     67 
     68 4
     69 
     70 1 2 2 4
     71 
     72 1
     73 
     74 2
     75 
     76 3
     77 
     78 1 4 8
     79 
     80 2
     81 
     82 1 1
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 3
     89 2
     90 2
     91 1
     92 3
     93 1
     94 ```
     95 
     96 Note
     97 
     98 In the first example, you can remove $a_3$ and $a_5$, then $a=[1, 2, 4, 6]$, the process of forming arrays for it is shown in the statement.
     99 
    100 In the second example, you need to remove $a_2$, after which $a = [1, 3]$, and the arrays $[1]$ and $[3]$ will be written.
    101 
    102 In the third example, no removals are needed; for $a = [1, 2, 2, 4]$, the arrays $[1, 2, 2]$ and $[4]$ will be written.