20240628

Thanks to enough sleep, I feel that I'm recovered.

1935A. Entertainment in MAC

n => even

we have two options for each operation

  1. s => s + s[::-1]
  2. s => s[::-1]

for each two operations

  1. s => s[::-1] => s’[::-1] => s (no change)
  2. s => s + s[::-1] => s’[::-1] => s + s[::-1] > s
  3. s => s[::-1] => s’ + s’[::-1] => s[::-1] + s

We only need to compare s and s[::-1] + s. Once we get the smallest string, we can simply keep reversing it, ending up the smallest string.

for _ in range(int(input())):
    n = int(input())
    s = input()
    srev = s[::-1]
    if s <= srev:
        print(s)
    else:
        print(srev + s)

1986B. Matrix Stabilization

First impression: that would be great if we could simply iterate through the matrix to perform the modifications.

for i in range(n):
  for j in range(m):
    # operations

After observation, once a cell is decreased to meet the requirement, we don't need to modify it because it makes its adjacent cells meet the requirement (?).

def solve(n: int, m: int, mat: list[list[int]]) -> None:
    for i in range(n):
        for j in range(m):
            max_nei = -1
            if i > 0:
                max_nei = max(max_nei, mat[i - 1][j])
            if i < n - 1:
                max_nei = max(max_nei, mat[i + 1][j])
            if j > 0:
                max_nei = max(max_nei, mat[i][j - 1])
            if j < m - 1:
                max_nei = max(max_nei, mat[i][j + 1])
            mat[i][j] = min(mat[i][j], max_nei)


for _ in range(int(input())):
    n, m = map(int, input().split())
    matrix = []
    for i in range(n):
        matrix.append(list(map(int, input().split())))

    solve(n, m, matrix)
    for i in range(n):
        print(" ".join([str(e) for e in matrix[i]]))

Total 3500 kcal

push ups

TODO:

index 20240627 20240629