Editorial for DMOPC '15 Contest 2 P6 - Manhattan Magnets


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.

by k_53P

For each piece of metal, find the distance to the closest magnet. In order to pick this piece of metal up, the new magnet must be placed within a certain zone where every square’s Manhattan distance is closer than the Manhattan distance to the closest magnet.

If you tilt the coordinate plane 45 degrees, this zone looks like a square. If you then draw a checkerboard on the coordinate plane, and look only at the white tiles, it is a square. If you look only at the black tiles, it is also a square.

The intended solution is to do a 2-D line sweep after separating the coordinate plane into two planes, black and white. Out of both planes, the tile which is in the most “zones” is the tile which will pick up the most metal.

Time Complexity: \mathcal{O}(NM+4000^2)


Comments

There are no comments at the moment.