codeforces-scrape

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

2003D1.md (3989B)


      1 Source: https://codeforces.com/problemset/problem/2003/D1
      2 
      3 D1. Turtle and a MEX Problem (Easy Version)
      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 The two versions are different problems. In this version of the problem, you can choose the same integer twice or more. You can make hacks only if both versions are solved.
     22 
     23 One day, Turtle was playing with $n$ sequences. Let the length of the $i$-th sequence be $l_i$. Then the $i$-th sequence was $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$.
     24 
     25 Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was:
     26 
     27 * There was a non-negative integer $x$ at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer.
     28 * In each operation, Turtle could choose an integer $i$ such that $1 \le i \le n$, and set $x$ to $\text{mex}^{\dagger}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i})$.
     29 * Turtle was asked to find the answer, which was the maximum value of $x$ after performing an arbitrary number of operations.
     30 
     31 Turtle solved the above problem without difficulty. He defined $f(k)$ as the answer to the above problem when the initial value of $x$ was $k$.
     32 
     33 Then Piggy gave Turtle a non-negative integer $m$ and asked Turtle to find the value of $\sum\limits_{i = 0}^m f(i)$ (i.e., the value of $f(0) + f(1) + \ldots + f(m)$). Unfortunately, he couldn't solve this problem. Please help him!
     34 
     35 $^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k)$ is defined as the smallest non-negative integer $x$ which does not occur in the sequence $c$. For example, $\text{mex}(2, 2, 0, 3)$ is $1$, $\text{mex}(1, 2)$ is $0$.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     40 
     41 The first line of each test case contains two integers $n, m$ ($1 \le n \le 2 \cdot 10^5, 0 \le m \le 10^9$).
     42 
     43 Each of the following $n$ lines contains several integers. The first integer $l_i$ ($1 \le l_i \le 2 \cdot 10^5$) represents the length of the $i$-th sequence, and the following $l_i$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$ ($0 \le a_{i, j} \le 10^9$) represent the elements of the $i$-th sequence.
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $\sum l_i$ over all test cases does not exceed $2 \cdot 10^5$.
     46 
     47 Output
     48 
     49 For each test case, output a single integer — the value of $\sum\limits_{i = 0}^m f(i)$.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 6
     57 
     58 3 4
     59 
     60 2 0 2
     61 
     62 3 2 3 3
     63 
     64 4 7 0 1 5
     65 
     66 3 4
     67 
     68 5 0 2 0 4 11
     69 
     70 1 1
     71 
     72 5 1 3 0 3 3
     73 
     74 2 50
     75 
     76 2 1 2
     77 
     78 2 1 2
     79 
     80 1 1
     81 
     82 7 1 2 4 1 4 9 5
     83 
     84 4 114514
     85 
     86 2 2 2
     87 
     88 5 7 3 6 0 3
     89 
     90 3 0 1 1
     91 
     92 5 0 9 2 1 5
     93 
     94 5 1919810
     95 
     96 1 2
     97 
     98 2 324003 0
     99 
    100 3 1416324 2 1460728
    101 
    102 4 1312631 2 0 1415195
    103 
    104 5 1223554 192248 2 1492515 725556
    105 ```
    106 
    107 Output
    108 
    109 ```
    110 16
    111 20
    112 1281
    113 6
    114 6556785365
    115 1842836177961
    116 ```
    117 
    118 Note
    119 
    120 In the first test case, when $x$ is initially $2$, Turtle can choose $i = 3$ and set $x$ to $\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}) = \text{mex}(2, 7, 0, 1, 5) = 3$. It can be proved that Turtle can't make the value of $x$ greater than $3$, so $f(2) = 3$.
    121 
    122 It can be seen that $f(0) = 3$, $f(1) = 3$, $f(2) = 3$, $f(3) = 3$, and $f(4) = 4$. So $f(0) + f(1) + f(2) + f(3) + f(4) = 3 + 3 + 3 + 3 + 4 = 16$.
    123 
    124 In the second test case, when $x$ is initially $1$, Turtle can choose $i = 3$ and set $x$ to $\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}, a_{3, 5}) = \text{mex}(1, 1, 3, 0, 3, 3) = 2$, and choose $i = 3$ and set $x$ to $\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}, a_{3, 5}) = \text{mex}(2, 1, 3, 0, 3, 3) = 4$. It can be proved that Turtle can't make the value of $x$ greater than $4$, so $f(1) = 4$.
    125 
    126 It can be seen that $f(0) = 4$, $f(1) = 4$, $f(2) = 4$, $f(3) = 4$, and $f(4) = 4$. So $f(0) + f(1) + f(2) + f(3) + f(4) = 4 + 4 + 4 + 4 + 4 = 20$.
    127 
    128 In the fourth test case, it can be seen that $f(0) = 3$ and $f(1) = 3$. So $f(0) + f(1) = 3 + 3 = 6$.