I worked really hard on figuring this out, tried all sorts of “clever” algorithms, put way too much time into it. I was overthinking the problem in a big way. When I took a step back and saw how simple it was, I erased all my code and completed the puzzle in 5 minutes.
Some hints for you:
This is one of those “When you see it…” situations.
If you have written more than 50 lines of code, erase everything and go back to the drawing board. I had written far more than that before I smacked myself hard and erased everything.
If you took highschool math, you have more than enough knowledge to pull this off. Go back to the basics. Some of the most basic stuff you can think of. Even before high school.
Not every language has a built-in function suitable for finding median.
Using a built-in sort function instead is okay as long as it is fast enough for the task at hand.
None of what you’ve said changes the facts of my previous comment. I.e.
Anyone explaining that “the solution is O(n.log n)” can do better.
Note that I didn’t say you couldn’t use sort to find the median - just that it wasn’t optimal.
You also don’t need a built-in function to find the median using an O(n) algorithm.
I have no idea why someone wouldn’t want to use a built-in function. You tell me.
You’re the one who’s saying people should try to use the slowest possible algorithm.
Personally, if a tool provides provides a useful built in function, I’d use it.
If the tool doesn’t provide something I need, I write my own function (or take a different approach).
And you’re still missing the fundamental point. I never said anyone’s O(n.log n) solutions wouldn’t “work”.
I was simply pointing out that claims that the data had to be sorted (resulting in a best case solution O(of n.log n)) are wrong and claims that the best solution is O(n.log n) are wrong. (Though I had originally attempted to avoid being so blunt about it.)
The claims are wrong because the problem is solvable without sorting; and a solution can be found in O(n) by anyone interested in digging a little deeper.
Really, the logic semantics behind my statements are quite trivial. I have no idea how I can explain it any more clearly to you.
I’d prefer it if this discussion doesn’t get derailed by tangential rhetoric.
I was merely pointing out something that might motivate some people to dig a little deeper into the functions their language provides and the algorithms that can determine what values go where without needing to fully sort a list.
This is after all a learning site.
I agree that those claims are wrong. But “slowest possible”, really? O(n log n) is best to second-best for most typical problems. Saying drivel like that just makes your point weaker
Hi.
It looks like Example 5 is wrong.
We have the positions (-3,-3), (2,2) and (-4,-4).
So if we place the main cable at y = -3,
then the dedicated cables will have lengths 0, 5 and 1.
And the main cable is 6, so in total we need 12 units of cable.
However, the expected solution is 18.
Wow, that’s the kind of bug (in my code) that should be so obvious, but since the first couple of examples passed the test, I didn’t think that my coordinates could be wrong!
I read the coordinates correctly:
for i in range(n):
x[i], y[i] = [int(j) for j in input().split()]
But back when I started this puzzle I for some reason thought you could do:
x = y = np.zeros(n)
as a short way of assigning several variables. But then they point to the same array. So when I change y, I change x too…
Thanks for your reply =)
Usort failed timeout on 99k+ elements. Used Quick Select, timed after submit. Ex.7 executed in 307.179ms and Ex8 in 139.552 . For reference, Ex. 5 ran in .075ms.
