codeforces-scrape

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

2059C.md (3274B)


      1 Source: https://codeforces.com/problemset/problem/2059/C
      2 
      3 C. Customer Service
      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 Nikyr has started working as a queue manager at the company "Black Contour." He needs to choose the order of servicing customers. There are a total of $n$ queues, each initially containing $0$ people. In each of the next $n$ moments of time, there are two sequential events:
     22 
     23 1. New customers arrive in all queues. More formally, at the $j$-th moment of time, the number of people in the $i$-th queue increases by a positive integer $a_{i,j}$.
     24 2. Nikyr chooses exactly one of the $n$ queues to be served at that moment in time. The number of customers in this queue becomes $0$.
     25 
     26 Let the number of people in the $i$-th queue after all events be $x_i$. Nikyr wants MEX$^{\dagger}$ of the collection $x_1, x_2, \ldots, x_n$ to be as large as possible. Help him determine the maximum value he can achieve with an optimal order of servicing the queues.
     27 
     28 $^{\dagger}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $y$ which does not occur in the collection $c$.
     29 
     30 For example:
     31 
     32 * $\operatorname{MEX}([2,2,1])= 0$, since $0$ does not belong to the array.
     33 * $\operatorname{MEX}([3,1,0,1]) = 2$, since $0$ and $1$ belong to the array, but $2$ does not.
     34 * $\operatorname{MEX}([0,3,1,2]) = 4$, since $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not.
     35 
     36 Input
     37 
     38 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
     39 
     40 The first line of each test case contains a single integer $n$ ($1 \le n \le 300$) — the number of queues and moments of time.
     41 
     42 The $i$-th of the next $n$ lines contains $n$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($1 \le a_{i,j} \le 10^9$) — the number of new customers in the $i$-th queue at each moment of time.
     43 
     44 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, output a single integer — the maximum value of $\operatorname{MEX}([x_1, x_2, \ldots, x_n])$ that can be achieved.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 4
     56 
     57 2
     58 
     59 1 2
     60 
     61 2 1
     62 
     63 2
     64 
     65 10 10
     66 
     67 10 10
     68 
     69 3
     70 
     71 2 3 3
     72 
     73 4 4 1
     74 
     75 2 1 1
     76 
     77 4
     78 
     79 4 2 2 17
     80 
     81 1 9 3 1
     82 
     83 5 5 5 11
     84 
     85 1 2 1 1
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 2
     92 1
     93 3
     94 3
     95 ```
     96 
     97 Note
     98 
     99 In the first test case, the second queue can be served at time $1$, and the first queue at time $2$. There will be $x_1 = 0$ people left in the first queue and $x_2 = 1$ person left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 1]) = 2$.
    100 
    101 In the second test case, the first queue can be served both times. There will be $x_1 = 0$ people left in the first queue and $x_2 = 20$ people left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 20]) = 1$.
    102 
    103 In the third test case, the third queue can be served at time $1$, the second queue at time $2$, and the first queue at time $3$. There will be $x_1 = 0$ people left in the first queue, $x_2 = 1$ person left in the second queue, and $x_3 = 2$ people left in the third queue. Therefore, the answer is $\operatorname{MEX}([0, 1, 2]) = 3$.