psywoo's blog

By psywoo, history, 2 years ago, In English

Problem :

You are standing at point (0 , 0). You can move to any point with integer coordinates that is exactly K units away in terms of manhattan distance from the point you are currently standing at. For eg : K = 3 , and you are standing at ( 4, -3) you can go to ( 5 , -5 ) or ( 4 , 0 ) as they both are at a manhattan distance of K (note that there are other options too).

You need to answer the minimum number of moves required to reach point (x , y) or say its impossible to reach (x , y)

Constraints :

-1e5 <= x , y <= 1e5

1 <= K <= 1e9

Sample TC : K = 3

pt = ( 1 , 3 )

output : 2

explanation : In one move you can go from (0 , 0) to (-3 , 2) Distance = |0 — (-3)| + |0 — 2| = 5 , and then from (-3, 2) you can go to (1 , 3) Distance = |-3 — 1| + |2 — 3| = 5 . So 2 moves is the minimum answer.

  • Vote: I like it
  • +11
  • Vote: I do not like it

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

Firstly let's perform a transformation $$$\varphi:(x,y)\mapsto (x+y,x-y)$$$ on this space. After that, the Manhattan distance turns to Chebyshev distance.

Assuming that you're currently standing at $$$P$$$, your target is $$$Q$$$, and $$$h(P,Q)$$$ is the Chebyshev distance between $$$P$$$ and $$$Q$$$, I think there're $$$3$$$ cases:

  1. When $$$K>h(P,Q)$$$, $$$2$$$ steps is needed. We can draw a $$$2K\times 2K$$$ rectangle whose center is $$$Q$$$, and move to it's edge by $$$1$$$ step.

  2. When $$$K\mid h(P,Q)$$$, it's obvious that we can reduce $$$h(P,Q)$$$ exactly by $$$K$$$ each time we move, so the answer is $$$h(P,Q)/K$$$.

  3. Otherwise, $$$\lceil h(P,Q)/K\rceil$$$ steps is needed, as we can reach the edge of the rectangle mentioned in case 1 in $$$\lceil h(P,Q)/K\rceil-1$$$ steps.

Poor at English :(

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    What about the Impossible cases ??

    I couldn't find any solution to this TC :

    TC

    Is there a way to generalise what kind of cases will be impossible ??

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Oops, it's my mistake, sorry :( There're some $$$P$$$ that $$$\varphi^{-1}(P)$$$ is not a point with integer coordinates.