Overview

This problem asks whether \(N\) friends on a number line, each moving exactly \(T\) times with a fixed step size \(P_i\), can all gather at the same coordinate. We express the conditions that each friend’s final coordinate must satisfy as mathematical formulas, reduce the problem to finding the common intersection of “ranges (intervals)” and “congruences (remainders)”, and solve it using the extended Euclidean algorithm (an extension of the Chinese Remainder Theorem).

---

Analysis

1. Coordinates reachable by a single friend

Consider friend \(i\) moving from initial position \(X_i\) with step size \(P_i\) for \(T\) moves. Out of \(T\) moves, if they move in the positive direction (\(+P_i\)) \(k\) times and in the negative direction (\(-P_i\)) \(T-k\) times (where \(0 \leq k \leq T\)), the final coordinate \(Y\) is:

\[ \begin{aligned} Y &= X_i + k P_i - (T - k) P_i \\ &= X_i + (2k - T) P_i \\ &= (X_i - T P_i) + 2k P_i \end{aligned} \]

From this formula, we can see that a coordinate \(Y\) reachable by friend \(i\) is an integer satisfying both of the following conditions simultaneously:

1. Range condition: The minimum is achieved when moving entirely in the negative direction, and the maximum when moving entirely in the positive direction: $\(X_i - T P_i \leq Y \leq X_i + T P_i\)$

2. Remainder condition (congruence): The difference between \(Y\) and the minimum coordinate \(X_i - T P_i\) must be a multiple of \(2 P_i\): $\(Y \equiv X_i - T P_i \pmod{2 P_i}\)$

2. Conditions for all friends to gather at the same coordinate

For all friends to gather at the same coordinate \(Y\), there must exist a \(Y\) that satisfies both conditions above for all \(i\).

① Intersection of ranges

Let the reachable range of friend \(i\) be \([l_i, r_i] = [X_i - T P_i, X_i + T P_i]\). The coordinate \(Y\) where everyone can gather must be contained in the intersection \([L, R]\) of all ranges. - \(L = \max(l_1, l_2, \dots, l_N)\) - \(R = \min(r_1, r_2, \dots, r_N)\)

If \(L > R\), there is no common range where everyone can gather, so we can immediately determine No.

② Common solution of congruences

The congruence for each friend \(i\) is: $\(Y \equiv a_i \pmod{d_i} \quad (\text{where } a_i = X_i - T P_i, \ d_i = 2 P_i)\)$

We need to find \(Y\) satisfying this congruence for all \(i\). This can be solved by merging congruences one by one using the extended Chinese Remainder Theorem (CRT).

---

Algorithm

1. Merging two congruences

We merge the congruence obtained so far \(Y \equiv A \pmod{D}\) with a new friend’s congruence \(Y \equiv a_i \pmod{d_i}\) to produce a new congruence \(Y \equiv A_{\text{new}} \pmod{D_{\text{new}}}\).

This corresponds to solving the following Diophantine equation: $\(A + x \cdot D = a_i - y \cdot d_i \iff x \cdot D + y \cdot d_i = a_i - A\)$

The necessary and sufficient condition for this equation to have an integer solution \((x, y)\) is that \(a_i - A\) is a multiple of \(g = \gcd(D, d_i)\). - If not a multiple: No common solution exists, so output No and terminate. - If a multiple: Use the extended Euclidean algorithm to find the solution \(x\) of \(x \cdot D + y \cdot d_i = g\), then compute the new \(A_{\text{new}}\) and \(D_{\text{new}} = \text{lcm}(D, d_i) = \frac{D \cdot d_i}{g}\).

2. Search range optimization (early termination)

As merging progresses, the modulus \(D\) can become very large. If the new modulus \(D_{\text{new}}\) exceeds the length of the common range \(R - L\) (i.e., \(D_{\text{new}} > R - L\)), then there is at most one \(Y\) within the range \([L, R]\) that satisfies the congruence.

Leveraging this property, we directly compute the sole candidate \(Y\) at that point and directly check whether that \(Y\) satisfies all friends’ conditions, allowing us to skip subsequent heavy computations and make a fast determination.

3. Final determination

After all merges are complete (or after narrowing down to a single candidate midway), we determine whether a \(Y\) satisfying the congruence \(Y \equiv A \pmod{D}\) exists within the common range \([L, R]\).

Specifically, we check whether there exists an integer \(k\) satisfying: $\(L \leq A + k \cdot D \leq R\)\( using floor and ceiling division. If such \)k$ exists, the answer is Yes; otherwise, it is No.

---

Complexity

• Time complexity: \(O(N \log(\max P_i))\) We perform the extended Euclidean algorithm once for each of the \(N\) friends. The complexity of the algorithm is \(O(\log(\min(D, d_i)))\), and since each \(P_i \leq 10^9\), it runs sufficiently fast.
• Space complexity: \(O(N)\) Depends on the array size needed to store the initial coordinates \(X_i\) and step sizes \(P_i\) for each friend.

---

Implementation Notes

• Extended Euclidean algorithm: A function is implemented within the loop that simultaneously computes the greatest common divisor \(g\) of two numbers and the solution to the linear Diophantine equation \(ax + by = g\).

• Large number handling and early termination: To prevent the modulus \(D\) from growing explosively due to the least common multiple (lcm), once D_new > R - L, the check_all function is called to directly determine the answer in \(O(N)\). This prevents overflow and TLE (Time Limit Exceeded) even in languages like Python.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    T = int(data[1])
    
    X = [0] * N
    P = [0] * N
    for i in range(N):
        X[i] = int(data[2 + 2*i])
        P[i] = int(data[3 + 2*i])
        
    def check_all(Y, X, P, T):
        for xi, pi in zip(X, P):
            li = xi - T * pi
            ri = xi + T * pi
            if not (li <= Y <= ri):
                return False
            if (Y - li) % (2 * pi) != 0:
                return False
        return True

    A = X[0] - T * P[0]
    D = 2 * P[0]
    L = X[0] - T * P[0]
    R = X[0] + T * P[0]
    
    for i in range(1, N):
        xi, pi = X[i], P[i]
        li = xi - T * pi
        ri = xi + T * pi
        L = L if L > li else li
        R = R if R < ri else ri
        if L > R:
            print("No")
            return
        
        di = 2 * pi
        ai = li
        
        # Extended GCD
        a_val, b_val = D, di
        x0, y0, x1, y1 = 1, 0, 0, 1
        while b_val != 0:
            q, r = divmod(a_val, b_val)
            a_val, b_val = b_val, r
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1
        g, x, y = a_val, x0, y0
        
        if (ai - A) % g != 0:
            print("No")
            return
        
        mod_val = di // g
        t = (x * ((ai - A) // g)) % mod_val
        A_new = A + t * D
        D_new = D * mod_val
        
        if D_new > R - L:
            k_min = -((A_new - L) // D_new)
            k_max = (R - A_new) // D_new
            if k_min <= k_max:
                Y = A_new + k_min * D_new
                if check_all(Y, X, P, T):
                    print("Yes")
                else:
                    print("No")
            else:
                print("No")
            return
        
        A = A_new
        D = D_new

    k_min = -((A - L) // D)
    k_max = (R - A) // D
    if k_min <= k_max:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.