Starfall Solution | Canada Day Contest 2021

Starfall Solution

A meteor shower is approaching the Monkey Empire. At the titith second, a meteor will fall at (xi,yi)(xi,yi) and destroy the planet. Luckily, the monkeys have a square tarp that they can use to catch the meteors. They can set up the tarp at any location initially at time 00, but once it has been set, the tarp can only be moved by up to KK units in

See Also : Canada Day Contest 2021

the ±x±x and ±y±y direction per second independently (You can move KK units in both directions at once). In addition, the tarp is aligned with the xx and yy axis and cannot be rotated. What is the minimum tarp side length required to catch all meteors?

Assume the meteors have insignificant size.

Input Specification

The first line contains an integer nn, the number of meteors, and KK, the tarp speed.

The next nn lines contain three integers each: titi, xixi, and yiyi, the time and location of the iith meteor strike. The input is given in order of nondecreasing time.

Output Specification

Output the minimum side length of the tarp.

Constraints

1≤n≤4000001≤n≤400000

0≤K≤4000000≤K≤400000

0≤ti,xi,yi≤1090≤ti,xi,yi≤109

Sample Input 1

2 0
1 0 0
2 0 3

Sample Output 1

3

Explanation For Sample 1

The tarp has a speed of 00, so it cannot move. It must be big enough to cover both (0,0)(0,0) and (0,3)(0,3) at the same time.
diagram

Sample Input 2

2 1
1 0 0
2 3 3

Sample Output 2

2

Explanation For Sample 2

At time 11, the bottom left corner of the tarp is at (0,0)(0,0). It moves 1 unit up and right by time 22. The top right corner now covers (3,3)(3,3).

Sample Input 3

3 1
1 100 100
3 100 105
103 0 5

Sample Output 3

3

Explanation For Sample 3

The tarp starts with the bottom left corner at (100,100)(100,100) to catch the second meteor, moves 22 units up to catch the third meteor, then moves 100100 units left to catch the first meteor.

Sample Input 4

3 1000
1 0 0
1 5 1
2 100 100

Sample Output 4

5

Sample Input 5

3 100
0 1 3
1 4 2
5 0 0

Sample Output 5

0

Hint

This is actually a 1 dimensional problem. We can consider each dimension separately, then take the maximum of the width and length as the solution.

Solution

You can use binary search for this problem but it’s not necessary. Let rr be the minimum current position of a the tarp’s right edge and ll be the maximum position of the tarp’s left edge, out of every path it could have taken to cover all the meteors so far. Initially, l=∞,r=−∞l=∞,r=−∞. Every second, ll increases by KK and rr decreases by KK, as the tarp could have travelled up to KK units to the left or right. When a meteor at xx is encountered, l=min(l,x),r=max(r,x)l=min(l,x),r=max(r,x) to ensure the tarp covers the meteor. Find the answer by taking the maximum of r−lr−l after every meteor encounter.

Complexity: O(n)O(n)

Leave a Comment

error: Content is protected !!
Please Click on 1 or 2 Ads to help us run this site.