EXPSTP - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Divya Patel
Testers: Nishank Suresh, Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1310

PREREQUISITES:

None

PROBLEM:

There is an N\times N grid, and Chef wants to move from position (x_1, y_1) to (x_2, y_2) using horizontal and/or vertical moves.
Each lateral step has a cost of 1 if either the starting or ending square lie within the grid, and 0 otherwise.

What is the minimum cost to reach (x_2, y_2) from (x_1, y_1)?

EXPLANATION:

There are two cases to consider: Chef can either travel fully within the grid, or he can choose to travel outside of it.

Within the grid

Chef needs to make |x_2 - x_1| horizontal steps and |y_2 - y_1| vertical steps to reach (x_2, y_2), so the minimum cost in this case is their sum, i.e,

|x_2-x_1| + |y_2-y_1|
Outside the grid

When choosing to travel outside the grid, Chef’s optimal route is to leave the grid as soon as possible, travel outside of it for some time, then enter it again as close to (x_2, y_2) as possible.

From a point (x, y), the smallest number of moves to reach the border is one out of:

  • x (move straight up)
  • y (move straight left)
  • N+1-x (move straight down)
  • N+1-y (move straight right)

In particular, it is the minimum of these four values.
So, the answer in this case is

\min(x_1, y_1, N+1-x_1, N+1-y_1) + \min(x_2, y_2, N+1-x_2, N+1-y_2)

Consider both cases, compute their answers, and take their minimum as the final answer.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x, y, a, b = map(int, input().split())
    ans = min(abs(x-a) + abs(y-b), min(x, y, n+1-x, n+1-y) + min(a, b, n+1-a, n+1-b))
    print(ans)
1 Like
2

when counting the cost of traveling outside the grid why doesnt the below
solution works,

res = min(min(x1,y1)+n-max(x2,y2)+1,n-max(x1,y1)+1+min(x2,y2))
where (x1,y1) are the initial point and (x2,y2) are the destination point.