All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Let's consider a square grid with N rows and N columns, both numbered 1 through N. Each cell contains one integer. Let ri denote the minimum value in the i-th row, and let Ci denote the maximum value in the i-th column. A grid is called nice if and only if the following condition holds true:
max(r1, r2, ..., rN) = min(C1, C2, ..., CN)
Chef has a square grid and can change some of its elements (numbers in the cells). Find the minimum possible number of elements Chef should change, so that the new grid is nice.
An element can be changed to any integer.
The first line of the input contains an integer N, denoting the size of the grid.
The following N lines describe the grid. The i-th of those lines contains N integers, denoting the numbers in the i-th row.
Print one integer, denoting the minimum number of changes required to make the grid nice.
- 1 ≤ N ≤ 1000
- Each number in the initial grid is between 1 and 106, inclusive.
Input1: 3 10 20 30 20 10 30 10 5 35 Output1: 1 Input2: 3 10 20 10 20 10 5 30 30 35 Output2: 0 Input3: 4 1 1 3 4 5 1 1 8 9 10 1 1 1 14 15 1 Output3: 2
Example #1. In the first example, initially we have r1 = 10, r2 = 10 and r3 = 5. For columns, we have C1 = 20, C2 = 20 and C3 = 35.
max(r1, r2, r3) = 10 and min(C1, C2, C3) = 20, and so the given grid isn't nice. Chef can change the second number in the first row from 20 to 10, to get the following nice grid:
10 10 30 20 10 30 10 5 35
The answer is 1 because we must change at least 1 number.
Example #2. The provided grid is already nice, so the answer is 0.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.