Network Cabling puzzle discussion

Puzzles
#63

Tests

Simple case : (0 0)(2 2)(4 4) -> 8 (100 pts)
Unordonate positions : (2 3)(1 1)(4 4) -> 6 (100 pts)
Pair N : (1 2)(0 0)(2 2)(5 3) -> 8 (100 pts)
If N = 1 then L = 0 (100 pts)
Negative positions (-5 -3)(-9 2)(9 -4) -> 24 (100 pts)
Works when 2^32 < L < 2^63 (100 pts)
Works in time when N = 100000 and L < 2^31 (200 pts)
Works in time when N = 99999 (every x and y are distincts) (200 pts)

Highly dispersed positions (200 pts)

Readability Analysis

Method IL Size: 282. Maximum Size: 165 (Long methods are usually hard to understand and maintain. This method can cause problems because it contains more code than the maximum allowed.)

My code fails on “Highly dispersed positions” test
Where is problem? What is “Maximum Size: 165” parameter?
My code have about 120 rows…

#64

In “Highly dispersed positions” test I need in.txt and out.txt files at least

#67

@Revernus When I first saw the drawings for this test, I found it looked like fitting a 0-degree polynomial for which the answer is the mean of the Ys when using least-square method (there is only 1 parameter).
Well after trying I found out like you guys that the proper answer is indeed the median, not the mean. My guess is that we shouldn’t think to minimize the squares of the difference but rather the absolute values.

I think this is a brilliant example that associating something simple with something complex as I did makes you think hours for futilities. The best was to think like @BlitzProg … So I had to come here and comment this game: brilliant.

@alec_m_melnikoff it looks like hard coding for 120 rows, it might be the reason why… (see comments above)

#68

I’ve tried another approach. Evaluate mean Y as double and then find the nearest existing Y. It works in IDE for all tests but fails on validation on “Works in time when N = 100000 and L < 2^31”.
Can’t see why.

#69

Hey there,

I’m solving all test cases except 6 and 7.

Any hint?

Thanks in advance :smiley:

#70

Read (again) the previous messages here.

#71

Thanks @nicolas_patrois for the hint, will do :blush:

#72

Hello,

My algorithm has almost passed all tests but not this one : 2^32 < L < 2^63 (100 pts)

Do you have any ideas ?

Thanks,

#73

@sebastien_hemono Long > Int ?

#74

I got the same issue as Sebastien.
I fail for : 2^32 < L < 2^63
But I don’t know why, I use long long to be sure… this shouldn’t have any problem, but it’s not ok…
I pass any other test.
Thanks if someone has idea.

#75

You’ve probably gotten past this by now; but I was recently here…and I solved it by looking at values that weren’t explicitly specified.

#76

Still stuck on “Works in time when N = 100000 and L < 2^31 (200 pts)”. Can anyone shed some light on what this means?

#77

maybe it does not work in time?

you need O(n log n) sorting algorithm, like qucksort - any O(n^2) algorithm like bubble sort will fail

1 Like
#78

Yup just implemented the new algo described above in this thread. Works fine.

#79

Hi, my algorithm also fail for : 2^32 < L < 2^63.

I can’t understand why as I’m using Ruby and I shouldn’t pay attention to Bignum or Fixnum

So I tried with inputs like this :

2
0 4611686018427387904
0 -4611686018427387904

and it results with 9223372036854775808

which is between 232 and 263.

What’s the trick ? Running machine is 32bits ? What am I missing :smiley: ?

#80

Here is a tip who helped me get a 100% score at this challenge.
When the range is absolutely huge, consider using the standard deviation function.

1 Like
#81

Hello,
As I’ve read posts above, some of you were stuck at certain test cases.
Personally, I’ve been stuck using Groovy at : "Works in time when N = 100000 and L < 2^31 (200 pts)"

But, after translating my program to Java, it passes all test cases ! :blush:
It might be that Groovy is relatively slow comparing to Java… :worried:

#82

Looks like there is an error in the task validation. I used iterative algorithm to find the optimal solution, so it is hard to make a mistake there. So let’s take a look on the data of the test case #7. I found houses with the same X value and reduced the search range between Y values of the houses. In the next lines we have 2 houses with X values and the search interval from min Y to max Y, let’s name variables as (xi, yi) (xj, yj) y0 y1:

(-12.0, 37.0) (-12.0,  -8.0)  -8.0 37.0
( 44.0,  3.0) ( 44.0, -58.0)  -8.0  3.0
(-19.0, 18.0) (-19.0,   1.0)   1.0  3.0

Thus, when y0 < min(yi,yj) < y1 then we update y0=min(yi,yj);
when y0 < max(yi,yj) < y1 we update y1=max(yi,yj).

So in the example above the search interval converges to [1.0, 3.0]. In the whole test, final search range is [1.0,1.0], but optimal solution is at 0, which means there are at least two houses that are connected to the main cable with a single cable.

My algorithm (without search range narrowing) passes all the IDE’s test cases and all validation tests except for the last one.

#83

Hint : Try to find median.

1 Like
#84

Yes, read this thread’s messages #50 and the following ones.