Editorial for COCI '11 Contest 3 #4 Robot
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 to
. Distance to any control point changed by
or
after this move. To be more precise, distance increased by
for every control point with x-coordinate no greater than
, and decreased by
for the rest of them. If we denote the number of points in the first group
, then the sum of these distances changed by
. We can do the same for the y-coordinate.
Next, we must figure out how to calculate 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
for any value
.
This solution has a complexity of . Better complexity can be achieved by precomputing all the
values using dynamic programming.
Comments