I am also struggling on testcase 7. I get a result of 3972, while the outcome should be 3142894.
What I do is:
I saw another post that suggested similar logic and also warned for testcase 7, but unfortunately I could not find that post back. Does anyone have suggestions to help me further? Thank you
As several other have mentioned the solution is a lot simpler than you would imagine. DataType is important because some calculations go over 4 billion.
Hints
The only calculation involving division or multiplication is when dividing total number of houses(n) by 2
so let, k = n/2
now k is a float
the best way is to round it to lower.
so use integer(n)
for median(m) = (arrayof_y_coords_sort_ascedning)[ int(n/2) ]
This really requries matrix mathematics to solve, but no libraries are provided for e.g. C++, where you need GSL, or other solvers.
The statistically expected value is around medians, but is not going to be right for all cases.
No it really does not require matrix mathematics to be solved.
I solved it 6 years ago with simple median calculation.
Hi,
I tried to complete this puzzle but I struggle on some points. Iām working in C.
I passed the tests 1 to 5 but the 6, 7, 8 and 9 are not working.
I used the quicksort method to sort the buildings, then I searched for the median value in order to have the best Y coordinate for the main cable. Then I searched for the minimum and maximum X coordinate in order to have the length of the main cable, and finally I add the lengths of the cables that links the buildings to the main cable.
I didnāt find the good results for the test 6,7 and 9, and the test 8 takes too much time so my solution isnāt optmized.
Is my method wrong? Can someone can give me some advice?
Thanks by advance for your response,
With regards to timing out: The X part is correct but you need to think again about the Y portion. I would suggest drawing it on a piece of map ā how/why do you find the median? how are you adding the lengths? Can any of this be done faster?
Getting almost the right answer but not quite as the function seems to want me to round values at a basically random point for no reason, canāt really make any sense of it.
Hi everyone,
After numerous attempts, I finally got 100%.
In order to solve this puzzle, the best HINT there is to know is calculating the MEDIAN only on the ordinates (Y coordinates).
From that step itās possible to determine the cable length, cumulating all the connected nodes.
Note 1:
The median allows a fast way to find the smallest cumulated length of cable set.
The chart represents the calculated length based on a reference axis (here only Y).
Here, the median gives directly the reference axis corresponding to the lowest cable length.
Note 2:
If you calculate both cable lengths based on either a long and a wide common trunk and then you compare them, you could find smaller results than the expected ones.
Here, we could say that comparing the two cable sets the second one (with the wide common trunk) is the best solution because it implies a shortest length. Well, this puzzle handles only the first solution.
I hope my post will help those in need and perhaps an improvement from the contributors.
Thatās not a hint
Thatās what is specified in 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).
For each building, a dedicated cable will connect from the building to the main cable by a minimal path (North or South), as shown in the following example:Hello.
I finally beat this awful beast. Very, very, very, very hard. Not anywhere near mediumā¦
Of course, if the description were clarified, then yes, it would be medium / almost easy.
It says that two houses that share an X value cannot share the same cable. And, based on the deceptive illustration of a simple example, it looks like that means that the main cable cannot lie on the same side of two houses with the same X value. So, for every duplicate X, I was limiting the position of the main cable to lie between the Y values for that X. Very, very unclear description.
I can see a potential ambiguity here, you can indeed undestand āplace the main cable in a way that 2 houses with the same x never lie on the same sideā, but itās more likely that it just means āif 2 houses have the same x, give a separate cable per house, whatever side they areā.
Anyway when there are two possible options like this, you should always try the easiest one first, and here the second option is pretty straightforward (and I agree itās more easy than medium) so you should have tried it before.
But I can try to edit if you really think itās that ambiguous.
Edit: looks like itās an official puzzle that canāt be edited.
Good point. Iāve always tended to start with the hardest, because Iāve had many occasions where I had to recode several times because something that solved the easiest test failed on the harder ones, but youāre right, I would have finished this far faster if I hadnāt assumed the line had to be between the houses.
Let me propose the test case below. What result will be given by any of the correct implementations for the following co-ordinates?
8
1 1
3 2
3 -2
4 4
7 1
8 -3
7 -2
7 -3
@ pardouin thanks, I 've spend so much time struggling with this too.
Rule and schemes make it a bit unclear.
Youāre assuming that there canāt be several houses at the same location, nor several cables at the same location. Example 7 has 100,000 houses in a 128x128 square (=16,384). For any coordinates, chances are that ou have around 8 houses at the same location, each one with its own separate cableā¦
Imagine that you place your horizontal cable far above all the houses, with all houses below it. If you go down 1 unit, your total length will decrease by 1 per house, or n in total. Then, if you go down and past the top house, when you go down one unit, that house will increase your total length by 1, cancelling the effect of one of the houses below it. So you will get the minimum total length when you have as many houses above as below the cable.
Note that for an odd number of houses, your cable must be right on the middle house, but for an even number, any value of Y between the 2 middle houses will do (the total length will be the same).
what should be the approach if u were to take in account the amount of cable u need in the X axis. As that can have multiple solutions, we take the closest one to 0.
can some body explain me his solution ? iām trying some simple stuff but it doesnāt work at 100%