codeforces-scrape

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

2148E.md (2216B)


      1 Source: https://codeforces.com/problemset/problem/2148/E
      2 
      3 E. Split
      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 Farmer John has an array $a$ containing $n$ positive integers and an integer $k$.
     22 
     23 Let $a[l, r]$ be a subarray$^{\text{∗}}$ of $a$. He performs the following procedure to independently determine if subarray $a[l, r]$ is awesome:
     24 
     25 * Initially, FJ has $k$ empty [multisets](https://en.wikipedia.org/wiki/Multiset), numbered from $1$ to $k$.
     26 * Then, for each element $a_i$ ($1 \leq i \leq n$) in $a$:
     27   + If $l\leq i\leq r$ (that is, $a_i$ is in the subarray $a[l, r]$), he places $a_i$ in multiset $1$,
     28   + Otherwise, he places $a_i$ into any multiset he wants (which may be multiset $1$).
     29 * Subarray $a[l, r]$ is awesome if there is some way for him to place elements such that, for every value $v$, all multisets contain the same number of elements with value $v$. In other words, he wants to make all multisets contain the exact same elements (ignoring ordering).
     30 
     31 Output the number of awesome subarrays.
     32 
     33 $^{\text{∗}}$For array $a$ of size $n$ and integers $1\leq l\leq r\leq n$, the subarray $a[l, r]$ denotes the array consisting of the elements $a_l, \ldots, a_r$, in order.
     34 
     35 Input
     36 
     37 The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     38 
     39 The first line of each test case contains two integers $n$ and $k$ ($2 \leq k \le n \leq 2 \cdot 10^5$).
     40 
     41 The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each testcase, output one integer on a new line: the number of awesome subarrays.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 3 2
     57 
     58 1 1 1
     59 
     60 4 2
     61 
     62 1 2 1 2
     63 
     64 8 2
     65 
     66 3 3 3 3 2 2 2 2
     67 
     68 6 3
     69 
     70 1 1 1 1 1 1
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 0
     77 7
     78 18
     79 11
     80 ```
     81 
     82 Note
     83 
     84 Test case 1: $n=3$, $a=[1,1,1]$.
     85 
     86 For $k=2$, you cannot finish with the same number of $1$'s in both multisets, so no subarray works.
     87 
     88 Test case 2: $n=4$, $a=[1,2,1,2]$.
     89 
     90 For $k=2$, the final state must give each multiset exactly one $1$ and one $2$. Thus a valid subarray can contain at most one $1$ and at most one $2$.