I solved several ABC problems but forgot to record them in my blog. I’ll write them all together here.

ABC #136 D - Gathering Children

Once you enter an RL pair, you can’t escape. Move an even distance and attach to the RL pair.

ABC #136 E - Max GCD

Sort first, bring small values closer to 0, and bring large values closer to the answer $d$. Calculate the cumulative sum from both forward and backward directions.

ABC #136 F - Enclosed Points

The number of rectangles containing a certain point $x$ can be calculated based on how many points are selected from each of the four regions above, below, left, and right. Let $A, B, C, D$ be the number of points contained in each region.

  • When point $x$ is not included, consider 16 cases by whether to take points from each region
  • When point $x$ is included, simply $ABCD$

Use plane sweep to calculate the number of points for each region. Also, coordinates need to be compressed in advance.

ABC #137 D - Summer Vacation

Since all part-time jobs finish in one day, the cost doesn’t change, only the payment date differs. Look at the jobs in descending order of reward and fill in from the latest possible date.

ABC #137 E - Coins Respawn

First, use DFS to find the set $S$ of vertices reachable from both the start and end points. Then multiply the cost by $-1$ and apply the Bellman-Ford algorithm to find the longest path. If a vertex in set $S$ is included in a cycle, return $-1$. Note that simply finding a cycle with the Bellman-Ford algorithm is insufficient.

ABC #137 F - Polynomial Construction

Use Fermat’s Little Theorem. I think it’s a common technique, so I want to review it. Consider $a’ = {0,0,..,1,…,0}$ where the $i$-th element of $a = {0,0,…,0}$ is set to 1. Then $f$ using $a$ and $f’$ using $a’$ have the following relationship. This should be calculated for all $i$ where 1 is set.

$$ f’(x) = f(x) + (1- (x-i)^{P-1}) $$

By Fermat’s Little Theorem, $(1-(x-i)^{P-1})$ becomes 1 only when $x=i$. Under modulo P, the following holds:

$$ x^{P-1}= \begin{cases} 0 & (x = 0) \ 1 & (x \neq 0) \end{cases} $$

ABC #138 D - Ki

Add to the counter $x$ of each node, then update the counter from the root to the leaves with DFS (or BFS) like a cumulative sum.

ABC #138 E - Strings of Impurity

Consider a string $s’$ that is an infinite concatenation of string $s$. Look at each character of $t$ from the front, and calculate where that character appears in $s$ using DP.

ABC #138 F - Coincidenc

I solved it using the same method as the YouTube explanation video. The conditions are $L \leq X \leq Y \leq R$ and $Y % X = Y \oplus X$. First, consider cases:

    1. When $X = Y$
    • $Y % X = Y \oplus X = 0$ so OK
    1. When $X < Y$
    • 2A) $X$ and $Y$ have the same number of digits in binary
      • $Y \oplus X = Y+X-2(Y&X)$
      • $Y%X = Y-X$ (because $X<Y<2X$, so $Y/X=1$)
      • That is, $X = X \oplus Y$
      • At some digit, if $X=1$ and $Y=0$ it’s NG (the other 3 cases are OK)
    • 2B) $X$ and $Y$ have different number of digits in binary
      • NG ($Y%X$ starts with 1, MOD starts with 0)
    1. When $X > Y$
    • Not subject to the problem, no need to consider

After that, fill in the digit DP dp[i][j][k][s].

  • When looking up to the i-th digit from the top
  • j is whether X>=L is confirmed
  • k is whether Y<=R is confirmed
  • s is whether the leading bit has already appeared