ARC106

I was almost worried about C, but after my previous experience, I realized that I should read all the questions first, so I read D. D is just an equation transformation and easy for me, so I solved that one first and went back to C. C is able to generate output that looks correct, but only 2 cases were WA and I didn’t get them in time. I was not able to solve it in time.

Yay, it’s light blue!

• I was slammed in the last 10 minutes or so. I got through D in less than 40 minutes and had 45 minutes left, but I couldn’t get the bug out and C didn’t go through. Well, I guess I made progress in that I was able to make the decision to do D first.

A - 106

• 
• Thoughts.
  • How many possible values of A and B are actually there since they are of logarithmic order?
  • Counting 3^A less than 10^18 → 37
  • Then we can afford to do the whole search. python

 def solve(N):
     P3 = [3, 9, 27, 81, ...]
     P5 = [5, 25, 125, 625, ...]
     for i, x in enumerate(P3):
         for j, y in enumerate(P5):
             if x + y == N:
                 print(i + 1, j + 1)
                 return
     print(-1)

• I printed 3^A instead of A. 1WA

B - Values

• 
• Thoughts.
  • Can move values through paths
  • OK if the sum of the contents of the connected components are the same.
  • Find the connected components by UnionFind, and find the sum of A and B for each connected component. python

def solve(N, M, AS, BS, CD):
    init_unionfind(N)
    for (c, d) in CD:
        unite(c - 1, d - 1)

    sumA = defaultdict(int)
    sumB = defaultdict(int)
    for v in range(N):
        root = find_root(v)
        sumA[root] += AS[v]
        sumB[root] += BS[v]

    for k in sumA:
        if sumA[k] != sumB[k]:
            return "No"
    return "Yes"

I looked at C for a while and made concrete examples by hand, but I couldn’t see the path, so I decided to read other problems. d seemed easier, so I decided to solve D.

D - Powers

• 
• Thoughts. - Half of the queue :
  • ${\sum }_{i=1}^{N-1}{\sum }_{j=i+1}^N{A}_{ij}=({\sum }_{ij}{A}_{ij}-{\sum }_i{A}_{ii})/2$
  • N is 10^5, which is too large to process to the order of squares, which means One row at a time processing may be possible.
  • Consider fixing j
  • ${\sum }_i(S+A_i{)}^X$
    • binomial theorem :
  • $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$
  • ${\sum }_i(S+A_i{)}^X={\sum }_i\left(S^X+\left(\genfrac{}{}{0ex}{}{X}{1}\right)S^{X-1}{A}_i^1+\dots \right)$
    • Change the order of addition
    • If we do the addition of the inside out, it’s going to be in the form ${\sum }_i{A}_i^k$.
    • This can be calculated in linear order, so it’s pre-processed to speed up the process.
    • The S’s are going to be clean too.
  • Reorganize again
    • ${\sum }_{L=1}^{N-1}{\sum }_{R=L+1}^N(A_L+A_R{)}^X=\left({\sum }_L{\sum }_R(A_L+A_R{)}^X-{\sum }_i(2A_i{)}^X\right)/2$ … Half of the queue
    • ${\sum }_L{\sum }_R(A_L+A_R{)}^X={\sum }_L{\sum }_R{\sum }_i(\genfrac{}{}{0ex}{}{X}{i})A_L^{X-i}{A}_R^i$ … binomial theorem
    • $={\sum }_i\left(\left(\genfrac{}{}{0ex}{}{X}{i}\right){\sum }_L{A}_L^{X-i}{\sum }_R{A}_R^i\right)$… Change the order of addition 　 Exchange of product and sum
    • If we pre-calculate $f(k)={\sum }_i{A}_i^k$, we get [$ \sum_i \binom{X}{i} f(X-i) f(i)
• mounting
  • I’m going to write it down plainly.
    • Multiply by Inverse Element in mod P where P is divided by 2
    • Combination calculation is Combination in mod P.
    • Two TLEs were careless mistakes in the pre-treatment part.
      • I was doing a ** x at first, and before I got to the remainder, the digit exploded, 15 TLE.
      • Next I tried pow(a, x, MOD), but it was 9 TLE, I had my head in the sand for a while.
      • The above is of logarithmic order, and if you use the past results instead of multiplying by a power each time, it will be of constant order. python

def solve(N, K, AS):
    MOD = 998_244_353
    div2 = pow(2, MOD - 2, MOD)
    sumTable = [N] * (K + 2)
    ps = AS[:]
    for x in range(1, K + 1):
        s = 0
        for i in range(N):
            s += ps[i]
            s %= MOD
            ps[i] *= AS[i]
            ps[i] %= MOD
        sumTable[x] = s

    c = Comb(K + 1, MOD)
    for x in range(1, K + 1):
        ret = 0
        for i in range(x + 1):
            ret += c.comb(x, i) * sumTable[x - i] * sumTable[i]
            ret %= MOD
        p = pow(2, x, MOD)
        ret -= sumTable[x] * p
        ret %= MOD
        ret *= div2
        ret %= MOD
        print(ret)

C - Solutions

• 
• I’ll implement it honestly first, hit the random input and observe. python

def aoki(LR):
    selected = []
    for lr1 in sorted(LR):
        if not any(is_p(lr1, lr2) for lr2 in selected):
            selected.append(lr1)
    return len(selected)


def takahashi(LR):
    from operator import itemgetter
    selected = []
    for lr1 in sorted(LR, key=itemgetter(1)):
        if not any(is_p(lr1, lr2) for lr2 in selected):
            selected.append(lr1)
    return len(selected)


def random_test():
    from random import seed, randint
    for s in range(1000):
        seed(s)
        LR = []
        for i in range(5):
            W = 20
            l = randint(0, W - 1)
            r = randint(l + 1, W)
            LR.append((l, r))
        t = takahashi(LR)
        a = aoki(LR)
        if t != a:
            print(s, LR, t, a)

• observation

  • M is unlikely to be negative.

  • Up to $\lceil N/2\rceil$? (not true)

  • I’d say the top is up to $N-2$! (PS: it’s not)

  • I saw something like Figure A in the observations, so I decided to generate something like B. Oh, I see.

    • I forgot how to put in the missing part, so I corrected it to C.

  • 

  • We’ll call the big one a wrap, the finely wrapped one a child, and the last one in line a tail.

    • Sorting by L
      • The wrappings come first, so the wrapped child is eliminated.
      • Tails are also eliminated.
      • →1
    • Sorting by R, children are processed first.
      • M number of children
      • The first of the tails will also be added
      • →M+1 throughout
    • I thought this would accomplish m
      • I assumed M was up to N - 2.
      • I thought M could be N - 1. I realized that and loosened the constraint, but when N - 1, there is no tail, so “the first of the tails is added and +1” doesn’t happen, so this algorithm can’t generate the correct data.
      • Contest time ran out here.
• Official Explanation
  • M is not N-1.
    • except for the case where N=1
  • My WA was an oversight there too.
    • 
  • I stopped returning -1 when N-1, and as a result N1M0 now passes, but other M=N-1 tests do not pass because the above algorithm produces incorrect results.
    • 
• points worthy of special consideration
  • I was totally freaking out with about 10 minutes left.
  • When I looked at the problem conditions, the fact that N was from 1 stuck in my mind for a moment, but I didn’t go through with it.
    • It was an obvious trap to have only one object present when discussing the intersection of intervals.
      • Boundary Value Test
• The original was Interval Scheduling, and they knew the Takahashi solution was optimal if they knew it.

---

This page is auto-translated from /nishio/ARC106 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.