codeforces-scrape

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

1637B.md (2958B)


      1 Source: https://codeforces.com/problemset/problem/1637/B
      2 
      3 B. MEX and Array
      4 
      5 time limit per test
      6 
      7 1 second
      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 Let there be an array $b_1, b_2, \ldots, b_k$. Let there be a partition of this array into segments $[l_1; r_1], [l_2; r_2], \ldots, [l_c; r_c]$, where $l_1 = 1$, $r_c = k$, and for any $2 \leq i \leq c$ holds that $r_{i-1} + 1 = l_i$. In other words, each element of the array belongs to exactly one segment.
     22 
     23 Let's define the cost of a partition as $$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$ where $\operatorname{mex}$ of a set of numbers $S$ is the smallest non-negative integer that does not occur in the set $S$. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let's define the value of an array $b_1, b_2, \ldots, b_k$ as the maximum possible cost over all partitions of this array.
     24 
     25 You are given an array $a$ of size $n$. Find the sum of values of all its subsegments.
     26 
     27 An array $x$ is a subsegment of an array $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
     28 
     29 Input
     30 
     31 The input contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 30$) — the number of test cases.
     32 
     33 The first line for each test case contains one integer $n$ ($1 \leq n \leq 100$) — the length of the array.
     34 
     35 The second line contains a sequence of integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array elements.
     36 
     37 It is guaranteed that the sum of the values $n$ over all test cases does not exceed $100$.
     38 
     39 Output
     40 
     41 For each test case print a single integer — the answer to the problem.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 2
     51 
     52 1 2
     53 
     54 3
     55 
     56 2 0 1
     57 
     58 4
     59 
     60 2 0 5 1
     61 
     62 5
     63 
     64 0 1 1 0 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 4
     71 14
     72 26
     73 48
     74 ```
     75 
     76 Note
     77 
     78 In the second test case:
     79 
     80 * The best partition for the subsegment $[2, 0, 1]$: $[2], [0, 1]$. The cost of this partition equals to $2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0, 1\}) = 2 + 0 + 2 = 4$.
     81 * The best partition for the subsegment $[2, 0]$: $[2], [0]$. The cost of this partition equals to $2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0\}) = 2 + 0 + 1 = 3$
     82 * The best partition for the subsegment $[2]$: $[2]$. The cost of this partition equals to $1 + \operatorname{mex}(\{2\}) = 1 + 0 = 1$.
     83 * The best partition for the subsegment $[0, 1]$: $[0, 1]$. The cost of this partition equals to $1 + \operatorname{mex}(\{0, 1\}) = 1 + 2 = 3$.
     84 * The best partition for the subsegment $[0]$: $[0]$. The cost of this partition equals to $1 + \operatorname{mex}(\{0\}) = 1 + 1 = 2$.
     85 * The best partition for the subsegment $[1]$: $[1]$. The cost of this partition equals to $1 + \operatorname{mex}(\{1\}) = 1 + 0 = 1$.
     86 
     87 The sum of values over all subsegments equals to $4 + 3 + 1 + 3 + 2 + 1 = 14$.