image

A - Two Choices

  • image
  • Where there is a discrepancy between the answers for Si and Sj .
  • 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:
  • where xor is an operation that satisfies associative law, so the order can be changed:
  • 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
        • Pay to get the number of pieces of each type first
        • Then the computation of the same value combination can be performed together, so .
    • This time K=2
    • Pay and find the number x of those for which is 1 first
      • 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

  • image
  • If there exist A, B satisfying the condition
  • , but can be set as [$ \min(B_j) = 0
    • , since subtracting m from all Bs and adding m to all As does not change the result
  • So , so ,
  • 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

  • image
  • Think small first.
    • image
    • 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

  • image
  • 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
    • image
    • image
    • 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.