SAPO 2018 stadium

Hello. In the internal solution to this problem, it is mentioned that we can solve in \mathcal{O(n \log n)} the “decision problem” if we binary search on the stadium length. I know that the binary search on the answer solution won’t get 100 points, but I am still interested in knowing how to determine in the aforementioned complexity whether a certain side length is “attainable”.

If you fix the width and add all trees that the stadium could potentially touch to a set, then you simply check whether there exists a “gap” between two consecutive trees in the set that’s at least as big as the width

1 Like

Basically you do the same thing as the solution, but you don’t change the width you’re testing as you sweep through the trees

1 Like

Thanks for the answer!