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