ARC115

Where there is a discrepancy between the answers for Si and Sj $S_{i} \oplus S_{j}$ .
If the discrepancies are even, the number of correct answers may match, if they are odd, there is no possibility.
So for each digit we can take xor and see if it is 1: $⨁ (S_{i} \oplus S_{j})$
where xor is an operation that satisfies associative law, so the order can be changed: $⨁ (S_{i}) \oplus ⨁ (S_{j})$
This still loops for i and j, so it would take 10^10 calculations.
- What to do with this?
  - →Typical approach frequency table.
    - A technique that can be used when the value type K is much less than N
    - $O (N)$ Pay to get the number of pieces of each type first
    - Then the computation of the same value combination can be performed together, so $O (N^{2}) \to O (K^{2})$ .
- This time K=2
- Pay $O (N)$ and find the number x of those for which $⨁ (S_{i})$ is 1 first
  - $\sum_{ij} (⨁ S_{i} \oplus ⨁ S_{j}) = x^{2} (1 \oplus 1) + x (N - x) (1 \oplus 0) + (N - x) x (0 \oplus 1) + (N - x)^{2} (0 \oplus 0) = 2 x (N - x)$
  - This does not distinguish between large and small i and j, so the answer can be obtained by making Half of the queue. python

def main():
    N, M = map(int, input().split())
    s1 = 0
    for i in range(N):
        S = input().strip()
        s = S.count(b"1")
        if s % 2:
            s1 += 1
    print(s1 * (N - s1))

B - Plus Matrix

If there exist A, B satisfying the condition $R_{j} = \sum_{i} C_{ij} = \sum_{i} A_{i} + N B_{j}$
$min (R_{j}) = \sum_{i} A_{i} + N min (B_{j})$ , but can be set as [$ \min(B_j) = 0
- $min (B_{j}) = m > 0$ , since subtracting m from all Bs and adding m to all As does not change the result
So $min (R_{j}) = \sum_{i} A_{i}$ , so $B_{j} = (R_{j} - min (R_{j})) / N$ , $A_{i} = C_{i 1} - B_{1}$
Find C again with the obtained A and B, and check if it is constructed correctly. python

def solve(N, CS):
    sums = [sum(row) for row in CS]
    m = min(sums)
    if any((x - m) % N for x in sums):
        return ()

    AS = [(x - m) // N for x in sums]
    BS = [x - AS[0] for x in CS[0]]
    if any(x < 0 for x in BS):
        return ()
    NCS = [tuple(AS[i] + BS[j] for j in range(N)) for i in range(N)]
    if NCS != CS:
        return ()
    return (AS, BS)

C - ℕ Coloring

Think small first.
- When you draw this far, you realize, “Oh, the number of prime factors.
proof
- Items with K prime factors cannot be divisors of each other.
  - So you can paint them the same color.
- Those with K prime factors always have at least one divisor with prime factors less than K.
  - So it has to be a different color than those python

def main():
    N = int(input())
    ret = []
    for i in range(1, N + 1):
        f = get_factors(i)
        x = sum(f.values()) + 1
        ret.append(x)
    print(*ret)

D - Odd Degree

I looked at it for a while and thought, “I guess I need to find the connected components,” but I didn’t know where to go from there, so I first created a code to solve it with a full search. python

def blute(N,M,edges,edgelist):
    ret = [0] * (N + 1)
    for i in range(2 ** M):
        deg = [0] * N
        for j in range(M):
            if i & (1 << j):
                a, b = edgelist[j]
                deg[a] += 1
                deg[b] += 1
        r = sum(x % 2 for x in deg)
        ret[r] += 1
    return ret

What we learned from observation
- If not linked, find each and fold
mounting
- Count the number of vertices and edges of connected components with UnionFind
- Create and set up an inverse/factorial table and calculate for each connected component
- Fold each of them in.
Result TLE
Post-Contest AC
- Cause of TLE: Using FFT library to compute convolution
  - If you folded in a rustic loop, it was AC. py

def solve(N,M,edges,edgelist):
    init_unionfind(N)
    for x, y in edgelist:
        unite(x, y)
    comps = []
    for x in range(N):
        if find_root(x) == x:
            comps.append((num_edges[x], num_vertex[x]))

    MOD = 998_244_353
    comb = CombinationTable(N + 10, MOD).comb

    ret = None
    for e, v in comps:
        xs = [0] * (v + 1)
        xs[0] = 1
        for i in range(1, (v // 2) + 1):
            xs[i * 2] = comb(v, 2 * i)
        if e > v - 1:
            m = pow(2, e - (v - 1), MOD)
            xs = [x * m % MOD for x in xs]
        if ret is None:
            ret = xs
        else:
            ys = ret
            ret = [0] * (len(xs) + len(ys) - 1)
            for i in range(len(xs)):
                for j in range(len(ys)):
                    ret[i + j] += xs[i] * ys[j]
                    ret[i + j] %= MOD
    return ret

This page is auto-translated from /nishio/ARC115 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

ARC115

Graph View

Backlinks