codeforces-scrape

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

1162B.md (2686B)


      1 Source: https://codeforces.com/problemset/problem/1162/B
      2 
      3 B. Double Matrix
      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 $n \times m$ matrices containing integers. A sequence of integers is strictly increasing if each next number is greater than the previous one. A row is strictly increasing if all numbers from left to right are strictly increasing. A column is strictly increasing if all numbers from top to bottom are strictly increasing. A matrix is increasing if all rows are strictly increasing and all columns are strictly increasing.
     22 
     23 For example, the matrix $\begin{bmatrix} 9&10&11\\ 11&12&14\\ \end{bmatrix}$ is increasing because each individual row and column is strictly increasing. On the other hand, the matrix $\begin{bmatrix} 1&1\\ 2&3\\ \end{bmatrix}$ is not increasing because the first row is not strictly increasing.
     24 
     25 Let a position in the $i$-th row (from top) and $j$-th column (from left) in a matrix be denoted as $(i, j)$.
     26 
     27 In one operation, you can choose any two numbers $i$ and $j$ and swap the number located in $(i, j)$ in the first matrix with the number in $(i, j)$ in the second matrix. In other words, you can swap two numbers in different matrices if they are located in the corresponding positions.
     28 
     29 You would like to make both matrices increasing by performing some number of operations (possibly none). Determine if it is possible to do this. If it is, print "Possible", otherwise, print "Impossible".
     30 
     31 Input
     32 
     33 The first line contains two integers $n$ and $m$ ($1 \leq n,m \leq 50$) — the dimensions of each matrix.
     34 
     35 Each of the next $n$ lines contains $m$ integers $a_{i1}, a_{i2}, \ldots, a_{im}$ ($1 \leq a_{ij} \leq 10^9$) — the number located in position $(i, j)$ in the first matrix.
     36 
     37 Each of the next $n$ lines contains $m$ integers $b_{i1}, b_{i2}, \ldots, b_{im}$ ($1 \leq b_{ij} \leq 10^9$) — the number located in position $(i, j)$ in the second matrix.
     38 
     39 Output
     40 
     41 Print a string "Impossible" or "Possible".
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 2 2
     49 2 10
     50 11 5
     51 9 4
     52 3 12
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 Possible
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 2 3
     65 2 4 5
     66 4 5 6
     67 3 6 7
     68 8 10 11
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 Possible
     75 ```
     76 
     77 Input
     78 
     79 ```
     80 3 2
     81 1 3
     82 2 4
     83 5 10
     84 3 1
     85 3 6
     86 4 8
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 Impossible
     93 ```
     94 
     95 Note
     96 
     97 The first example, we can do an operation on the top left and bottom right cells of the matrices. The resulting matrices will be $\begin{bmatrix} 9&10\\ 11&12\\ \end{bmatrix}$ and $\begin{bmatrix} 2&4\\ 3&5\\ \end{bmatrix}$.
     98 
     99 In the second example, we don't need to do any operations.
    100 
    101 In the third example, no matter what we swap, we can't fix the first row to be strictly increasing in both matrices.