Network Cabling puzzle discussion

I don’t get the test “Works in time when N = 100000 and L < 2^31” but I get the next one…

Can we have some more details?
Works in time = how many seconds?

The next one isn’t used to make your program fail if it’s slow. N is very small for last test, it’s only used to increase the chance that if the program pass all tests, the program is valid.
Timelimit is varying with programming language, which one are you using?

100% score with less than 10 lines of Clojure.

As NewboO noticed, this is a pretty easy problem once you figure out the trick.

Encrypted hint: nfejufssbofbo

I use Python3


I’m struggle with the last test, number 9. (All the other passed)
I’m able to pass it and i don’t have a clue where i missed something.
Does someone have an hint for help?

Test 9 has the particularity of dealing with very large numbers. Can your number type hold them ? Or maybe, is your algorithm going through all possible heights of the main cable ? If so, odds are that it is too slow

1 Like

I use double (in c#). Maybe it’s that, i forgot to check it.
I don’t think it’s the speed because it’s really fast (i mean as fast as the other tests).

i’ll retry tomorow, and do it manually step by step whith the calc. I’m pretty sure it’s something easy and i can’t see through.

i’ll let you in touch

You should avoid floats (and so doubles) to hold integers because you’ll lose precision at some point with very large numbers. :wink:

All righ,

So i changed to type long and still have the same problem.
It’s not a conversion problem, as I try the example 9 owith Calc, and I found the same result as my program.
I don’t know from where the result to this example come from.

So I guess it’s an algorithm problem. But i can’t find why it’s working on the other and not on this particular example.

I don’t really want to spoil for other user, so if you want i could send you a private message with the algo I used.

Thanks for that tip, so i’ll withdraw my post to be sure it wont’ stay too long.

=> spoiler removed after cup_of_tea answer. (wasn't a spoiler anyway as it was wrong :) )

Expectected result : 2178614523.
So my result on this example is really completely different, i don’t know where the problem is.

So i someone could have an hint ot some intermediary steps, i’ll be gratefull.

That’s because we wanted to avoid this kind of algorithm, who is based on a wrong heuristic.
I can’t really give you big hints about the answer, I can just tell you that the true solution doesn’t exploit average parameter at all.

1 Like

Ok, thanks for the hint.
That means i have to undestand why it’s doesn’t work and find an other way.

PS : I’ll edit my previous post to not spoiled or mislead other people.

i decrypted your message but i’m nowhere close to understanding what it means :slight_smile:

1 Like

Well done :slight_smile: Now, take a left substring of the message, then a right substring of it and concatenate them :wink:

lol…i eventually figured what you meant. thanks!

Thought of the solution instantly, “surely it’s too simple”, went for average + variation method, got screwed by evil developpers on test 9. Amazed that a couple of lines solved it.

Mean Y for cable Y works, but I don’t fully understand why.

Hi, is it possible to know the reason why a validation test failed (wrong result, time’s up…) ?
I did pass all the tests and really don’t understand why the last validation test is KO, and this kind of information could be useful…

Anyone able to give any hints for Test 9, I can’t see why I’m failing on that test.

That is very strange. I succeed in all tests. But for that I have adopted 2 different strategies depending on the number of houses.

  • For small number (<99999), I test all y positions to find the shortest cable length. It is a good algorithm but very costly.
  • For big numbers, I compute the mean y (sum of y / N) and compute the cable length.

Intuitively, I thought that the second approach based on mean was the right one. But this is not the case when there are few houses. It seems that thsi approach does not enable to find solutions where the cable crosses several houses.