20240910

I found a bug in my dashboard dashboard.huyfififi.com that my rating and contest counts are not updated correctly. I need to debug it.

First, I will trigger the background job manually and see if it raises some errors, but because I have many meetings today, I don't think I can dig it deeper now.

2008D. Sakurako’s Hobby - 1000

Because the input array is a permutation, meaning that each node has exactly one pointer to an other node. And, that means if pj is reachable from pi, they share the same F(i) (the number of black integers that are reachable from i).

My approach is to perform search for each loop and make them point to the same F(i) object. If a node is already visited, we will skip searching its result, so the time complexity is around O(n).

from typing import Optional


class Group:
    def __init__(self, bn: int = 0):
        self.black_count: int = bn


for _ in range(int(input())):
    n: int = int(input())
    p: list[int] = list(map(int, input().split()))
    b: list[bool] = [True if x == "1" else False for x in input()]

    p: list[tuple[int, bool]] = list(zip(p, b))

    ans: list[Optional[Group]] = [None] * n
    for i in range(n):
        if ans[i] is not None:
            continue

        val, blk = p[i]
        g = Group(bn=(0 if blk else 1))
        ans[i] = g

        j = val - 1
        while ans[j] is None:
            dst_val, dst_blk = p[j]
            g.black_count += 0 if dst_blk else 1
            ans[j] = g
            j = dst_val - 1

    ans = [str(g.black_count) for g in ans]
    print(" ".join(ans))

This problem is tagged as dsu, which I have never heard of before. TODO: check the editorial and what is dsu (Disjoint Set Union?)

-> 20240911: The editorial says the same thing as I mentioned above.

Codeforces Round 970 (Div. 3) Editorial

Any permutation can be divided into some number of cycles, so F(i) is equal to the number of black colored elements in the cycle where i is. So, we can write out all cycles in O(n) and memorize for each i the number of black colored elements in the cycle where it is.

Protein shake 200 Sushi bowl 800 Chicken mayo salad 600 Nori 100 Yogurt 300

Total 2000 kcal

MUST:

TODO:

index 20240909 20240911