codeforces-scrape

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

2242C.md (3159B)


      1 Source: https://codeforces.com/problemset/problem/2242/C
      2 
      3 C. Unstable Elements
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a sorted array of integers $[a_1, a_2, \dots, a_n]$. We can perform any number of operations of the following type on this array:
     22 
     23 * mark the first element of the array, as well as all elements that are not equal to their left neighbors (that is, all elements $i$ such that $a_i \ne a_{i-1}$).
     24 * then either delete all marked elements or duplicate them (that is, replace each marked element with two identical elements).
     25 
     26 For example, consider the array $[\mathbf{1}, 1, 1, \mathbf{2}, \mathbf{4}, 4, \mathbf{5}]$ (marked elements are shown in bold). If we delete all marked elements, we get $[1, 1, 4]$, and if we duplicate them, we get $[1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5]$.
     27 
     28 The operations cannot be performed if the array becomes empty. After each operation, every element gets unmarked.
     29 
     30 We call an array of integers $b$ reachable if it can be obtained from array $a$ by some number of the described operations. Your task is to count the number of reachable arrays of length $k$.
     31 
     32 Input
     33 
     34 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     35 
     36 Each test case consists of two lines:
     37 
     38 * the first line contains two integers $n$ and $k$ ($1 \le n, k \le 3 \cdot 10^5$);
     39 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le n$). Note that the array is sorted.
     40 
     41 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output one integer — the number of reachable arrays $b$ of length $k$. It can be shown that, under the constraints of the problem, the answer fits into a standard $32$-bit integer type.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 10
     53 
     54 1 5
     55 
     56 1
     57 
     58 4 5
     59 
     60 1 1 2 2
     61 
     62 3 1
     63 
     64 1 1 1
     65 
     66 4 8
     67 
     68 1 2 3 4
     69 
     70 8 6
     71 
     72 1 1 1 2 2 2 2 2
     73 
     74 6 3
     75 
     76 1 1 2 2 3 3
     77 
     78 10 7
     79 
     80 1 1 1 2 2 3 3 3 3 4
     81 
     82 12 5
     83 
     84 1 1 1 1 2 2 2 3 3 4 4 4
     85 
     86 6 5
     87 
     88 1 1 2 2 3 3
     89 
     90 3 1
     91 
     92 1 2 2
     93 ```
     94 
     95 Output
     96 
     97 ```
     98 1
     99 
    100 0
    101 
    102 1
    103 
    104 1
    105 
    106 2
    107 
    108 1
    109 
    110 2
    111 
    112 1
    113 
    114 0
    115 
    116 1
    117 ```
    118 
    119 Note
    120 
    121 In the first example, the following sequence of operations can be performed:
    122 
    123 * $[\mathbf{1}] \rightarrow [\mathbf{1}, 1] \rightarrow [\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1, 1, 1] \rightarrow [1, 1, 1, 1, 1]$.
    124 
    125 In the second example, it is impossible to obtain an array of length $5$.
    126 
    127 In the third example, the following sequence of operations can be performed:
    128 
    129 * $[\mathbf{1}, 1, 1] \rightarrow [\mathbf{1}, 1] \rightarrow [1]$.
    130 
    131 In the fifth example, the arrays $[1, 1, 2, 2, 2, 2]$ and $[2, 2, 2, 2, 2, 2]$ can be obtained:
    132 
    133 * $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [1, 1, 2, 2, 2, 2]$;
    134 * $[\mathbf{1}, 1, 1, \mathbf{2}, 2, 2, 2, 2] \rightarrow [\mathbf{1}, 1, \mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{1}, \mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2] \rightarrow [\mathbf{2}, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2] \rightarrow [\mathbf{2}, 2, 2, 2, 2] \rightarrow [2, 2, 2, 2, 2, 2]$.
    135 
    136 In the seventh example, the arrays $[1, 1, 1, 3, 3, 3, 3]$ and $[3, 3, 3, 3, 3, 3, 3]$ can be obtained.