ABC179

D was difficult, so I solved E first, then went back and solved it and got 5 questions correct.

C - A x B + C

• 

• The problem of counting the number of solutions that exist on a skipped basis.

• Tends to be buggy with rounding up and down.

  • At first, I changed N - 1 to N - A + 1.
    • If A==2, it would be.
  • (3, 1, 7), (3, 2, 4), (3, 3, 1) when A=3, N=10
  • (3, 1, 6), (3, 2, 3) for A=3, N=9
  • From this we know that (N - 1) // A. python

def solve(N):
    ret = N - 1
    for i in range(2, N + 1):
        ret += (N - 1) // i
    return ret

ABC179D E - Sequence Sum

• 

  • loop detection
  • The reason I'm so tied to variables is because I debugged with print.
    • Bug: loop_start was off by 1 and loop_tail was taken from the end.
  • Finding the start of the loop is O(1)
    • If visited is 0, it has not appeared, and if it is non-zero, it is the position at which it first appeared + 1.

python

def solve(N, X, M):
    visited = [0] * M
    a = X
    ret = []
    for i in range(N):
        if visited[a]:
            s = sum(ret)
            loop_start = visited[a] - 1
            loop_end = i
            loop_sum = sum(ret[loop_start:loop_end])
            loop_length = loop_end - loop_start
            loop_count = (N - i) // loop_length
            loop_left = (N - i) % loop_length
            loop_tail = sum(ret[loop_start:loop_start + loop_left])
            return s + loop_count * loop_sum + loop_tail
        ret.append(a)
        visited[a] = (i + 1)
        a = (a * a) % M

    return sum(ret)

• I saw on Twitter that some people solved it with doubling?

F - Simplified Reversi

• 
• Since it is a range update and point acquisition, dual segment tree is fine.
  • But I had not yet organized my own code only for the relative segment tree...
  • I was in a hurry because I had 10 minutes left.
• There is also the possibility of bisecting the point at which the value changes.
  • But Python's bisect requires a sorted array.
  • That's not good, because this problem condition would cause an insertion into the array, which would be O(N).
  • Essentially, I should be prepared to immediately retrieve and use an equilibrium binary tree that can be used in Python...
  • For this problem only, "no addition to other than the beginning is necessary", so if you have it in reverse order, you get O(1) with the tail addition, but it's tricky.
• Version to hold in reverse order and search for two minutes python

def main():
    from bisect import bisect_left
    N, Q = map(int, input().split())
    ret = (N - 2) ** 2
    xs = [-N]
    xvals = [N - 2]
    ys = [-N]
    yvals = [N - 2]
    for _q in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            i = bisect_left(xs, -x)
            ret -= xvals[i - 1]
            if i == len(xs) and yvals[-1] > x - 2:
                ys.append(-xvals[i - 1] - 2)
                yvals.append(x - 2)
        else:
            y = x
            i = bisect_left(ys, -y)
            ret -= yvals[i - 1]
            if i == len(ys) and xvals[-1] > y - 2:
                xs.append(-yvals[i - 1] - 2)
                xvals.append(y - 2)

    print(ret)

• I'm not sure if dual segment tree would have been sufficient, but there are a lot of people solving this problem with a lazy segment tree, so I guess it would have been better to use a lazy segment tree.
• Related Articles
  • https://hackmd.io/@tatyam-prime/DualSegmentTree

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