codeforces-scrape

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

2055C.md (3486B)


      1 Source: https://codeforces.com/problemset/problem/2055/C
      2 
      3 C. The Trail
      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 |  |
     22 | --- |
     23 | There are no mountains in Florida, and Florida Man cannot comprehend their existence. As such, he really needs your help with this one. |
     24 
     25 In the wilderness lies a region of mountainous terrain represented as a rectangular grid with $n$ rows and $m$ columns. Each cell in the grid is identified by its position $(i, j)$, where $i$ is the row index and $j$ is the column index. The altitude of cell $(i, j)$ is denoted by $a_{i,j}$.
     26 
     27 However, this region has been tampered with. A path consisting of $n + m - 1$ cells, starting from the top-left corner $(1, 1)$ and ending at the bottom-right corner $(n, m)$, has been cleared. For every cell $(i, j)$ along this path, the altitude $a_{i,j}$ has been set to $0$. The path moves strictly via downward ($\mathtt{D}$) or rightward ($\mathtt{R}$) steps.
     28 
     29 To restore the terrain to its original state, it is known that the region possessed a magical property before it was tampered with: all rows and all columns shared the same sum of altitudes. More formally, there exists an integer $x$ such that $\sum_{j=1}^m a_{i, j} = x$ for all $1\le i\le n$, and $\sum_{i=1}^n a_{i, j} = x$ for all $1\le j\le m$.
     30 
     31 Your task is to assign new altitudes to the cells on the path such that the above magical property is restored. It can be proven that a solution always exists. If there are multiple solutions that satisfy the property, any one of them may be provided.
     32 
     33 Input
     34 
     35 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.
     36 
     37 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 1000$) — the number of rows and columns in the grid.
     38 
     39 The second line of each test case contains a string $s$ of length $n+m-2$ ($s_i = \mathtt{D}$ or $s_i = \mathtt{R}$) — the steps the path makes from $(1, 1)$ to $(n, m)$. The character $\mathtt{D}$ represents a downward step, and $\mathtt{R}$ represents a rightward step.
     40 
     41 The $i$-th of the next $n$ lines each contain $m$ integers $a_{i,1}, a_{i, 2}, \ldots, a_{i,m}$ ($-10^6 \leq a_{i,j} \leq 10^6$) — the altitude of each cell in the grid. It is guaranteed that if a cell $(i, j)$ lies on the path, then $a_{i,j} = 0$.
     42 
     43 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.
     44 
     45 Output
     46 
     47 For each test case, output $n$ lines of $m$ integers representing the restored grid of altitudes $b_{i, j}$. The altitudes must satisfy $-10^{15} \leq b_{i,j} \leq 10^{15}$, and additionally $a_{i,j} = b_{i,j}$ if $(i, j)$ is not on the path. If multiple solutions exist, output any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 3 3
     57 
     58 DRRD
     59 
     60 0 2 3
     61 
     62 0 0 0
     63 
     64 3 1 0
     65 
     66 4 5
     67 
     68 DRRRRDD
     69 
     70 0 1 0 2 3
     71 
     72 0 0 0 0 0
     73 
     74 -1 0 -3 -3 0
     75 
     76 0 0 0 -1 0
     77 
     78 2 3
     79 
     80 RRD
     81 
     82 0 0 0
     83 
     84 0 1 0
     85 
     86 5 5
     87 
     88 DDDDRRRR
     89 
     90 0 25 2 9 11
     91 
     92 0 6 13 20 22
     93 
     94 0 17 24 1 8
     95 
     96 0 3 10 12 19
     97 
     98 0 0 0 0 0
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 1 2 3
    105 2 3 1
    106 3 1 2
    107 -6 1 0 2 3
    108 7 -1 3 2 -11
    109 -1 0 -3 -3 7
    110 0 0 0 -1 1
    111 0 -1 1
    112 0 1 -1
    113 18 25 2 9 11
    114 4 6 13 20 22
    115 15 17 24 1 8
    116 21 3 10 12 19
    117 7 14 16 23 5
    118 ```
    119 
    120 Note
    121 
    122 In the first test case, the grid has been filled such that every row and column contains the numbers $1, 2, 3$ in some order, resulting in a common sum of $6$.
    123 
    124 In the second test case, the grid has been filled such that all rows and columns sum to $0$.