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!