Official

E - Tile Distance 2 Editorial by en_translator

For simplicity, we may assume that the start and goal is in the left half of a tile. (That is, if \(S _ x+S _ y\) is odd, subtract \(1\) from \(S _ x\).)

Logical derivation

One can freely travel between the left half and right half, so we regard a travel from the left half of a tile to the left half of another as a one batch of move.

By paying a toll of \(1\), one can make one of the following two moves:

  • Move by \(1\) vertically, and move by \(1\) horizontally.
  • Move by \(2\) horizontally.

Suppose that one could travel from \((S _ x,S _ y)\) to \((T _ x,T _ y)\) by making the former move \(a\) times and the latter \(b\) times .

Then the following property holds.

  • \(\lvert S _ y-T _ y\rvert\leq a\)
  • \(\lvert S _ x-T _ x\rvert\leq a+2b\)
  • \(a\gt0\) or \(S _ x-T _ x\equiv2b\pmod4\)

Conversely, if a pair of non-negative integers \((a,b)\) satisfies the condition above, then one can make the former move \(a\) times and the latter \(b\) times to travel from \((S _ x,S _ y)\) to \((T _ x,T _ y)\).

Therefore, we want to minimize the toll \(a+b\) under \((0\leq a,0\leq b)\) and the conditions above.

By \(0\leq b,\lvert S _ y-T _ y\rvert\leq a\), it is necessary that \[\lvert S _ y-T _ y\rvert\leq a+b.\quad\cdots\ (1)\] Since \(\lvert S _ y-T _ y\rvert\leq a,\lvert S _ x-T _ x\rvert\leq a+2b\), it is necessary that \[\dfrac{\lvert S _ y-T _ y\rvert+\lvert S _ x-T _ x\rvert}2\leq a+b.\quad\cdots\ (2)\]

Conversely, \((a,b)=\left(\lvert S _ y-T _ y\rvert,\max\left\lbrace0,\dfrac{\lvert S _ x-T _ x\rvert-\lvert S _ y-T _ y\rvert}2\right\rbrace\right)\) always satisfies all the conditions, and one of \((1)\) and \((2)\) is true as an equation.

Hence, the sought minimum toll is represented as\[\max\left\lbrace\lvert S _ y-T _ y\rvert,\dfrac{\lvert S _ x-T _ x\rvert+\lvert S _ y-T _ y\rvert}2\right\rbrace=\dfrac{\lvert S _ y-T _ y\rvert+\max\lbrace\lvert S _ x-T _ x\rvert,\lvert S _ y-T _ y\rvert\rbrace}2.\]
While one can derive it by reorganizing the conditions as described in the folded section, one may also be able to obtain it by doing experiment for smaller cases and recognize and proof the pattern.
Deforming the plane as follows may also lead to the expression too.

The following is sample code.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    long Sx, Sy, Tx, Ty;
    cin >> Sx >> Sy >> Tx >> Ty;

    // Move to the left half of the tile
    if ((Sx + Sy) % 2 == 1) {
        --Sx;
    }
    if ((Tx + Ty) % 2 == 1) {
        --Tx;
    }

    // The answer is (|Sy - Ty| + max(|Sx - Tx|, |Sy - Ty|)) / 2
    long Dx = abs(Sx - Tx);
    long Dy = abs(Sy - Ty);
    
    cout << (Dy + max(Dx, Dy)) / 2 << endl;
    return 0;
}

Sx, Sy = map(int, input().split())
Tx, Ty = map(int, input().split())

# Move to the left half of the tile
if (Sx + Sy) % 2 == 1:
    Sx -= 1
if (Tx + Ty) % 2 == 1:
    Sx -= 1

# The answer is (|Sy - Ty| + max(|Sx - Tx|, |Sy - Ty|)) / 2
Dx = abs(Sx - Tx)
Dy = abs(Sy - Ty)

print((Dy + max(Dx, Dy)) // 2)

posted:
last update: