codeforces-scrape

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

2234C.md (3071B)


      1 Source: https://codeforces.com/problemset/problem/2234/C
      2 
      3 C. Vessels, Heights and Two Versions (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 This is the easy version of the problem. The difference between the versions is that in this version, constraints on $n$ and on the number of test cases are smaller. You can hack only if you solved all versions of this problem.
     22 
     23 There are $n$ communicating vessels of infinite height arranged in a circle. The base area of each vessel is $1$ cm$^2$, and between the $i$-th vessel and the $(i \bmod n) + 1$-th vessel there is a connection of negligible volume at height $h_i$ cm. For each vessel $i$, find the maximum total volume of water in cm$^3$ that can be placed in these vessels under the condition that the $i$-th vessel remains empty.
     24 
     25 Formally, you are given an array $h_1, h_2, \ldots, h_n$. A cyclic array of non-negative integers $w_1, w_2, \ldots, w_n$ is called good if the following holds:
     26 
     27 * For every $i$ from $1$ to $n$, if $\max(w_i, w_{i \bmod n + 1}) \gt h_i$, then $w_i = w_{i \bmod n + 1}$. In other words, if the maximum of two neighboring elements of the array $w$ exceeds the corresponding element of the array $h$, then these two neighboring elements of the array $w$ must be equal.
     28 
     29 For each $i$ from $1$ to $n$, output the maximum possible sum $w_1 + w_2 + \ldots + w_n$ among all good arrays $w_1, w_2, \ldots, w_n$, under the condition that $w_i = 0$.
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     34 
     35 The first line of each test case contains one integer $n$ ($3 \le n \le 3000$) — the number of vessels.
     36 
     37 The second line of each test case contains $n$ integers $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$) — the heights of the partitions between the vessels.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $3000$.
     40 
     41 Output
     42 
     43 For each test case, output $n$ integers — the $l$-th integer means the maximum total volume of water in cm$^3$ in the vessels under the condition that the $l$-th vessel remains empty.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 4
     53 
     54 1 2 3 4
     55 
     56 5
     57 
     58 5 3 1 5 2
     59 
     60 6
     61 
     62 3 4 2 6 1 5
     63 
     64 7
     65 
     66 1 2 1 4 2 3 5
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 6 6 7 9
     73 
     74 17 16 14 14 17
     75 
     76 21 21 20 20 21 21
     77 
     78 17 17 17 17 21 21 22
     79 ```
     80 
     81 Note
     82 
     83 Consider the first test case.
     84 
     85 * To keep vessel $1$ empty, one good array is $w = [0, 1, 2, 3]$, with a total of $6$ cm$^3$ of water.
     86 * To keep vessel $2$ empty, one good array is $w = [1, 0, 2, 3]$, with a total of $6$ cm$^3$ of water.
     87 * To keep vessel $3$ empty, one good array is $w = [2, 2, 0, 3]$, with a total of $7$ cm$^3$ of water.
     88 * To keep vessel $4$ empty, one good array is $w = [3, 3, 3, 0]$, with a total of $9$ cm$^3$ of water.
     89 
     90 For example, the array $w = [2, 2, 0, 4]$ is not good, because $\max(w_3, w_4) \gt h_3$, and therefore $w_3 = w_4$ must hold.
     91 
     92 It can be shown that each of the arrays above has the maximum possible sum among all suitable options.