Network Cabling puzzle discussion

I used Javascript to try solve this one and unfortunately I get everything correct with exception of text number 9 were it’s expects 21 and i return 22. Can’t tell why … can anyone give me some feedback please !?

I am getting the “Works in time when N = 100000 and L < 2^31” validation failing after submitting. I am curious if anyone has any insights for me into the reason for this failure. Is the failure generally associated with a Timeout?

I am passing everything else, with less than 80 lines of code and no nested loops. Trying to figure out if I need to target a different method for this one.

Did the same thing.

1 Like

Ok i finally solved it, this one was quite hard in my opinion. Not the code itself, but the way to demonstrate it mathematically with absolute certainty. When viewing other people answers, i found many used the median technique. Ok that looks fine, but i still don’t know how to prove that using the median gives the best solution. And even that, i’m not sure because all i can say is that the median solution fullfills 9 unit tests. On the other hand, with my solution i proved that the code i provided will always give the best answer to the problem. So in a way i prefer to stick to my code, even if it uses a std::sort

I like your attitude. My solution used median and I feel like you did about it… no idea if it’s actually correct but it got full credit so I’m moving to the next one :slight_smile:

“Note : Les bâtiments ayant la même position x ne doivent en aucun cas partager le même câble dédié.”
(The buildings with the same x, don’t share the same cable)

I think there is no particular test for this rule.
I looked at some of the solutions of Codingamers and they completely forgot it (or ignored ?)
A part of my code is used to respect this rule, but with or without it, I pass all the tests.

Since i was unsure of the shenanigans used i calculated with mean, median and mode and selected the smallest.

Hi everybody,

I got stuck with this puzzle.
I can’t get understand how could be the Example 5 test case result 18?
Houses:
X -5, Y -3
X -9, Y 2
X 3, Y -4
The test said, 18 the cable length.
I tried to get this result in a piece of paper on a coordinate system, but can’t get the 18.
I calculate is 21.
I think I miss something, but don’t find what is that.

Please help me,
Thank you in advance!

what if the cable is on y=-3?

x=xmax-xmin
X=3-(-9)=12
you take the middle Y
Y=-3-(-3)+2-(-3)±3-(-4)
y= 0+5+1

total =x+y=12+6

Ohh, I think the cable is always starting from the origo.
Now I see the mistake I made.
Thanks you!

It’s strange my solution won’t pass to the example 6, 7, 8, 9 test cases.
I already using longs to represent the x and y points.
Also I using double to compute the manhattan distance.

I compute the manhattan distance between the nodes and get the median.
This solution works fine for the first 5 test cases.
Any idea what is the problem?

This problem might at first seem difficult. But the simplest algorithm there is to solve this is:

  1. Get the median of the houses relative in the Y-axis.
  2. Get the leftmost and rightmost houses. That will serve as the start and end points of your main distribution cable which lies on your median axis found on step 1.
  3. Count the number of pipes it takes for the houses to connect to the main distribution pipeline by subtracting their y-coordinate from the median.
  4. Add the total pipes from step 3 and the length of your main distribution pipe.

There you have it. :slight_smile:

**NOTE: ** Ensure you are using the right data structure for testcases 7 and 8. In my case, I used an arraylist for storing coordinates. And don’t forget to ensure the capacity of your integers. :wink:

It is probably meaningless now, but i just got the same behaviour using ruby and initializing my arrays with x=y=[]… Ruby has just created a single array and two pointers on it… Spent quite one hour before finding the bug…

I cannot complete validators 7 and 9, no matter what I tried
I complete all examples successfully.

The 9th validator is not very descriptive, but as far as I understood from discussion - it’s about number of code lines, there should be 80, my code is 67 lines with normal formatting. Otherwise, I do not understand what validator 9 is about.

The 7th is about time, I complete Example 7 in ~375ms. I even switched to BufferedReader + Stream to improve the time. I use Java array.sort (and tried parallelSort) which should be quite fast and using BufferedReader cut more time than sort even took. I see some people mentioning getting median without sorting, but on the other hand I see many people completed the test with sorting just okay.
Yet, validators 7 and 9 always fail, I don’t understand the reason at all

EDIT: Turns out I added one correction variable that was not really needed and was 0 for all examples, but I guess it was not zero in validators and skewed the result

I’ve been beating my head on this all day, trying to figure out why this code wasn’t running the way I thought it should. Then I got the gag. Oh, Codingame. It’s going to be like that? And here I thought we were going to be friends.

Gloves off, Codingame. That wasn’t nice. :slight_smile:

omfg Medians is literally a tag on this puzzle and I kept trying to use the mean, I’m a dummy

I somehow manage to output negative values when my result starts at zero and is only ever increased thereafter.
I’m somewhat proud of this feat.
Edit: It only happened with the larger numbers so I figured out that it was because of the way ones and zeros behave in confinement.

there is something wrong in the data :
on test 6, (with 8 points and large numbers) , I get :
found : 5 343 706 357
expected :6 066 790 161
My solution is shorter than the answer … because I can place the main cable vertically !

and for validation cases too …