Editorial for COCI '09 Contest 5 #6 Chuck
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 of elements we want to place in the first column. For element we:
- If is already in the first column, we place it out rotating the row by one.
- We rotate the column containing so that it is in the row.
- Rotate the row containing so that it is placed into the first column.
Using this algorithm, we can place any chosen elements in the first column and any chosen 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 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 and that results in the smallest possible solution. Sorting the elements of the array and using dynamic programming easily yields the best and .
Note that for each element, we use at most three rotations, and two negations this ensures that the number of operations is smaller than .
Coding this in solves the problem.
Comments