codeforces-scrape

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

1955D.md (2408B)


      1 Source: https://codeforces.com/problemset/problem/1955/D
      2 
      3 D. Inaccurate Subsequence Search
      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 Maxim has an array $a$ of $n$ integers and an array $b$ of $m$ integers ($m \le n$).
     22 
     23 Maxim considers an array $c$ of length $m$ to be good if the elements of array $c$ can be rearranged in such a way that at least $k$ of them match the elements of array $b$.
     24 
     25 For example, if $b = [1, 2, 3, 4]$ and $k = 3$, then the arrays $[4, 1, 2, 3]$ and $[2, 3, 4, 5]$ are good (they can be reordered as follows: $[1, 2, 3, 4]$ and $[5, 2, 3, 4]$), while the arrays $[3, 4, 5, 6]$ and $[3, 4, 3, 4]$ are not good.
     26 
     27 Maxim wants to choose every subsegment of array $a$ of length $m$ as the elements of array $c$. Help Maxim count how many selected arrays will be good.
     28 
     29 In other words, find the number of positions $1 \le l \le n - m + 1$ such that the elements $a_l, a_{l+1}, \dots, a_{l + m - 1}$ form a good array.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le k \le m \le n \le 2 \cdot 10^5$) — the number of elements in arrays $a$ and $b$, the required number of matching elements.
     36 
     37 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of array $a$. Elements of the array $a$ are not necessarily unique.
     38 
     39 The third line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^6$) — the elements of array $b$. Elements of the array $b$ are not necessarily unique.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output the number of good subsegments of array $a$ on a separate line.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 7 4 2
     55 
     56 4 1 2 3 4 5 6
     57 
     58 1 2 3 4
     59 
     60 7 4 3
     61 
     62 4 1 2 3 4 5 6
     63 
     64 1 2 3 4
     65 
     66 7 4 4
     67 
     68 4 1 2 3 4 5 6
     69 
     70 1 2 3 4
     71 
     72 11 5 3
     73 
     74 9 9 2 2 10 9 7 6 3 6 3
     75 
     76 6 9 7 8 10
     77 
     78 4 1 1
     79 
     80 4 1 5 6
     81 
     82 6
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 4
     89 3
     90 2
     91 4
     92 1
     93 ```
     94 
     95 Note
     96 
     97 In the first example, all subsegments are good.
     98 
     99 In the second example, good subsegments start at positions $1$, $2$, and $3$.
    100 
    101 In the third example, good subsegments start at positions $1$ and $2$.