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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 be the minimum current position of the tarp's right edge and
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,
. Every second,
increases by
and
decreases by
, as the tarp could have travelled up to
units to the left or right. When a meteor at
is encountered,
to ensure the tarp covers the meteor. Find the answer by taking the maximum of
after every meteor encounter.
Time complexity:
Comments