codeforces-scrape

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

1706B.md (3069B)


      1 Source: https://codeforces.com/problemset/problem/1706/B
      2 
      3 B. Making Towers
      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 have a sequence of $n$ colored blocks. The color of the $i$-th block is $c_i$, an integer between $1$ and $n$.
     22 
     23 You will place the blocks down in sequence on an infinite coordinate grid in the following way.
     24 
     25 1. Initially, you place block $1$ at $(0, 0)$.
     26 2. For $2 \le i \le n$, if the $(i - 1)$-th block is placed at position $(x, y)$, then the $i$-th block can be placed at one of positions $(x + 1, y)$, $(x - 1, y)$, $(x, y + 1)$ (but not at position $(x, y - 1)$), as long no previous block was placed at that position.
     27 
     28 A tower is formed by $s$ blocks such that they are placed at positions $(x, y), (x, y + 1), \ldots, (x, y + s - 1)$ for some position $(x, y)$ and integer $s$. The size of the tower is $s$, the number of blocks in it. A tower of color $r$ is a tower such that all blocks in it have the color $r$.
     29 
     30 For each color $r$ from $1$ to $n$, solve the following problem independently:
     31 
     32 * Find the maximum size of a tower of color $r$ that you can form by placing down the blocks according to the rules.
     33 
     34 Input
     35 
     36 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).
     39 
     40 The second line of each test case contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$).
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output $n$ integers. The $r$-th of them should be the maximum size of an tower of color $r$ you can form by following the given rules. If you cannot form any tower of color $r$, the $r$-th integer should be $0$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 7
     56 
     57 1 2 3 1 2 3 1
     58 
     59 6
     60 
     61 4 2 2 2 4 4
     62 
     63 1
     64 
     65 1
     66 
     67 5
     68 
     69 5 4 5 3 5
     70 
     71 6
     72 
     73 3 3 3 1 3 3
     74 
     75 8
     76 
     77 1 2 3 4 4 3 2 1
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 3 2 2 0 0 0 0 
     84 0 3 0 2 0 0 
     85 1 
     86 0 0 1 1 1 
     87 1 0 4 0 0 0 
     88 2 2 2 2 0 0 0 0
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, one of the possible ways to form a tower of color $1$ and size $3$ is:
     94 
     95 * place block $1$ at position $(0, 0)$;
     96 * place block $2$ to the right of block $1$, at position $(1, 0)$;
     97 * place block $3$ above block $2$, at position $(1, 1)$;
     98 * place block $4$ to the left of block $3$, at position $(0, 1)$;
     99 * place block $5$ to the left of block $4$, at position $(-1, 1)$;
    100 * place block $6$ above block $5$, at position $(-1, 2)$;
    101 * place block $7$ to the right of block $6$, at position $(0, 2)$.
    102 
    103  ![](https://espresso.codeforces.com/d0bb8379199b1a125f664684ccdae691d44b945a.png) 
    104 
    105 The blocks at positions $(0, 0)$, $(0, 1)$, and $(0, 2)$ all have color $1$, forming an tower of size $3$.
    106 
    107 In the second test case, note that the following placement is not valid, since you are not allowed to place block $6$ under block $5$:
    108 
    109  ![](https://espresso.codeforces.com/d8c42e73c18a92ff52cf319c2dada9b3f6eeec90.png) 
    110 
    111 It can be shown that it is impossible to form a tower of color $4$ and size $3$.