Блог пользователя aka.Sohieb

Need hint (New York Hotel)
Автор aka.Sohieb, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!!

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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))

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить