(CH) Bear and Sorted Rows
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Limak has a grid that consists of N rows and N columns. He randomly wrote all numbers 1 through N2 in the cells of the grid, one number in each cell. You can assume that each of (N2)! ways was equally likely.
Limak asks you to rearrange the numbers in the grid, so that each row will be sorted either increasingly or decreasingly.
Let (r, c) denote the cell at the intersection of the r-th row and the c-th column. If a number x was in (r1, c1) in the initial grid and it is in (r2, c2) in the new grid, the cost of moving x is (r1 - r2)2 + (c1 - c2)2. Your score for one test is the sum of costs of moving all numbers, divided by N3 for clarity. The final score is the sum of scores in all tests. The goal is to minimize that score.
There are 20 tests. If your program works incorrectly (e.g. it exceeds the time limit or rows aren't sorted) on any of 20 tests, you will get a suitable verdict (e.g. TLE or WA). Otherwise, you will get AC and your score will be decided by only 20% of tests (first 4 tests). The final score will be revealed after the contest.
The first line of the input contains an integer N denoting the size of the grid.
Next N lines describe the grid. The i-th of those lines contains N integers t i,1, t i,2, ..., t i,N.
Output N lines, describing the new grid in the same format as in the input (do not print the value N though).
The printed grid should contain all values 1 through N2. Each row should be sorted either increasingly or decreasingly.
- N = 300
- 1 ≤ t i,j ≤ N2
- Values t i,j are distinct.
- The initial grid was generated by randomly shuffling all N2 values.
Input: 4 2 8 12 14 5 13 1 10 16 7 6 4 3 15 11 9 Output: 2 8 12 14 1 5 7 10 16 13 6 4 3 9 11 15
In the provided output, each row is indeed sorted — the third row is sorted decreasingly, while other rows are sorted increasingly. Let's compute the score:
- A number 5 moved from (2,1) to (2,2) with the cost 12 + 02 = 1.
- A number 13 moved from (2,2) to (3,2) with the cost 12 + 02 = 1.
- A number 1 moved from (2,3) to (2,1) with the cost 22 + 02 = 4.
- A number 7 moved from (3,2) to (2,3) with the cost 12 + 12 = 2.
- A number 15 moved from (4,2) to (4,4) with the cost 22 + 02 = 4.
- A number 9 moved from (4,4) to (4,2) with the cost 22 + 02 = 4.
The total cost is 1 + 1 + 4 + 2 + 4 + 4 = 16. Divided by N3 it gives the score 16 / 64 = 0.25.
Note that this test has N = 4 only for reader's convenience. The actual tests, on which your solution will be scored, will have N = 300.
|Tags||challenge, dynamic-programming, errichto, march17, optimization|
|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, CLOJ, FS|
Fetching successful submissions