codeforces-scrape

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

1870C.md (2462B)


      1 Source: https://codeforces.com/problemset/problem/1870/C
      2 
      3 C. Colorful Table
      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 You are given two integers $n$ and $k$. You are also given an array of integers $a_1, a_2, \ldots, a_n$ of size $n$. It is known that for all $1 \leq i \leq n$, $1 \leq a_i \leq k$.
     22 
     23 Define a two-dimensional array $b$ of size $n \times n$ as follows: $b_{i, j} = \min(a_i, a_j)$. Represent array $b$ as a square, where the upper left cell is $b_{1, 1}$, rows are numbered from top to bottom from $1$ to $n$, and columns are numbered from left to right from $1$ to $n$. Let the color of a cell be the number written in it (for a cell with coordinates $(i, j)$, this is $b_{i, j}$).
     24 
     25 For each color from $1$ to $k$, find the smallest rectangle in the array $b$ containing all cells of this color. Output the sum of width and height of this rectangle.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows the description of the test cases.
     30 
     31 The first line of each test case contains two integers $n$ and $k$ ($1 \leq n, k \leq 10^5$) — the size of array $a$ and the number of colors.
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq k$) — the array $a$.
     34 
     35 It is guaranteed that the sum of the values of $n$ and $k$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output $k$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $1$ to $k$.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 
     48 2 1
     49 
     50 1 1
     51 
     52 2 2
     53 
     54 1 2
     55 
     56 3 5
     57 
     58 3 2 4
     59 
     60 4 2
     61 
     62 1 2 1 2
     63 
     64 5 3
     65 
     66 1 2 3 2 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 4 
     73 4 2 
     74 0 6 6 2 0 
     75 8 6 
     76 10 6 2
     77 ```
     78 
     79 Note
     80 
     81 In the first test case, the entire array $b$ consists of color $1$, so the smallest rectangle for color $1$ has a size of $2 \times 2$, and the sum of its sides is $4$.
     82 
     83 In the second test case, the array $b$ looks like this:
     84 
     85 |  |  |
     86 | --- | --- |
     87 | 1 | 1 |
     88 | 1 | 2 |
     89 
     90 One of the corner cells has color $2$, and the other three cells have color $1$. Therefore, the smallest rectangle for color $1$ has a size of $2 \times 2$, and for color $2$ it is $1 \times 1$.
     91 
     92 In the last test case, the array $b$ looks like this:
     93 
     94 |  |  |  |  |  |
     95 | --- | --- | --- | --- | --- |
     96 | 1 | 1 | 1 | 1 | 1 |
     97 | 1 | 2 | 2 | 2 | 1 |
     98 | 1 | 2 | 3 | 2 | 1 |
     99 | 1 | 2 | 2 | 2 | 1 |
    100 | 1 | 1 | 1 | 1 | 1 |