Send your feedback or ask for help here!
I am wondering if a solution better than Θ(n²) exists for this…
(Although not needed here, the dumb brute-force algo passes even in a slow language, as n is not too big in the tests.)
Yes you can do a first iteration to identify the potential endpoints.
They form a decreasing subsequence.
Then you iterate over every possible startpoint and find its optimal corresponding endpoint with bisection.
It results in a O(n log n) algorithm.
Worst case would be an increasing then decreasing sequence like this:
1, 2, 3, … top - 1, top, top -1, …, 3, 2, 1.
Could you say something more about your bisection method. I’ve been giving it a try to no avail.
Not really a spoiler but just in case.
For instance, for the big test I have as candidates (in the format (index, height)):
starts [(0, 316), (6, 337), (7, 469), (13, 490), (43, 493)]
ends [(99, 255), (93, 453), (69, 479), (43, 493)]
solution ((7, 469), (93, 453))
Now I found the solution by trying every combination, I don’t see how to binary search it, if that’s what you meant.
This should work:
for each start s: binary search the bigger index i that meets the following: ends[i] >= s for each end e: binary search the smallest index i that meets the following: starts[i] >= e
Edit : didn’t see that your ends list was reversed so you want to reverse it first.
Took me longer than I’m willing to admit but it was quite fun. Thanks for the hints.
I shared it in case anyone wants to check it. I was testing a bit the performance and apparently it can pass this (worst case):
n = 1000000 arr = [i for i in range(1, n//2+1)] + [n//2-i for i in range(n//2)]
import numpy as np n = 1000000 arr = [np.random.randint(2, n) for _ in range(n)]
Edit: I didn’t need to reverse it at the end.
I published solution in C++ with time O(n). And algorithm is even simpler:
Start with leftId=0, rightId=n-1 and remember corresponding heights while (leftId < rightId) calculate volume and check if is greater if left height is smaller than right height from leftId go right and find next bigger height else from rightId go left and find next bigger height
Very nice indeed. I learned quite a bit with this puzzle. Thanks to everyone .
I understood the description and the validators seem solid.