codeforces-scrape

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

2121C.md (2174B)


      1 Source: https://codeforces.com/problemset/problem/2121/C
      2 
      3 C. Those Who Are With Us
      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 a matrix of integers with $n$ rows and $m$ columns. The cell at the intersection of the $i$-th row and the $j$-th column contains the number $a_{ij}$.
     22 
     23 You can perform the following operation exactly once:
     24 
     25 * Choose two numbers $1 \leq r \leq n$ and $1 \leq c \leq m$.
     26 * For all cells $(i, j)$ in the matrix such that $i = r$ or $j = c$, decrease $a_{ij}$ by one.
     27 
     28 You need to find the minimal possible maximum value in the matrix $a$ after performing exactly one such operation.
     29 
     30 Input
     31 
     32 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.
     33 
     34 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 10^5$) — the number of rows and columns in the matrix.
     35 
     36 The next $n$ lines of each test case describe the matrix $a$. The $i$-th line contains $m$ integers $a_{i1}, a_{i2}, \ldots, a_{im}$ ($1 \leq a_{ij} \leq 100$) — the elements in the $i$-th row of the matrix.
     37 
     38 It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $2 \cdot 10^5$.
     39 
     40 Output
     41 
     42 For each test case, output the minimum maximum value in the matrix $a$ after performing exactly one operation.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 10
     50 
     51 1 1
     52 
     53 1
     54 
     55 1 2
     56 
     57 1 2
     58 
     59 2 1
     60 
     61 2
     62 
     63 1
     64 
     65 2 2
     66 
     67 4 2
     68 
     69 3 4
     70 
     71 3 4
     72 
     73 1 2 3 2
     74 
     75 3 2 1 3
     76 
     77 2 1 3 2
     78 
     79 4 3
     80 
     81 1 5 1
     82 
     83 3 1 3
     84 
     85 5 5 5
     86 
     87 3 5 1
     88 
     89 4 4
     90 
     91 1 3 3 2
     92 
     93 2 3 2 2
     94 
     95 1 2 2 1
     96 
     97 3 3 2 3
     98 
     99 2 2
    100 
    101 2 2
    102 
    103 1 2
    104 
    105 3 2
    106 
    107 1 2
    108 
    109 2 1
    110 
    111 1 2
    112 
    113 3 3
    114 
    115 2 1 1
    116 
    117 1 2 1
    118 
    119 1 1 2
    120 ```
    121 
    122 Output
    123 
    124 ```
    125 0
    126 1
    127 1
    128 3
    129 2
    130 4
    131 3
    132 1
    133 1
    134 2
    135 ```
    136 
    137 Note
    138 
    139 In the first three test cases, you can choose $r = 1$ and $c = 1$.
    140 
    141 In the fourth test case, you can choose $r = 1$ and $c = 2$.
    142 
    143  ![](https://espresso.codeforces.com/c17767a6920a311231f92f0369c10b9b6a34d491.png) 
    144 
    145 In the fifth test case, you can choose $r = 2$ and $c = 3$.
    146 
    147  ![](https://espresso.codeforces.com/45bddc965ec3fa397cb2b518c9236cd1e45f846e.png) 
    148 
    149 In the sixth test case, you can choose $r = 3$ and $c = 2$.