Editorial for Canada Day Contest 2021 - Starfall

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: Aaeria

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 binary search the answer but it's not necessary. Let $r$ ~r~ be the minimum current position of the tarp's right edge and $l$ ~l~ 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=\infty,r=-\infty$ ~l=\infty,r=-\infty~. Every second, $l$ ~l~ increases by $K$ ~K~ and $r$ ~r~ decreases by $K$ ~K~, as the tarp could have travelled up to $K$ ~K~ units to the left or right. When a meteor at $x$ ~x~ 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-l$ ~r-l~ after every meteor encounter.

Time complexity: $\mathcal O(n)$ ~\mathcal O(n)~

Comments

There are no comments at the moment.