day1

jail

1. It can be proved that if the answer is Yes, we always have a construction in which each prisoner take consecutive moves.
   Tips: if 2 moves by one prisoner is not consecutive, let it be \(u \rightarrow w\) and \(w \rightarrow v\). No moves via \(w\) can be made between the 2 moves.
   By moving all moves via \(v\) in the interval before \(u \rightarrow w\) and all moves via \(u\) after \(w \rightarrow v\), the construction should remain valid.
   
2. The problem now reduced to report if a topo order of prisoners exiets.
   
3. Reduce the edges to \(O(n\log n)\) by binary lifting.

kyoto

1. in a 2x2 grid, if \(A_2-A_1\lt B_2 - B_1\), we will never turn right at \((1,2)\).
   
2. get the difference array of \(A\) and \(B\).
   
3. observation: assume \(A_j - A_{j-1}\) is the maximum of all differences, we will never turn left at \((j,*)\), we simply delete road \(A_j\).
   
4. with several road deleted we write the difference as \(\frac{A_i - A_{\mathrm{prev}(i)}}{i-\mathrm{prev}(i)}\) and the observation still works.

misspelling

1. observation \[ T_A = T_B \iff S_A=S_{A+1} \dots = S_B\ (A\lt B) \] \[ \text{let}\ x\ \text{be the first index between }[A, B] \text{ where } S_x \neq S_{x+1}. \] \[ T_A \lt T_B \iff \begin{cases} S_x \lt S_{x+1} & A \gt B\\ S_x \gt S_{x+1} & A \lt B \end{cases} \]
2. let \(dp[n][c] = \#[S_{n-1} \neq S_n \land S_n = c]\)
   
3. optimize it.

day2

copypaste3

1. write an interval DP.
   
2. system test passed...
   
3. actually, count of all possible Operation B & C combo is \(O(n^2\ln n)\).

team

Elementary 3D partial order practice.
Can be implemented in \(O(n\log n)\) time though.

day3

sprinkler

1. \(D_i \le 40\), wow!
   
2. sadly \(L\) is not a prime, if we implement an inclusion-exclution principle + BIT, it would be \(O(N \log D \log maxA)\).
   
3. why not design a tiling strategy that eliminates 2 logs in one go?
   
4. \(O(ND)\).

sugar

1. render this as a bipartite matching problem. review Hall's marriage theorem (quantitative version).
   
2. \(Ans = \sum ants + \min_{S \subseteq Ants}|\mathrm{Adj}(S)| - |S|\), where \(\mathrm{Adj}(S)\) is all sugar reachable from ants in \(S\).
   
3. subtask2: the matching has strong locality (choose of ant only affect adjacent sugars). This can be easily maintained by a segment tree.
   
4. observation: assume sugar in \(|\mathrm{Adj}(S)|\), that can be reached by ants in interval \([l, r]\), if \(\exists s, t \in S\cap [l, r]\), if we just include all ants in interval \([s, t]\), the answer will only be lesser. which implies the optimal choose of \(S\) has all its element form a substring in all it's adjacent sugars.
   
5. with this observation, we can apply the inclusion-exclution principle: for each sugar, let any \(x\in [l, r], x \in S\) have \(+1\) contribution, and any \(x \in [l, r-1], x, x+1 \in S\) have \(-1\) contribution. And once again, we have strong locality guaranteed.
   
6. How to handle the insertion of sugar?
   1. for a whole node in segment tree, the answer will always increase by number of sugar inserted.
      
   2. to handle the gap between nodes, we can record for each node, sugars that affect the gap between it's two childrens.

day4

dango3

devide and conquer. ### fish2

reconstruction

Deficiency of Bipartite Graph

\[ \text{let}\ G = (X + Y, E) \\ \mathrm{def}(G;X) = \max_{S\subseteq X} |S| - |\mathrm{Adj}(S)| \]

since \(S\) can be \(\emptyset\), \(\mathrm{def}(G;X)\ge 0\).

extended Hall's Theorem

Every bipartite graph \(G = (X+Y, E)\) admits a matching in which at most \(def(G;X)\) vertices of \(X\) are unmatched. (from Wikipedia).

Example

JOISC 2022 day3, sugar

\[ v_p(n!)=\sum_{k\ge1}\lfloor\frac{n}{p^k}\rfloor=\frac{n-\mathrm{sum\_of\_digits}(n)}{p-1} \]

thus

\[ v_p(\binom {n+m}m) = \#\text{lifting in p-ary addition n + m.} \] 3

上下都有限制的折线法: 可以反复映射,做到\(O(n+m/(a+b))\)的复杂度.2

切比雪夫距离与曼哈顿距离转化

区间DP套数位DP, WTF? 数位DP, 但上下界不独立: 记录0/1/2表示顶上界/下界/自由选择

多想想极限情况,最后再想推广

二维fft

对每一行+列做1Dfft

f(x+c)

卷积

\(\left [ m \atop n \right]\)

倍增+位移

多项式除法

\(\sum_{k=r}^n (-1)^k\binom{n}{k}^{-1}\binom{k}{r}\)

AtCoder Regular Contest 136

B - Triple Shift

In this construction, parity of the inversion number is an inveriant. ## C - Circular Addition cyclic difference.

E - Non-coprime DAG

DON'T resort to flows, math is the way to go!

try analyze what it means to be connected.

Base on the fact that every pair of even number are connected, and the distance to any number connected to \(x\) is always greater than \(\mathrm{lpf}(x)\). a simple casework reveals the exact constraint.

F - Flip Cells

PGF magic.

Assume the process never ends, let \(F(z)\) be the PGF formoving from initial state to a valid end state, and \(G(z)\) be the PGF for moving from a valid end state to another(note how the initial state is irrelavent here).

We have: \[E(z)G(z)=F(z)\]

where \(E(z)\) is the PGF of the game.

The answer is just \(E'(1)\).

details

derive \(F(z)\) and \(G(z)\)

we first calculate the exponential PGF of \(F\) and \(G\), then wirte them as the sum of a bunch of \(\exp\). Finally substitute \(\exp\) for \(\frac1{1-z}\) to get the ordinary PGF.