Overview

Two people are standing on cells of an infinitely long number line, and we want to find the minimum number of operations to reach a target arrangement, where each operation swaps the contents of two adjacent cells.

The key point is to split into cases based on whether the left-right order of the two people is the same or reversed between the initial and final states.

Analysis

There are two types of operations:

• Swap a person with an empty cell
  → That person moves one cell to the side
• Swap the two people when they are adjacent
  → The left-right relationship of the two people is reversed

The important observation here is that the left-right relationship only changes when the two people are directly swapped.

Let the initial positions in ascending order be

\( a < b \)

and the target positions in ascending order be

\( c < d \)

Case where the left-right relationship does not change

For example, when Takahashi is to the left of Aoki both at the start and at the end.

In this case, there is no need to directly swap the two people.
Simply move the person on the left to the left target position, and the person on the right to the right target position.

Therefore the answer is

\( |a-c| + |b-d| \)

Even if you directly swap the two people, the set of occupied cells does not change, so it cannot lead to a shorter solution.

Case where the left-right relationship is reversed

In this case, the two people must be directly swapped at some point.

Suppose the swap operation takes place between cells \(x\) and \(x+1\).

Just before the swap:

• The person initially on the left is at \(x\)
• The person initially on the right is at \(x+1\)

The movement cost up to this point is

\( |a-x| + |b-(x+1)| \)

Then, directly swapping the two people costs \(1\).

After the swap, the left-right relationship matches the target, so:

• Move the left person to \(c\)
• Move the right person to \(d\)

The cost for this is

\( |x-c| + |x+1-d| \)

Therefore, the total cost when the swap position is \(x\) is

\( |a-x| + |b-(x+1)| + 1 + |x-c| + |x+1-d| \)

Rearranging this gives:

\( 1 + |x-a| + |x-(b-1)| + |x-c| + |x-(d-1)| \)

In other words, we need to minimize the sum of distances to the following four values:

\( a,\ b-1,\ c,\ d-1 \)

If we sort these four values in ascending order as

\( v_0 \leq v_1 \leq v_2 \leq v_3 \)

then the minimum of

\( |x-v_0| + |x-v_1| + |x-v_2| + |x-v_3| \)

is

\( (v_3-v_0) + (v_2-v_1) \)

This is because the minimum is achieved when \(x\) is between \(v_1\) and \(v_2\).

Therefore, the answer when the left-right relationship is reversed is

\( (v_3-v_0) + (v_2-v_1) + 1 \)

Algorithm

1. Sort the initial positions \(A, B\) in ascending order to get \(a, b\)
2. Sort the target positions \(C, D\) in ascending order to get \(c, d\)
3. Check whether the left-right relationship is the same in the initial and target states
   • Specifically, check whether \((A < B) = (C < D)\)
4. If the left-right relationship is the same, output

\( |a-c| + |b-d| \)

1. If the left-right relationship is reversed:

   • Put \(a, b-1, c, d-1\) into an array and sort it
   • Let the sorted array be \(v\), and output

   \( (v_3-v_0) + (v_2-v_1) + 1 \)

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(1)\)

Since we only sort 4 values, it is essentially constant time.

Implementation Notes

• Coordinates can be as large as \(10^{18}\), so simulation is not feasible.
• In Python, there is no need to worry about integer overflow.
• If implementing in C++ or similar languages, use long long.
• The left-right relationship check can be written as follows:

if (A < B) == (C < D):
    ...

• The values used when the left-right relationship is reversed are \(a, b-1, c, d-1\).
  The \(b-1\) and \(d-1\) appear because the swap takes place between cells \(x\) and \(x+1\).

  Source Code

import sys

A, B, C, D = map(int, sys.stdin.readline().split())

a, b = (A, B) if A < B else (B, A)
c, d = (C, D) if C < D else (D, C)

if (A < B) == (C < D):
    ans = abs(a - c) + abs(b - d)
else:
    v = [a, b - 1, c, d - 1]
    v.sort()
    ans = (v[3] - v[0]) + (v[2] - v[1]) + 1

print(ans)

---

This editorial was generated by gpt-5.5-high.