Sending Messages

Question

N animals are sitting on the X axis and want to send messages to each other.One animal can send a message to another one if the distance between them is less or equal to K.P pairs of animals are given,check if they send messages between them or not.

Given Coordinates of N animals,value of K and P.

Ex.

N=5 K=3 P=3

0 3 8 5 12

1 2

1 3

2 5

Output

Yes

Yes

No

Explanation

For pair (1, 2) frog 1 can directly send message to the frog 2 as the distance between them is 3 - 0 = 3 <= K .

For pair (1, 3) frog 1 can send a message to frog 2, frog 2 can send it to frog 4 and it can send it to frog 3.

For pair (2, 5) frogs can't send a message under current constraints.

As N,P<=10^5, 0(n^2)solution gives TLE... any better approach to remove TLE.

Answer 1

• Sort the coordinates, tracking their original order.
• Construct spanning sequences -- sequences of neighboring sorted coordinates pairwise differing by $\leq$ K. Number the disjoint spanning sequences as you go. Since the new array of coordinates is sorted, start at the left and add new coordinates to the spanning sequence as long as it is $\leq$ K units from the last member. Then the gap is too big, start the next spanning sequence.
• Make a map from original order to spanning sequence number.
• Lookups are from original order to spanning sequence number. If the two original order numbers are in the same spanning sequence, they can communicate.

Lookups are $O(1)$.

The sort is $O(n \log n)$. Extracting the spanning sequences is $O(n)$. Making the map is $O(n)$.

This should be sufficiently fast compared to $O(n^2)$.