20240729

back to work

1996C. Sort

I remember that when sorted strings are the same, the occurrences of characters are the same.

What I overlooked was

It is guaranteed a only contains lowercase latin letters. It is guaranteed b only contains lowercase latin letters.

The number of lowercase latin latters is finite (= 26), and we can afford to store extra in memory or run for loops.

The idea is to have prefix-sum array of the occurrences. For each index, we will have two lists of length = 26; one for a and the other for b.

import string


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

    asumarr: list[list[int]] = [[0] * 26 for _ in range(n + 1)]
    bsumarr: list[list[int]] = [[0] * 26 for _ in range(n + 1)]

    a: list[str] = list(input())
    b: list[str] = list(input())

    for i in range(1, n + 1):
        ai: int = string.ascii_lowercase.find(a[i - 1])
        bi: int = string.ascii_lowercase.find(b[i - 1])

        for j in range(26):
            asumarr[i][j] = asumarr[i - 1][j]
            if j == ai:
                asumarr[i][j] += 1
            bsumarr[i][j] = bsumarr[i - 1][j]
            if j == bi:
                bsumarr[i][j] += 1

    anss: list[int] = []
    for qc in range(q):
        ans: int = 0
        l, r = map(int, input().split())
        for i in range(26):
            aran: int = asumarr[r][i] - asumarr[l - 1][i]
            bran: int = bsumarr[r][i] - bsumarr[l - 1][i]
            ans += max(bran - aran, 0)
        anss.append(ans)

    for ans in anss:
        print(ans)

Ketone not measured 15 mg/dl

Roasted seaweed snacks 5g Sushi Salad 20g Macadamia nuts 20g Cheese 5g

Total carbohydrate 50 g

push ups 2k run

MUST:

• Review Codeforces Round 962 D (by this friday)

TODO:

• Update my resume with the sign up feature
• Update my resume with the document structure and AWS S3
• Update my LinkedIn summary section
• Consider the microservice independency with Redis/RabbitMQ
• Clean my keyboard

index 20240728 20240730