Network Cabling puzzle discussion

Puzzles
#85

Really bad examples… It’s look like manathan distance from sorted (in x) house.

waste of time, I event try to use a GA >_<

#86

Hello,

I’ve found a solution for this problem, all test cases pass.
But (!) the validation fails on this one :
Works on time when N = 100000 and L < 2^31.

So i tried to execute the code on my computer by using a local file. I took file of test number 7 and then 8.
Results are that more than 99% of time is used by the simple fact of reading the file. The actual computation takes about 2 or 3 ms. So i don’t know what to optimize…

Has somebody made this in java and passed this test ?
I’d like to see his code in that case.

Thank you

#87

Hello,

Here a probabilistic Monte-Carlo algorithm (I think there is no name for it) whick works without sorting the list for finding the median:

Let’s have S the set of inputs of cardinality n.

  1. R = set of samples. This set is built by randomly uniformly getting n^(3/4) elements from S (with putting back).
  2. Sort R
  3. Let d be the n^(3/4) - sqrt(n) smaller element of R and u the n^(3/4) + sqrt(n) bigger element of R
  4. C <— {s \in S | d <= s <= u}
  5. Let l_d be the number of elements strictly lesser than d
  6. Let l_r be the number of elements strictly bigger than u
  7. If l_d > n/2 or l_r > n/2 then FAILURE
  8. If #© >= 4*n^(3/4) then FAILURE else sort C
  9. return the (n/2 - l_d +1)-ith element of C sorted
#88

So my code verified all the tests cases, but when I tried to validate it, I had the 7th test wasn’t good.

The description of the 7th test is : Works in time when N = 100000 and L < 2^31
When I read this description, I thought that the problem in my code was that it was slow.
So I tried to minimize the time of processing (inserting + sorting), but without success.

Until I came to the forum and figured out that the parameter I’m using to set the main line wasn’t the right one.

I’m not gonna say that I’m lost a lot of time, but I spend a lot of it to figure out what was wrong.

So please, Could you mention in the validation tests, when it’s not succeeded, if the problem comes from the time

Thanks

3 Likes
#89

Hi,

tried to solve it today. I am failing a bit (if there is such a thing as failing a bit). Basicaly, there are 2 questions: 1- I am not satisfied with the way I calculate the position of the main cable. 2- I do not think they way I calculate the Y position of the main cable is right since I can not validate the 9th test.

Formulated as a question:

  1. Is there a nicer way to calculate the Y coordinate of the main cable? (I use C#)
    I want to calculate the Y coordinate as some refined average of the Y position of all the buildins. Something like the integer average of the Buildings Y position + the rest of the division multiplied by the decimal part of the floating average rounded up if positive and down if negative. This inclued a lot of typecasting and I wonder if there is a cleaner way. What I do is:
  • intResult = Integer division of (Sum of all Y position)/(Number of buildings).
  • floatRest = Integer division of (Sum of all Y position)%(Number of buildings) casted to float.
  • floatResult = Floating division of (Sum of all Y position casted to float)/(Number of buildings).
  • floatDecimalPart = floatResult - intResult casted to float
  • floatRestResult = floatRest * floatDecimalPart
  • intRestResult = floatRestResult rounded down IF positive or rounded up ELSE.
  • intFinalResult = intResult + intRestResult.
    I do not use a variable for each step, but this seem overly complicated with a lot of type cast. Are there any nicer way?
  1. How should I calculate the height of the main cable?
    I tried the average of all building Y position, the median, the average rounded, the average “complicated” (see above) but I can not pass all tests. At best (with the result above) I pass all but the last one. And I fail it from a lot (10% away from the optimal length of cable). What could go wrong?

Thanks

#90

This is how is find te Y of the main cable :
First Sort homes by y ascending
Then :

y = homes[Math.ceil(homes.length / 2) - 1].y;
2 Likes
#91

So it IS actually the median. I might have miscoded it, as it didn’t work at first.

I will rethink my home class, as I defined my IComparable to sort my home array by ascending X. But this shouldn’t be a major issue. Thanks a lot :slight_smile:

EDIT; it worked, thanks a lot!

#92

Hello,

I have a problem with test 7.
It pass in IDE but not when I submit.

I suppose a performance problem but I have no info.
I code in Java.

Thank you

#93

Hi.
When i tried to submit this puzzle didn’t passed Test 9: “Highly dispersed positions”. And i can not understand why. Where I am mistaken?
My algorythm c#:
[EDIT: NO FULL CODE]

#94

I am very confused right now as my code passes 100% upon submission but fails test case #6. I don’t know enough to diagnose what the problem is but I figured this may be of some interest to codngame and maybe to those working in python.

Got it, no full code even behind a link.

if anyone knows python well, I’d love to talk to you about my solution and why it works 100% when submitted but gives me an answer that is off by 4 for test 6.

1 Like
#95

Well… It is not allowed :stuck_out_tongue: . Sorry. Could you remove the link please?

Usualy validation tests are similar to IDE test. Test 6 has big numbers. I do not know how it works in pythin (I suppose it should not be a problem since it adapts automaticaly to datatype) but can your solution variable handle 64 bits coded integer?

#96

I don’t know but it’s producing an answer of 6066790157 but wants an answer of 6066790161 (a difference of 4) so I’m guessing its ability to handle 64 bits wouldn’t be at issue.

#97

Greetings to all again.
I have not solved the problem with test 9 Highly dispersed positions.
My algorithm: the entire cable is the distance between the most distant buildings of the X-coordinate + all of the branches at a certain height. How do I find this height: Calculate the distance of the branches for the maximum and minimum Y coordinates of buildings, as well as for the middle between these two coordinates (the median). Then assign the height of the median to the greatest distance, and compute new median, and so on.
Now the question is, what may be an error of my algorithm, why it is not pass only the test Highly dispersed positions?

#99

Well, I actually implemented by myself same solution as Magus proposed and passed all tests, but it’s clearly wrong because you can simply add 2 houses on same vertical lane and below all others and it’s stated that the main cable must pass between them, so main cable must be below all points in original array and that’s clearly not the case with this solution.

Note: the buildings with the same position x should not in any case share the same dedicated cable.

So actually tests aren’t covering this special case and the problem is much easier to solve without considering it.

^… o
| …o
| …o
| …o
| …o
±------------------------------------------------------
| …o
| …
| …o

#100

I don’t understand your graphic. With my solution the main cable will be here:

^ .............................o
| ........................o
| .....................o
| ..................o
| ++++++++++++++o+++++++++++++++
| ....
| ...o
| .... 
| ...o
#101

Well, it’s quite ambigous what that note meant at second glance. Two nodes with y below 0 share the same x coordinate and I understood “they should not share the same dedicated cable” as “main cable must be between them”. But after all on second thought as there’s no hint that there can be no solutuion at all it looks like it just meant “cables to nodes with same x coordinate shall be counted as two cables even if they share a segment”

As I looked on other solutions looks like it’s purely my misunderstanding and it’s all right.

1 Like
#102

I am getting a bus error when i try to make this puzzle in C. That is associated with hardware failure. Did anyone got this problem too?

#103

Hey, greetings fellow coders!
First of all, cool puzzle did make me think for quite a while. I have some questions though.
My first attempt was a bruteforce one, put the cable at all possible positions between highest Ypos and lowest Ypos, calculate cable length and compare. Easy and enough for the first few cases. Ofc it did timeout on the ones with big distances between max and min Y.

So I went for another approach which would cut my computing time in log_2 of the previous time.
I computed the cable for the max pos and the min pos, decided which was shorter and updated my maximum or minimum Ypos accordingly. Now i passed all IDE tests, and all but the last validator test. I cannot see why this approach would fail a test? It should in theory always find the right answer, so my only guess would be it being to slow? Would be helpful if one can see if the code just takes to long or the solution was wrong.

anyway cheers, keep up the good work!

#104

WOW! Works perfectly for me.

But, depending on which langage you choose, you must make sure that (homes.length / 2) return a double and not an floored int ! You might prefer the division by 2.0 to make sure that ex: 3 / 2 return 1.5 instead of 1 :slightly_smiling:

Thanks again Magus!

#105

I am a bit confused.
A rather simple python code passes all the tests yet doesn’t pass the validator number 7, I guess it times out ?

I simply do a dichotomy on the list of Y coordinates to keep the closest house to the mean ‘altitude’.

Nevertheless, it’s quite frustrating when the validator doesn’t pass and you simply can’t know why !