2 ms·

Thanks. I enjoyed reading this and found it sufficiently detailed that I could understand it despite being previously unfamiliar with some of it. I don't quit

Thanks. I enjoyed reading this and found it sufficiently detailed that I could understand it despite being previously unfamiliar with some of it. I don't quite understand why this solution is preferable to a solution which simply evaluates S(P_j) for each j and returns the minimum in O(n^2) time. I'm also not sure why I would prefer it to a solution that is faster. One O(n lg n) solution requires that we convert the "Minimum sum of distances at a house for houses on lattice points in 2-space under the square metric" problem to an equivalent "Minimum sum of distances at a house for houses on lattice points in 2-space under the taxicab metric" problem, at which point we can consider the two dimensions independently. With some trickery we can find the sum of distances to other houses for all houses in the 1-dimensional version of the problem in linear time plus the amount of time required to sort the houses. To do this, we begin at the house with the lowest coordinate and calculate its sum of distances. From the the sum of distances for one house, we can calculate the sum of distances for the next house in constant time: S(P_j) = S(P_j-1) + |P_j - P_j-1|(j) - |P_j - P_j-1|(n-j). This is not the most compact form and is an abuse of the notation considering that it refers only to the 1-dimensional problem, but I think it conveys its meaning well: Once the houses are sorted, the sum of distances for a house other than the first is the sum of distances for the previous house plus the distance between them for each house with a lower coordinate than this house, minus the distance between them for each house with a higher coordinate than this house. The phrasing of that is not quite right for houses that have the same coordinate, but that doesn't particularly matter since the distance between them will be 0. After that we can calculate S(P_j) as the the sum of distances for P_j along one dimension and along the other. Finally, since we've calculated the sum of distances for each house, we can just print the least of these. We could also solve the problem in linear time if we were willing to use radix sort, but we probably wouldn't want to do that.

bumbledraven 15y ago
Exactly. I did just this, and still my algorithm supposedly gets only 4/15 test cases correct. The algorithm is pretty simple, and I tested it extensively against the naive O(n^2) algorithm on a bunch of random test cases and it always prints the same thing, so I'm not sure where it's going wrong. My one consolation is that no one else seems to have solved it either yet... Ah, the joy and frustration of programming challenges.
- NY_Entrepreneur 15y ago
  The conversion from the given metric to the 'taxicab' metric needs some justification! The n^2 algorithm is simple enough to be solid. If your code does not give their answers, then their answers might be wrong! My work with convexity is an effort at faster code, but actually programming all that would be a bit much. I've done such things, but I got the linear programming from the old IBM Fortran Optimization Subroutine Library (OSL) and, then, wrote the code in Watcom Fortran so that I could use the Fortran OSL OBJ files. Using the OSL for the problem in this thread would be a bit much.
  - bumbledraven 15y ago
    You're right! They seem to have fixed a bug in their test program, and I'm now credited with solving that problem. As for the justification, it shouldn't be too hard to show with a little algebra that TaxicabDistance(x1+y1, y1-x1, x2+y2, y2-x2)/2 = ChebyshevDistance(x1, y1, x2, y2) where ChebyshevDistance(x1, y1, x2, y2) = max(|x1-x2|,|y1-y2|) and TaxicabDistance(x1, y1, x2, y2) = |x1-x2|+|y1-y2|.
    - NY_Entrepreneur 15y ago
      There's a nice justification in http://news.ycombinator.com/item?id=2865396 http://news.ycombinator.com/item?id=2865396 So, we have a linear transformation from R^2 into R^2 with matrix 1 1 1 -1 So, the rows are orthogonal! And the columns! It's not quite an orthonormal matrix where its transpose is its inverse because the length of each row, column is not 1, but it's 'close' to orthonormal. So, except for a scalar multiple, this linear transformation has to be an 'isometry', that is, preserves lengths and angles, lengths in the usual metric in R^2. So, this linear transformation starts to 'smell good'! Looking, for the given metric, consider the 'unit circle', that is, all points distance 1 from the origin. Then consider the image of these points under this linear transformation. That 'circle' is a square with diagonal (1,1) to (-1,-1). Then its image is a 'diamond', that is, a square with diagonal, say, (-2,0) to (2,0). So, except for a scalar 2, we have preserved distances. That is, our linear transformation is 1-1 between a 'circle' in one metric and a circle in the other metric. That's close enough to a proof for gumment work! Nice. Be wise, generalize: So we have taken a nasty problem with an n^2 solution, or some tricky, solution iterating with convexity, and with a simple linear transformation turned the problem into a 'decomposition' on the two coordinates separately. So, where else can we take a challenging optimization problem, stuff a linear transformation inside the problem, and get a much simpler problem? Hmm ....
NY_Entrepreneur 15y ago
The conversion from the given metric to the 'taxicab' metric needs some justification! Else use just the n^2 approach or, if really want to struggle for something faster, then use my convexity approach. There may be another approach if can find a cute way to exploit the special properties of that special metric.
- anonymoushn 15y ago
  The taxicab metric is useful here because if you compute the components of a distance in the square metric, you must max() them together, while under the taxicab metric you can add them together. We can add a pair of large sums together to get the large sum of pairs, but we can't max() a pair of large sums together to get the large sum of max()es. One way to get to the taxicab metric verson of the problem is to take w = x + y and z = x - y. From then on all the distances you calculate in wz-space under the taxicab metric will be precisely twice the distance between the same points in xy-space under the square metric.
  - NY_Entrepreneur 15y ago
    Nice! Then, if all this is correct, your solution should be nicely fast. Cute conversion of the metrics!

bumbledraven 15y ago

Exactly. I did just this, and still my algorithm supposedly gets only 4/15 test cases correct. The algorithm is pretty simple, and I tested it extensively against the naive O(n^2) algorithm on a bunch of random test cases and it always prints the same thing, so I'm not sure where it's going wrong. My one consolation is that no one else seems to have solved it either yet... Ah, the joy and frustration of programming challenges.

NY_Entrepreneur 15y ago
The conversion from the given metric to the 'taxicab' metric needs some justification! The n^2 algorithm is simple enough to be solid. If your code does not give their answers, then their answers might be wrong! My work with convexity is an effort at faster code, but actually programming all that would be a bit much. I've done such things, but I got the linear programming from the old IBM Fortran Optimization Subroutine Library (OSL) and, then, wrote the code in Watcom Fortran so that I could use the Fortran OSL OBJ files. Using the OSL for the problem in this thread would be a bit much.
- bumbledraven 15y ago
  You're right! They seem to have fixed a bug in their test program, and I'm now credited with solving that problem. As for the justification, it shouldn't be too hard to show with a little algebra that TaxicabDistance(x1+y1, y1-x1, x2+y2, y2-x2)/2 = ChebyshevDistance(x1, y1, x2, y2) where ChebyshevDistance(x1, y1, x2, y2) = max(|x1-x2|,|y1-y2|) and TaxicabDistance(x1, y1, x2, y2) = |x1-x2|+|y1-y2|.
  - NY_Entrepreneur 15y ago
    There's a nice justification in http://news.ycombinator.com/item?id=2865396 http://news.ycombinator.com/item?id=2865396 So, we have a linear transformation from R^2 into R^2 with matrix 1 1 1 -1 So, the rows are orthogonal! And the columns! It's not quite an orthonormal matrix where its transpose is its inverse because the length of each row, column is not 1, but it's 'close' to orthonormal. So, except for a scalar multiple, this linear transformation has to be an 'isometry', that is, preserves lengths and angles, lengths in the usual metric in R^2. So, this linear transformation starts to 'smell good'! Looking, for the given metric, consider the 'unit circle', that is, all points distance 1 from the origin. Then consider the image of these points under this linear transformation. That 'circle' is a square with diagonal (1,1) to (-1,-1). Then its image is a 'diamond', that is, a square with diagonal, say, (-2,0) to (2,0). So, except for a scalar 2, we have preserved distances. That is, our linear transformation is 1-1 between a 'circle' in one metric and a circle in the other metric. That's close enough to a proof for gumment work! Nice. Be wise, generalize: So we have taken a nasty problem with an n^2 solution, or some tricky, solution iterating with convexity, and with a simple linear transformation turned the problem into a 'decomposition' on the two coordinates separately. So, where else can we take a challenging optimization problem, stuff a linear transformation inside the problem, and get a much simpler problem? Hmm ....

NY_Entrepreneur 15y ago

The conversion from the given metric to the 'taxicab' metric needs some justification! Else use just the n^2 approach or, if really want to struggle for something faster, then use my convexity approach. There may be another approach if can find a cute way to exploit the special properties of that special metric.

anonymoushn 15y ago
The taxicab metric is useful here because if you compute the components of a distance in the square metric, you must max() them together, while under the taxicab metric you can add them together. We can add a pair of large sums together to get the large sum of pairs, but we can't max() a pair of large sums together to get the large sum of max()es. One way to get to the taxicab metric verson of the problem is to take w = x + y and z = x - y. From then on all the distances you calculate in wz-space under the taxicab metric will be precisely twice the distance between the same points in xy-space under the square metric.
- NY_Entrepreneur 15y ago
  Nice! Then, if all this is correct, your solution should be nicely fast. Cute conversion of the metrics!