aka.Sohieb's blog

Need hint (New York Hotel)
By aka.Sohieb, history, 9 years ago, In English

Hello, guys!

I need help in this problem 491B - New York Hotel, there is no tutorials for this round and I can not get the idea to solve it.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Imagine that, instead of writing a point as (X, Y), we think of it as (X' = X + Y, Y' = X - Y). Visually, you can think of this transformation as rotating the grid by 45 degrees, so that the diagonals become the rows and columns.

Before the transformation, the distance between two points was given by abs(X1 - X2) + abs(Y1 - Y2), which is max(X1 - X2, X2 - X1) + max(Y1 - Y2, Y2 - Y1). It's hard to simplify things when you have operators like sum and max mixed together. We cannot do anything simple like looking only at the furthest point in each direction. At the same time, considering all of the points is too expensive.

But now, distance is given by max(max(X'1 - X'2, X'2 - X'1), max(Y'1 - Y'2, Y'2 - Y'1)) (can you see why?). In order to determine how good a restaurant is, we're interested in the maximum over all of the distances to the hotels. Since we are dealing only with max, we are free to regroup the terms as we want. So, let's find the maximum possible (R'X - H'X), the maximum possible (H'X - R'X), etc. To do that, we only need to consider the most extreme values of H'X and H'Y among the hotels, and that's easy to do.

You can see my implementation here: 8840674.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why the distance given by max(max(X'1 - X'2, X'2 - X'1), max(Y'1 - Y'2, Y'2 - Y'1)) after this transformation?! I can not get this part!!

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      consider you want to calculate distance between two points B and A. there are 4 cases : 1) point B is at right down of A then the distance will be : xA+yA-(xB+yB) 2) point B is at left up of A then the distance will be : xB+yB-(xA+yA) 3) point B is at left down of A then the distance will be : xA-yA-(xB-yB) 4) point B is at right up of A then the distance will be : xB-yB-(xA-yA) so the maximum distance will be : max(max(X'1 - X'2, X'2 - X'1), max(Y'1 - Y'2, Y'2 - Y'1))

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      One way to see it is that the four moves you can make in the grid, which were previously (0, 1), (1, 0), (0, -1), and (-1, 0), look like (1, -1), (1, 1), (-1, 1), (-1, -1) along the rotated axes.

      That means two things. One, we can handle the two dimensions X' and Y' independently. Two, if you have a difference DX' = X'1 - X'2, you need DX' moves to cover the difference, and then you are allowed to make an even number of extra steps (we can throw them away by alternating +1 and -1).

      DX' and DY' always have the same parity, so we can just pick the bigger one as our number of steps, and it is clearly minimal.

      → Reply