20250103

Today is too productive. I wonder if I will burn out soon (though I have no idea how to rest).

Designing Data-Intensive Applications: Chapter 5 - Replication

(It’s a bit embarrassing that I don’t have any experience managing big (large amount of) data. Because of the lack of hands-on exposure, the content of this book feels unfamiliar to me. Still, skimming it should be helpful in the future, providing me with some starting points for tackling data storage challenges.)

Replication is a technique to replicate data across multiple machines to place data closer to users geographically, have some tolerance for server down, and scale out the number of machines that serve for read requests.

These are the main approaches for replication that the author mentions in this chapter.

When replication happens asynchronously, a client may read outdated data from an asynchronous follower. However, asynchronous followers should catch up with their leader at some point, and the effect is called eventual consistency.

Guarantees in leader-based replication

2048A. Kevin and Combination Lock - 800

If x is divisible by 33, it can be reduced to 0 by repeating x = x - 33.

If x is not divisible by 33, we can simply iterate str(x), remove 33, and recursively apply the check. At first, we have 8 positions to check for 33, and in the next iteration, we have 6 positions as we removed 33 somewhere. Roughly speaking, we will check 8 * 6 * 4 * 2 = 384 positions at most, and its time complexity is not a problem here.

def solve(x: int) -> bool:
    if x % 33 == 0:
        return True

    x_str: str = str(x)
    for i in range(len(x_str) - 1):
        if x_str[i : i + 2] == "33" and solve(int(x_str[:i] + x_str[i + 2 :])):
            return True

    return False


for _ in range(int(input())):
    x: int = int(input())
    if solve(x):
        print("YES")
    else:
        print("NO")

2048B. Kevin and Permutation - 900

The idea is to distribute minimum values evenly with k intervals. We put 1 in the middle instead of the beginning to maximize the number of subarrays that have 1 as their minimum value.

for _ in range(int(input())):
    n, k = map(int, input().split())

    ans: list[int] = []
    cnt: int = 1
    for i in range(n):
        if (i + 1) % k == 0:
            ans.append((i + 1) // k)
        else:
            ans.append(cnt + n // k)
            cnt += 1

    print(" ".join([str(x) for x in ans]))

2048C. Kevin and Binary Strings - 1200

Let’s call the larger substring of s a and the smaller one b. When s consists of only 1s, XOR of any (a, b) is smaller than a.

111 xor 001 = 110 < 111

if 0 in s, there is at least one pair of (a, b) whose XOR is larger than a.

100 xor 010 = 110 > 100

To maximize the XOR, we should pick s as a and b to turn the leftmost 0 in a into 1. There may be several subarrays to achieve it, and we just need to check all possibilities.

for _ in range(int(input())):
    s: str = input()

    sb: int = int(s, 2)
    i0: int = s.find("0")

    if i0 == -1:
        print(f"1 {len(s)} 1 1")
        continue

    sublen: int = len(s) - i0
    max_res: int = -1
    max_i: -1
    for i in range(i0):
        subs: int = int(s[i : i + sublen], 2)
        if sb ^ subs > max_res:
            max_res = sb ^ subs
            max_i = i

    print(f"1 {len(s)} {max_i + 1} {max_i + sublen}")

_ lb

lat pulldown, bench press, 30 minutes run, 60 minutes walk


TODO:


index 20250102 20250104