Editorial for COCI '09 Contest 5 #6 Chuck


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First note that using row/column rotations, we can place arbitrary elements on given rows or columns. For example, let sequence S = \{p_1, p_2, \dots, p_R\} of R elements we want to place in the first column. For i^\text{th} element we:

  • If p_i is already in the first column, we place it out rotating the row by one.
  • We rotate the column containing p_i so that it is in the i^\text{th} row.
  • Rotate the row containing p_i so that it is placed into the first column.

Using this algorithm, we can place any chosen R elements in the first column and any chosen S elements in the first row. We can now negate all elements in the first row/column. If we repeat this procedure it follows that we can choose arbitrary a \cdot R + b \cdot S \le R \cdot S elements of the matrix and negate them.

The best solution is of course to negate all negative elements. Since this is not always possible, we need to choose such a and b that results in the smallest possible solution. Sorting the elements of the array and using dynamic programming easily yields the best a and b.

Note that for each element, we use at most three rotations, and two negations this ensures that the number of operations is smaller than 5 \cdot R \cdot S.

Coding this in \mathcal O((\max\{R, S\})^4) solves the problem.


Comments

There are no comments at the moment.