Editorial for COCI '11 Contest 3 #4 Robot


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.

We will find a way to quickly keep track of the current sum after each move of the robot.

Assume that robot moved to the right (east) from (a, b) to (a+1, b). Distance to any control point changed by 1 or -1 after this move. To be more precise, distance increased by 1 for every control point with x-coordinate no greater than a, and decreased by 1 for the rest of them. If we denote the number of points in the first group f(a), then the sum of these distances changed by f(a)-(N-f(a)). We can do the same for the y-coordinate.

Next, we must figure out how to calculate f(a) efficiently. One of the ways to do this is to keep the control points in two arrays, one sorted by x-coordinate and the other sorted by y-coordinate. Now we can easily binary search f(a) for any value a.

This solution has a complexity of \mathcal O(N \log N + M \log N). Better complexity can be achieved by precomputing all the f(a) values using dynamic programming.


Comments

There are no comments at the moment.