Finally got this one down. As stated above, deceptively simple. My one tip to others that are having trouble with Test 9 and passing the others is to follow cup_of_tea’s advice:
I was using the average until I read this. Then I rethought my process.
If you are having trouble, remember that least sum of squares and least sum of abs value are different.
Is the decoded message mediterranean?
But what does that mean?
I had troubles making the test “Works in time when N = 100000 and L < 2^31” pass with PHP. Rewrote the exact same code in C and test passed. Would be curious to know if there is a solution to get it in PHP with another approach. Anyone made it ?
Whatever the language, the complexity is the same as the sorting function you use. So yes, it’s possible in PHP as the default sorting function is largely fast enough for this puzzle.
I did it in PHP, if your solution has the good “approach” it should work fine even in PHP 
intesresting, nobody mentions median of the distribution of Y-value of houses - how people manage solve this without knowing this?
Actually some people including me hinted several times for it (so a lot solved this puzzle this way). It’s better giving only hints than the plain solution.
I simply came up with this logic
Put a cable in a given Y0 place.
=> if you move that cable Y up (and not going past any house)
-You’ll save (Y times the amount of houses above it) worth of cable, but:
-You’ll lose (Y times the amount of houses below it) worth of cable
So the optimal Y place is where there’s the same amount of houses above and below.
The median will works, but it’s not always the only best Y. In fact, it is, when there’s an odd number of house. But when working with an even amount of houses, picking a value anywhere between the two middle houses (inclusive) will always lead to the correct distance being computed. In fact, it’s better to not pick the median in that case and stick with one of the two best houses, so you’ll avoid decimal calculations 
Example: you have houses with coordinates -3, -1, 1, 3. The correct Y is anywhere between -1 and 1.
sum of distances with -1: 2 + 0 + 2 + 4 = 8
sum of distances with 0 : 3 + 1 + 1 + 3 = 8
sum of distances with 1 : 4 + 2 + 0 + 2 = 8
9 Likes
Yup, I solved it in Python but I used the right mathematical concept.
In fact, there were some wrong solutions using median and “variations” like “mean+1”,“mean-1”.
A lot of solutions like this passed all previous tests, but we added some tests to avoid this kind of solution to pass all of them.
Users having already submitted a wrong solution who passed previous tests are still rewarded, only the next submissions are affectated.
1 Like
I used the median, not the mean.
1 Like
Why median and not mean, exactly? As far as I could think, the mean would be the point in the Y axis that the sum of the absolute value of all the distances to it (i.e.: sum of all abs(y[i] - mean)), would be the least. If I used the median to determine this point, the sum of the absolute values of all the distances would be greater.
By the way, I could score 100% using Python, but I feel like my algorithm was unnecessary complex.
Because the min of such absolute values is reached at the median. It’s a mathematical theorem.
2 Likes
Could you provide me more information, like the name of the theorem? I would like to learn more about it.
It’s a small theorem that has no name. I read it recently in a French math teachers’ revue (le bulletin vert de l’APMEP, #510, p. 398 to 404).
1 Like
It’s a pity I can’t read French. But the main principle of this theorem is that given a sequence of ordered numbers, the median of this sequence is the point that has the least abs distances sum, is that it?
Yes, and the numbers don’t need to be ordered.
Thanks for your help, Nicolas!
Hi all!
I know that using median gives right solution but I’ve tried another algorithm and all tests pass in IDE. At validation I have a failed test “Works in time when N = 100000 and L < 2^31”.
Can anybody help with this? I can’t even determine if algorithm is wrong or too slow. I can share code or describe the logic. Using C#.
1 Like