PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef is standing at position K, and wants to reach position N.
He can:
- Move one step to the left/right.
- Mirror his position in the segment [1, N], meaning move to N+1-X from X.
Find the minimum number of moves to reach X.
EXPLANATION:
To make the analysis simple, for now suppose N is even - say N = 2M.
Let’s split the segment [1, N] into two equal halves: [1, M] and [M+1, N].
Now,
- If K \geq M+1, i.e. Chef starts in the right half, it’s optimal to just repeatedly walk right till he reaches N.
This is because the mirror operation will put him in the left half so it’s not helpful to use it.
The number of moves needed is thus simply (N - K). - If K \leq M, i.e. Chef starts in the left half, it’s optimal to repeatedly walk left till he reaches 1, and then use the mirror operation to immediately end up at N.
The number of operations needed is K, because there are (K-1) steps left and then one mirror operation.
If N is odd, the analysis is similar: if Chef starts in the right half it’s optimal to just move right; and if he starts in the left half he should move left to reach 1 and then use the mirror operation.
So,
- If K \ge \lceil\frac{N}{2}\rceil, the answer is (N-K).
- If K \lt \lceil\frac{N}{2}\rceil, the answer is instead K.
Here, \lceil x \rceil denotes the value of x when rounded up to the nearest integer.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
if k <= n//2: print(k)
else: print(n-k)