Network Cabling – CodinGame solution in C
The horizontal cable must run from the smallest to the largest x, so its length is fixed at xMax - xMin; the only choice is its height. The sum of vertical drops |y_i - Y| is minimised when Y is a median of the building y-coordinates, so sort the y values, take ys[N/2], and add every |y_i - median| to xMax - xMin using 64-bit integers.
The problem
A business park is described by the integer coordinates of N buildings. You must connect all of them with one straight horizontal main cable plus, for each building, a vertical cable going straight from the building down or up to the main cable.
Print the minimum total length of cable. There can be up to 100,000 buildings, coordinates go from -2^30 to 2^30, and the total exceeds the 32-bit range, so the answer has to be computed with 64-bit integers.
Approach, step by step
- Separate the two dimensionsThe main cable has to reach the leftmost and rightmost buildings, and a longer cable never helps, so the horizontal part is always xMax - xMin. The y-position of the cable only affects the vertical parts, so the problem becomes one-dimensional.
- Minimise the sum of distancesWe need the height Y minimising the sum of |y_i - Y|. Moving Y by one unit changes the total by (number of buildings below) - (number above), so the total keeps decreasing until the two counts balance, which is exactly at a median.
- Find the medianStore all y values, sort them and take ys[N / 2]. For even N any value between the two middle elements is optimal, so either middle element works.
- Sum with 64-bit arithmeticStart from xMax - xMin and add |y_i - median| for every building, using long long in C or long in Java. A single difference can already be 2^31, which does not fit in an int.
Complexity
O(N log N)O(N)Sorting the y-coordinates dominates. A selection algorithm such as nth_element or quickselect finds the median in O(N) average time if you want to skip the full sort.
Solution code
Bug fixed in this version: The original C code fails on valid inputs. First, xMax is initialised to 0, so when every building has a negative x the horizontal length is computed against 0 instead of the real maximum (input 3 buildings at x = -5, -3, -1 gives 7 instead of 6). Second, it adds abs(Ys[N/2] - Ys[i]) where abs() takes and returns an int, so a vertical distance of 2^31 (y = -2^30 and y = 2^30) overflows and the program prints -2147483648. It also reads x into a long with a %Ld format meant for long long. The replacement fixes all three.
Network Cabling – C
#include <stdio.h>
#include <stdlib.h>
static int cmp(const void *a, const void *b) {
long long x = *(const long long *)a, y = *(const long long *)b;
return (x > y) - (x < y);
}
int main(void) {
int n;
scanf("%d", &n);
long long *ys = malloc(n * sizeof *ys);
long long xMin = 0, xMax = 0;
for (int i = 0; i < n; i++) {
long long x;
scanf("%lld %lld", &x, &ys[i]);
if (i == 0 || x < xMin) xMin = x;
if (i == 0 || x > xMax) xMax = x;
}
qsort(ys, n, sizeof *ys, cmp);
long long median = ys[n / 2];
long long total = xMax - xMin;
for (int i = 0; i < n; i++)
total += llabs(ys[i] - median);
printf("%lld\n", total);
free(ys);
return 0;
}
Common mistakes
- Using the average instead of the medianThe mean minimises squared distances, not absolute ones. With buildings at y = 0, 0, 0 and 100 the mean puts the cable at 25 and costs 175, while the median 0 costs only 100.
- Initialising max/min with 0Coordinates can be negative, so xMax = 0 or xMin = 0 silently inflates the horizontal length. Initialise both from the first building, or use the extreme values of the type.
- 32-bit overflowOne vertical distance can reach 2^31 and the total goes far beyond. Every intermediate value, including the absolute value function, must be 64-bit: llabs in C, Math.abs on a long in Java.
- Forgetting the horizontal cable or the single-building caseWith N = 1 the answer is 0: no horizontal length and a vertical cable of length 0. Solutions that only sum vertical distances, or that assume N >= 2, fail the smallest test.
Going further
The median argument is worth understanding rather than memorising, because it explains why the cable does not have to sit on the y of an existing building when N is even. Sort the y values and slide the cable upward one unit at a time: every building above it gets one unit shorter and every building below it gets one unit longer, so the total improves as long as more buildings are above than below. When N is even the two counts are equal for every height between the two middle values, so the cost is flat on that whole segment. This also tells you that you never need to try candidate heights or run a ternary search: the cost is a convex, piecewise linear function and the median is its minimum. For huge inputs, C++ nth_element or a quickselect finds the median in linear time, but with 100,000 buildings a plain sort is already instant.
FAQ
Why is the median optimal in Network Cabling?
Moving the main cable one unit up shortens every vertical cable above it and lengthens every one below it. The total only stops improving when as many buildings are above as below, which is the definition of a median.
For an even number of buildings, which median should I take?
Either middle value, or any height between them: the total is the same on that whole interval, so ys[N/2] or ys[N/2 - 1] both give the right answer.
Why does my solution fail on the large test?
Almost always integer overflow. Use 64-bit integers for coordinates, differences and the total, and make sure your absolute value function works on 64-bit values.