Editorial for COCI '06 Contest 3 #4 Tenkici


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.

Suppose that we lax the constraints a bit so that more than one tank may occupy a single square. With that assumption in place, any tank may take any route to his final destination (it doesn't have to look out for other tanks).

Now notice that we can consider rows and columns separately, distributing all tanks to separate rows first, then to separate columns. We distribute the tanks into rows (and later columns) greedily – sort the tank by rows, send the first tank to the first row, the next to the second etc. It's not hard to prove that such an arrangement is optimal.

Reintroducing the constraint that tanks may not occupy the same square and using the same strategy, we only need to make sure that the tanks are moved so that no two tanks run into each other. We can achieve that by moving all tanks that need to be moved up in top-down order, all tanks that need to be moved down in bottom-up order etc.


Comments

There are no comments at the moment.