1816

Codeforces Round 865 (Div. 2)

A_Ian_Visits_Mary

Explanation

Ian and Mary are frogs living on a grid (Cartesian coordinate plane) with integer coordinates. Ian starts at point (0,0), and Mary is at point (a, b).

Ian wants to reach Mary in at most two jumps. Ian can only jump from one point with integer coordinates to another point with integer coordinates without landing on any other integer-coordinate point in between.

1. Ian can always reach Mary in two jumps.
2. The first jump can either be to a point on the same diagonal as Mary's position or to a point with the same x or y coordinate.
3. In this solution, Ian jumps to the point (a - 1, 1) if a > 0 or to the point (1, 1) if a = 0. This guarantees that no other integer-coordinate points are on the line segment between the starting point and the first jump point.
4. In the second jump, Ian jumps directly to Mary's position (a, b).

def solve():
    a, b = map(int, input().split())
    if a > 0:
        print(2)
        print(a - 1, 1)
        print(a, b)
    else:
        print(2)
        print(1, 1)
        print(a, b)


for _ in range(int(input())):
    solve()

B_Grid_Reconstruction

Explanation

1. Start by placing the maximum value (2 * 𝑛) in the top-left cell (1, 1), and the second maximum value (2 * 𝑛 - 1) in the bottom-right cell (2, 𝑛).
2. Fill the remaining cells in the first row and the second row using the remaining numbers in descending order while alternating rows.
3. If the row has an even number of cells, start filling the row from the second cell, otherwise start from the first cell.

def solve():
    n = int(input())
    grid = [[None] * n for _ in range(2)]
    grid[0][0] = n * 2
    grid[-1][-1] = n * 2 - 1

    for i in range(2):
        tmp1 = n * 2 - 2 - i % 2
        tmp2 = (i + 1) % 2 + 1

        for j in range(n):
            if grid[i][j] is None:
                if (i + j) % 2:
                    grid[i][j] = tmp2
                    tmp2 += 2
                else:
                    grid[i][j] = tmp1
                    tmp1 -= 2

    for line in grid:
        print(*line)


for _ in range(int(input())):
    solve()

C_Ian_and_Array_Sorting

Explanation

The main idea of the solution is to iterate through the array, making the difference between consecutive pairs alternate between positive and negative. To do this, we can perform the following algorithm:

1. Iterate through the array with a step of 2 (i.e., process every other element).
2. For each element, check if it is the last element or the second-last element.
3. If it's the last element, the answer is "YES" because we can always make the array non-decreasing by adding or subtracting the same value from every other element.
4. If it's the second-last element, the answer is "YES" if the current element is less than or equal to the next element, otherwise, it's "NO".
5. If the current element is not the last or second-last element, update the next next element by subtracting the difference between the current element and the next element. This ensures that the difference between consecutive pairs alternates between positive and negative.

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    for i in range(0, n, 2):
        if i == n - 1:
            print("YES")
            return
        if i == n - 2:
            if a[i] <= a[i + 1]:
                print("YES")
            else:
                print("NO")
            return

        a[i + 2] -= a[i + 1] - a[i]

    print("YES")


for _ in range(int(input())):
    solve()