20240609

woke up at 3:30 pm

Read “Don’t DRY Your Code Prematurely”

I tend to group similar logic, so the advice

Applying DRY principles too rigidly leads to premature abstractions that make future changes more complex than necessary.

made me doubt my thought process and reconsider it.

I still don't have that many experiences, but I will keep that in mind.

1980C. Sofia and the Lost Operations

If the last element of d does not appear in the modified array b, it's impossible to transform the original array a into b with the modifications d.

If the last elemenf of d does exist in the modified array b, we can just check if differences of b and a (set(b) - set(a)) exist in the modifications d. That is because any redundant modifications that do not contribute to the transformations a -> b can be overridden by the last element of d. (i.e., the transformations can be done by concentrating all the redundant operations under the bi=dm).

The difficulty of this problem is 1300, so I might want to skip this problem for now though I kind of understand the solution. I'll look in details later.

def possible(
    n: int, b: list[int], m: int, drr: list[int], dif: list[int], k: int
) -> bool:
    # drr[m - 1] must be present in the changed array brr
    if drr[m - 1] not in brr:
        return False

    drr = sorted(drr)

    bi: int = 0
    di: int = 0

    while bi < k and di < m:
        if dif[bi] == drr[di]:
            bi += 1
            di += 1
        elif dif[bi] < drr[di]:
            return False
        else:
            di += 1

    return bi == k


for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    brr = list(map(int, input().split()))
    m = int(input())
    drr = list(map(int, input().split()))

    dif = []
    for i in range(n):
        if arr[i] != brr[i]:
            dif.append(brr[i])
    dif.sort()

    if possible(n, brr, m, drr, dif, len(dif)):
        print("YES")
    else:
        print("NO")

410 Gone

It is advised that services should return 410 Gone when shutting down. For example, I have a Mastodon instance on ocalaavenue.net, and I should use AWS lambda function or Netlify to return 410 Gone if I decide to shut down the server. That will help relay (or connected) servers to know my instance is removed.

I didn't follow this with my previous Mastodon instance. I just used its self-destruct command. It should have been sufficient, but I'll try to return 410 Gone next time I migrate the instance (or finally decide to remove my instance).

410 Gone - HTTP | MDN

The HyperText Transfer Protocol (HTTP) 410 Gone client error response code indicates that access to the target resource is no longer available at the origin server and that this condition is likely to be permanent.

1593B. Make it Divisible by 25

BFS approach results in “Time limit exceeded.” I haven't encountered any competitive programming problems to use BFS. Are there?

from collections import deque


def bfs(n: int) -> int:
    q = deque()
    q.append((n, 0))

    while q:
        num, steps = q.popleft()
        if num < 10:
            continue

        if num % 25 == 0:
            return steps

        num_s: str = str(num)
        for i in range(len(num_s)):
            q.append((int(num_s[:i] + num_s[i + 1 :]), steps + 1))


for _ in range(int(input())):
    n = int(input())
    print(bfs(n))

Because 100 = 25 * 4, we can focus on suffix which creates numbers divisible by 25 (00, 25, 50, 75).

For example, 32925 = 329 * 100 (25 * 4) + 25 -> divisible by 25

You can see the 329 part is irrelevant.

My solution is dirty. I'll check the editorial tomorrow as it's getting too late here.

def min_steps(n: int) -> int:
    n_str: str = str(n)
    len_n: int = len(n_str)

    res = len_n

    # *00
    i0 = -1
    i = len_n - 1
    while i >= 0:
        if n_str[i] == "0":
            if i0 > 0:
                res = min(res, len_n - i - 2)
            else:
                i0 = i
        i -= 1

    # *25
    i5 = -1
    i2 = -1
    i = len_n - 1
    while i >= 0:
        if n_str[i] == "5":
            i5 = i
        elif n_str[i] == "2" and i5 > 0:
            res = min(res, len_n - i - 2)
            break
        i -= 1

    # *50
    i0 = -1
    i5 = -1
    i = len_n - 1
    while i >= 0:
        if n_str[i] == "0":
            i0 = i
        elif n_str[i] == "5" and i0 > 0:
            res = min(res, len_n - i - 2)
            break
        i -= 1

    # *75
    i5 = -1
    i7 = -1
    i = len_n - 1
    while i >= 0:
        if n_str[i] == "5":
            i5 = i
        elif n_str[i] == "7" and i5 > 0:
            res = min(res, len_n - i - 2)
            break
        i -= 1

    return res


for _ in range(int(input())):
    n = int(input())
    print(min_steps(n))

Smootie 300 Bubble tea 400

Total 700 kcal

TODO:

index 20240608 20240610