Editorial for TLE '16 Contest 7 P2 - Judging


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.

Author: ZQFMGB12

This problem can be tough to implement if not thought of carefully.

A relatively simple implementation involves keeping track of the current time, the distance traveled, the previous point visited, and a queue of events left to process.

Initially, the previous point visited is (0,0).

As we process events, we try to clear events from the queue. When we get a new event, we look at the first event in the queue, if one exists. We compute the time it will be after the event has finished processing, which is equal to \max(currentTime,eventTime) + dist(previousPoint,location[eventTeam]). If this time is less than or equal to the new event's starting time, we update the current time, the distance traveled, and the previous point visited. We pop the queue and repeat until the computed time is greater than the new event's starting time.

Now suppose that the new event is from a team that is not team 1. We simply push this event into the queue.

Otherwise, it is possible that the new event can interrupt the first event in the queue. Notice that all events already popped from the queue cannot be affected. If the queue of events is empty, we simply push the new event into the queue. Otherwise, we need to simulate an interruption by team 1. We can do this by computing the time difference between team 1's call and the maximum of the current tracked time and the interrupted event's start time. Mr. C will walk from the previous point to the interrupted team for this amount of time (and therefore, distance). To find the exact point where Mr. C changes direction, we can perform linear interpolation using this distance. After getting the new distance from the previous point to the point where Mr. C changes direction to team 1's location, we update the current time, the distance traveled, and we set the previous point visited to team 1's location. We do not change the queue.

After all of the events have been inputted, we simply pop the queue in the exact same manner as above until it is empty.

Time Complexity: \mathcal{O}(T)


Comments

There are no comments at the moment.