Network Cabling puzzle discussion

Puzzles
#1

Feel free to send your feedback or ask some help here!

4 Likes
#2

I don’t understand the exemple given with three houses. Where is the dedicated cable of the middle house in these exemples ? Can the main cable go through as much houses as needed without dedicated cable ?

4 Likes
#3

Yes, if the main cable go through a house, the dedicated cable isn’t needed (or you can consider it has a length of 0).

#4

I see. Thank you ! I feel that I’m going to have a hard time with this one XD

#5

Solved without even knowing how to actually solve this.

4 Likes
#6

Actually pretty easy, but I was being dumb : I was convinced that the main cable could go up and down and that the only restriction was that it couldn’t go left, making it another problem entirely

1 Like
#7

Gah - on the surface this problem is quite easy, but I’m not entirely sure that it’s possible to pass the last two tests in python - timing out before all possibilities have been enumerated… Tempting to implement a time-out of my own where the best guess is given, but that seems like cheating…

#8

Hi Alistair, I didn’t try using Python but I get the perfect score in Java. What’s the time complexity of your solution (it should be nlogn)?

2 Likes
#9

Hmm looks like I need to rethink my solution, i think mine has a worst case of n² - I thought it was all too simple…

#10

Hint: this problem is actually easier than you think as there’s always a single possibility (well… sometimes two but you can ignore the second one anyway) :wink:

2 Likes
#11

hey guys

i solved all the test cases, all of them work. however, when i submit, i only get 81% - case number 8 fails.

why does it work in the test cases, and when i want to submit, it does not?

#12

For me all tests before submitting are fine, then all tests except 7. Would be really nice to see, why it failed.

I would think, that test case 8 takes longer, so i doubt that i have a timeout here …

#13

Hi,
The test cases used on IDE aren’t the same than the tests used on submission, to avoid solution hard coding.

#14

I think there is a bug in the test cases proposed for final validation as well as in the solutions that can be found on the internet for this problem. I will try to explain why I think so:

  1. The solution that people posted on the internet (almost wrongly) assume that the main cable should necessarily be located in the [AvgY - 1, AvgY + 1] segment. This solution passes all internal and external test cases. At this point, all would be good except for the case with a higher standard deviation from the average, for which there doesn’t seem to be a test case or it is expecting wrong values (see 2)
  2. Let’s take a simple example with 3 houses located at (0, 0), (1, 6) and (2, 6). If we follow the mentioned solution then the Y of the main cable is in the [3, 5] segment, ie it is 5 and the length of the cable is (2-0) + (5-0) + (6-5) + (6-5) = 9, which is greater if Y of the main cable would be 6, thus the length would be 2 + 6 + 0 + 0 = 8

My conclusion is that both the posted solutions by members and the solution from codingame are identical and wrong. I have a different solution for this problem which I think is correct but it fails test 7 of the external test cases.

Please correct me if I’m wrong

#15

Example 8:
Fail
Found: “2500049997”
Expected: “2500049998”

6 Likes
#16

The solution you mentioned is wrong, and doesn’t correspond to the soluton made by codingame and expected.
I have tried to implement it, and it fails for one test. Can you provide me a link via private message to the page giving this solution?

Thanks in advance

#17

I finally submitted a correct solution that passed all the test cases. This means that the algorithm used at codingame for this problem was correct from the very beginning (sorry for doubting).

However the test cases still need to be reviewed as they also validate wrong algorithms posted on the internet as valid solutions. This was confirmed by one of the admins.

#18

I added a test that make fails solutions like the one referenced by int33h.
All the successes and the completion percent already earned stay the same.

To access at the new test, you need first to submit your solution, then return on the puzzle (by clicking on “try again” or from puzzle page. Backspace bug referenced on an other topic is still not fixed, and make you loose your code).

1 Like
#19

My code passes all of the test cases except for #7. I downloaded the .txt file for that test case and performed some experiments. Here is what I found:

(1) The range of x values is [-63, 63].
(2) The range of y values is [-63, 63].
(3) Every house but one has a house at y = -63 and y = 63.

So, with the following conditions, I calculate the worst case:

(1) at every x location there is a house at y = 63
(2) at every x location there is a house at y = -63
(3) lay horizontal cable at y = 0 intercept

Therefore,

(1) the cable length in the x direction = 63 - ( -63 ) = 126
(2) the cable length in the y direction = 126 houses * ( 63 - ( -63 ) ) = 15876
(3) the total cable length would be 126 + 15876 = 16002.

The problem is that Test case #7 appears to want me to enter 3142894 for the answer.

Does anyone have any ideas of what the discrepancy is?

4 Likes
#20

If two houses are aligned vertically, they can’t still share the same cable.
So even if the max and min for each x are 63 and -63, you still have to take in account the intermediary houses.

1 Like