PROBLEM LINK:
Author: Kamil Dębowski
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Challenge
PREREQUISITES:
Optimization skills, dynamic programming
PROBLEM:
For a given grid with N rows and N columns, randomly filled with all distinct numbers from 1 to N^2, the goal is to rearrange the numbers in the grid in such a way that each row is sorted either increasingly or decreasingly. Moving a number X which was in the initial grid in cell (r_1, c_1) into the cell (r_2, c_2) in the final grid costs (r_1-r_2)^2 + (c_1-c_2)^2. The score is the sum of costs of moving all the numbers to their final position in the resulting grid divided by N^3. The task is to minimize the score.
EXPLANATION:
First of all, we can make an important observation based on the scoring function. Notice that moving any number X from its initial position p_1 to its final position p_2 yields a cost proportional to a square of Euclidean distance between these positions. Thus, the intuition is that we should come up with solutions producing correct answers and not move numbers far from their initial positions.
Like with any optimization problem, many different ideas may be promising and result in decent scores. Here, we are going to list some possible approaches. We assume that both rows and columns are numbered from 0 to N-1.
Method 1
Perhaps the easiest solution taking advantage of the above intuition is to solve the problem independently for every row, which means to sort each row. Notice that there are exactly two possibilities to sort each row: either increasingly or decreasingly, so we can choose the one which yields a lower cost.
Method 2
In the first method, we never move numbers across the rows. In the second method we are going to do this, but only for two adjacent rows. The intuition is that moving a number one row up or one row down still doesn’t cost much, and we are going to move some numbers between adjacent rows in order to get both rows almost-sorted and then perform the sort operations for each row independently. More specifically, let’s group all rows into N/2 pairs in such a way that rows with numbers 2 \cdot i and 2 \cdot i + 1 are paired, so rows 1 and 2 are paired as well as rows 3 and 4, and so on. Then, for each such pair of rows r_1 and r_2, we get the first N/2 numbers from both rows, sort them and put the smallest N/2 of them into row r_1 while the others into row r_2. Next, we get the last N/2 numbers from both rows, sort them and put the largest N/2 of them into row r_1 while the others into row r_2. After these operations, there is a decent probability that row r_1 is “almost sorted” in ascending order, while row r_2 is “almost sorted” in descending order. Here, “almost sorted” means that the number of inversions in a row is quite small. Then the only thing left to do is to sort both these rows: row r_1 in ascending order and row r_2 in descending order.
Method 3
The idea used in Method 2 can be extended further. We are going to improve the placement of numbers achieved by the second Method, so first, we do exactly what in that method. Then, we group rows in pairs as follows: rows 4 \cdot i and 4 \cdot i + 2 are paired as well as rows 4 \cdot i+1 and 4 \cdot i+3, which means that the closest rows with the same ordering, either ascending or descending are paired. Then, for each pair of rows r_1 and r_2, we compute the minimum cost of placing in these rows the numbers assigned to them by the Method 2. This can be done for a single pair of rows in O(N^2) time using dynamic programming: we compute dp_{i,j} as the smallest cost of assigning the smallest i+j from all 2 \cdot N numbers initially assigned to rows r_1 and r_2 across these rows, in such a way that i numbers are assigned to first i columns of r_1 and j numbers are assigned to first j columns of r_2.
Method 4
The idea used in Method 3 can be extended further. We can try to improve the already achieved solution by exchanging the numbers between rows paired by different rules, for example, we can pair row 1 with row 2 with row 3 now, or pair rows with distance 4 instead of 2 between them. This requires some experiments and tweaks. What we can do is to perform such improvements as long as they run under defined time limit.
As always we encourage you to take a look at solutions, which get the highest scores during the contest. All methods described above are implemented in Setter’s solution linked below
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.