arc065_b: Connectivity

Do a flood fill on road to decide which city goes to which component, and then flood fill again on rail roads, but add the edge only if the two nodes are in the same components

Official solution handles a and b separately, and test of (a,b) are the same!!!

agc008_b: Contiguous Repainting

The final form must have a continons block of black or white of length >= K.

So we just try all i, and candidates are positives in [0, i), [i+k, n], max(sum[i, i+k), 0))

agc008_c: Tetromino Tiling

Note that only I, O, J, L matters. if I is odd, and give that extra to a J, L combo. Note official solution needs to try the number of I + J + L patterns!!!

agc010_b: Boxes

We can caluate exactly how many ops we performed O. if a2 - a1 = O, we know that no ops NOT in a1. Conversely, suppose we have O1 opes on a1, then the a2 - a1 = -O1 * (n-1) + O - O1,i.e., we can infer how many ops are on a1 .

Note:

  1. the formula suggests that k - d(i) = n * x => we need to check the dividability here.

  2. that sum of d(i)s is 0 => sum of (k - d(i))/n = k

agc011_b: Colorful Creatures

sort the value, for each i, check if there is an iterm s.t., a(j) > 2 * ps(i)

agc005_b: Minimum Sum

maintain next[i], prev[i], the index of next and previous unseen index, at i

We iterate value from n to 1, use the reverse index to update next and prev

Official solution uses a set to to get the adjacent numbers to the set.

agc005_c: Tree Restoring

Given the input, we know the diameter of the tree.

Assume D is even, we also know the min value must exactly D/2, and there is only one such point. so we just build the two legs of length D/2, each, and then, given each remaining d(i), directly attaches to a node with max distance d(i) - 1

Official answer uses a mutli-set

agc006_b: Median Pyramid Easy

Possible as long as the value is not 1 or N - 1!!!

Note that if we have two adjecent cells, the value will preserve all along the way, until the top. So we can use this to construct the bottom easily

agc007_b: Construct Sequences

A crazy construction!!! a(i) = 30000 * i b(i) = 30000 * (n - i) + inverse(i)

agc001_b: Mysterious Light

Base case x = y, ans = 3 * y

if x > y, ans = x + y + x + ans (y- x, x). similarly x LT y.

Note to improve the performance, we need to do something like the euclidian algorithm, when a LT b

f(a, b) = 2 * constant * floor(b/a) + f(a, b % a)

i.e., skipping the many expanding steps!!!

An even simpler solution is 3 (N - gcd(N, X))

agc001_c : Shorten Diameter

The key insight is the the properties of diameter!!!

  1. If d is even, then there exist a point s.t. all distances from v LTE d/2

  2. if d is odd, then there exists an edge, s.t., all distances from either end of edge LTE (d-1)/2

We just try all V/E’s and find the maximal graph that satifies this condition

arc058_b: Iroha and a Grid

Note that H, W LTE 100K.

ways(1,1) -> (H, W) = ways(1,1) -> (i, B + 1) * ways(i, B + 1) -> (H, W), for all i in [1…A)

First part is choose(i + B, i), second part is choose(H-i + W-B, H-i). Note that official solution uses (H-A + 1, j) instead

agc002_b: Box and Ball

We need to maintain

  1. cnt for each box

  2. at current step, possible for for it to have red ball

  3. red ball poitions we have visited

for each move, we mark the next one as possible if cnt[i] > 0 && possible[i]. When cnt[i] = 0, possible[i] becomes false

agc002_c: Knot Puzzle

Consider the last knot we untie, as long as l(i) + l(i+1) > L, we can find a solution. My original guess was too restricted!!! The construction is trivial given this insight.

agc003_b: Simplified mahjong

Claim: for each continous block of cards, we can make floor(S/2) cards!!! Proof: we list all S cards, and sort them, and we can see that the pair will keep going!!!

So we just scan through each continouous, non-0, subarray, and calculate sum from each side.

agc003_c: BBuBBBlesort!

Claim: answer is # of poistions at odd positions that should go even!!! Proof: we can use type 2 rearrangement to move odd should go even and even should go odd to each other, e.g., move both to the head of two spots, and then perform type 1. In the end perform type2 again

arc060_b: Digit Sum

Such number theory problem does not give too much insights, so let’s consider if we can brute force/simulation!!!

if b LTE sqrt(s), we can just do brute force conversion.

if b > sqrt(s), we know it can have only two digits, i.e.,

1. d1 * b^2 + d2 * b = n

2. d1 + d2 = s

We know that n % b = 0, i.e, we just try all b LT sqrt(n)

arc060_c: Tak and Hotels

Use two pointer/bsearch to calc, next(i) = rightmost hotel the pointer can reach, and then we can calc next(i)(2^p), the rightmost hotel to reach in 2^i days,

for each query, we can just try decreasing p from 32, the moment we have next(ai) (2^p) LTE bi, we add 2^p to the final answer, and update ai to next(ai)(2^p)

agc004_b: Colorful Slimes

Suppose we did K shifts in total, then we know that the cost to acquire a(i) >= min {a(i-1)…..a(i-k)}, overall cost >= sum over cost(i) + K * x

Claim: this lowerbound is reachable all the time!!!

Proof: if a(i) is the min value for only entry, we acquire it upfront. Otherwise, suppose it is also the init entry for a(j), and a(k), j LT k, then we can acquire, and then shift, and acquire again

Then we just need to iterate on K, can improve by DP on cost(i), as it is non-decreasing and K improves

arc061_c: Snuke’s Subway Trip

The hard part is how to construct the graph!!!

We construct the node (station, last visit comompnay), because the new node can only be generated by an edge, so the new node # LTE number of edges.

For each edge (u,v) operated by company c, we connect (u, c) to (v, c), with cost 0, we also connect each node to (v, -1) with cost 1, representing leaving and entering the gate, with cost 1.

Final answer is shortest distance from (1, -1), to (N, -1) divided by 2.