LCC/Moose '19 Contest 4 S3 - TPS

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

The Shinkansen (Japanese bullet train) is testing out a new Train Positioning System (TPS) to have better position and velocity data for their trains. Authorities placed N beacons along a straight part of the track which each send out a continuous signal with their beacon ID and a current timestamp. The N beacons are synchronized to a central atomic clock. Each second after t = 0, the train picks up two of these signals and uses the difference between the current time and the received timestamp to calculate the train’s position.

For example, suppose the train picks up a signal from beacons 1 and 2 with time differences equal to T_1 and T_2, where the time difference is the current time (an integer number of seconds) and the timestamp. Then the train is at a distance of D_1 = c\times T_1 from the first beacon and D_2 = c\times T_2 from the second, where c = 299792458 is the speed of light. It is possible to determine the position of the train using the positions of the beacons and these two distances.

You have access to the signal data received for each t = 1, 2, 3, ..., K seconds by a single train. Unfortunately, the order of the data has been scrambled and the data is missing the IDs of the beacons, i.e. you only have the timestamps T_i, without knowing at which second the timestamp arrived. If you know the positions of all the beacons and assume that the train moved at a constant integer velocity, can you determine the initial position (at t = 1) and the velocity of the train?

Input Specification

The input begins with two integers N, K (3 \le N, K \le 1000), the number of beacons and the number of seconds for which you have data. The second line contains N integers A_i (-10^6 \le A_i \le 10^6), the locations of the beacons. The next 2K lines each a real number T_i (0 \le T_i \le K), one of the timestamps received by the train, accurate to at least fifteen decimal places.

For at least 30% of points, N \le 20.

Output Specification

Output two integers: the initial position of the train (at t = 1) and the velocity of the train. It is guaranteed that a unique solution exists.

Sample Input 1

3 3
-5 0 100

Sample Output 1

3 7

Explanation of Sample Input

The timestamps correspond to distances of 3, 8, 10, 22, 83, and 90.

At t = 1, the train must have been at position 3, which is at a distance of 8 from the first beacon and a distance of 3 from the second beacon.

At t = 2, the train must have been at position 10, which is at a distance of 10 from the second beacon and a distance of 90 from the third beacon.

At t = 3, the train must have been at position 17, which is at a distance of 22 from the first beacon and a distance of 83 from the third beacon.


There are no comments at the moment.