because I can place the main cable vertically
No, you can’t.
Quoting the statement:
A main cable will cross through the park from the West to the East (from the position x of the most westerly building to the position x of the most easterly building).
yes, thanks,you are right, I solved the more complicated case, and wondered why my solution was wrong … 
Hi everyone.
My algortihm passed all the test, excep 6, 8 and 9.
I think it’s not optimized.
I compute the distance of cable, depending on y of main cable.
And then I test this distance for all y possible to look for the min.
Can someone can give me a hint to make something more optimized ?
thanks
Yes, you can think of the best position for the east-to-west cable. Draw some examples on your notebook.
You’ll figure out that you don’t need to bruteforce y.
Yes.
This is the median right ?
So i have to sort my list of all y, find the median of this list and compute the distance of the cable for this median.
I did this and it passed all the test except 7 and 8.
(I did not managed to see the inputs for this testes by the way).
Is it because sorting my list is not optimized ?!
I usede listey.sort() (Im using python3)
That’s the right thing to do.
Do you have the wrong answer or do you timeout ?
I got timeout
Make sure you handle huge values, as the answers for the last cases are over 2^31
with N elements, if you sort, you need O(N*log(N)) time and then choose the middle element.
So you could run out of time because of complexity, becausd sorting makes a lot of unnecessary work.
But there exists a linear O(N) algorithm for finding the median of a set , which works nice !
Hello everyone, I need some help here.
The code I wrote works for all test cases except the test cases 6, 7, 9.
In my eyes the code seems correct, although this is not the case obviously, and I can’t find what is wrong with it.
Can I explain here what I did, or should I private message someone?
you can explain what you did here. It will be easier to give you hints
Okay then!
First I sorted the given coordinates based on X axis. From that list I get the median on Y axis. This is where the main cable will be as a horizontal line.
Then I use Manhattan distance to get the total cable needed from each house to connect to the main cable (Horizontal), and then again from each house to the next based on the main cable (Vertical).
This solution works for all test cases except 6, 7, 9 where I get a little bit more cable than what is actually needed (there is no timeout errors). But I can’t figure out why is that.
Why do you sort the houses along the X axis to get the median on Y axis?
Also, it seems weird to calculate the horizontal distance from one house to another since you can easily know the total horizontal distance, can’t you?
Based on the examples I thought it’d be better to sort the houses based on their X value, in order to be in line from west to east. Then I believe by getting the median on Y value on that sorted list you get the position of the main cable.
Then I just loop and get each distance which I add each time in order to get the total distance.
Can I show you my code?
I saw your code 
I think it would fail for this test case:
3
0 3
1 0
2 3
What should be the Y-median here?
In my solution it would be zero, but I think the correct one should be 3.
So the error should be on how I get the median, I think I see your point.
I’ try again!! 
Update: Got it working 100%, thanks for the valuable help!!
I have a problem with the validator 9 !! I don’t pass !
I presume it’s a median problem but I absolutly don’t understand why I works with all the other validator and not with the last ?
I’ve been go through this post but don’t really find an answer !
Thanks for your help
The 9nth validator tests the performance of your algorithm. It seems it’s not fast enough.
Thnaks for your answer!
I just see I didn’ explain correctly my problem…it’s not the validator when sbmitting who falis but the 9th test.
I have a big difference between the correct answer and mine.
If you know the solution to it, Can you please tellme that how did you solved it so easily… it would be a great pleasure … thankyou.