## Task Authors and Setters

| Problem | Author | Setter |
| -------- | -------- | -------- |
| [A - Take It or Double It](#Problem-A---Take-It-or-Double-It) | Shang-En Huang | Ling-Ju Hung, Shang-En Huang |
| [B - Twin Guardians](#Problem-B---Twin-Guardians) | Jinn-Shyong Yang | Ling-Ju Hung, Shang-En Huang |
| [C - One-Way Abyss](#Problem-C---One-Way-Abyss) | Hong Yi Lin | Kuan-Lin Chen |
| [D - Palindromic Distance](#Problem-D---Palindromic-Distance) | Peter Rossmanith | Ling-Ju Hung |
| [E - Explosive Slabstones Rearrangement](#Problem-E---Explosive-Slabstones-Rearrangement) | Kai-Chun Ho | Kai-Chun Ho |
| [F - Fruitful Compression](#Problem-F---Fruitful-Compression) | Shang-En Huang, Ting-Wei Chen | Brian Tsai, Yu-Hang Sheng |
| [G - Gamer Bafuko](#Problem-G---Gamer-Bafuko) | Chungsheng Wu, Chen Shenghui | Hsuan-Yu Kuo |
| [H - Chopsticks](#Problem-H---Chopsticks) | Bo-Wei Lin, Brian Tsai | Brian Tsai |
| [I - Reactor](#Problem-I---Reactor) | Kuan-Lin Chen | Brian Tsai |
| [J - Gas Station](#Problem-J---Gas-Station) | Bo-Wei Lin | Bo-Wei Lin |
| [K - Move Stone](#Problem-K---Move-Stone) | Tsung-Ta Wu | Wang-Yang Li, Tsung-Ta Wu |
| [L - Stapler](#Problem-L---Stapler) | Wang-Yang Li | Ke-Wei Huang |

## Problem A - Take It or Double It

判斷是否 $2X \le D$，如果是就輸出 `double it`，否則輸出 `take it`。

## Problem B - Twin Guardians

對於輸入的兩個數字 $a$ 與 $b$，分別檢查兩個數字是否為質數、以及兩數是否滿足 $b = a+2$。判斷質數的時候可以使用試除法，但要小心不能把 $1$ 判斷成質數。

## Problem C - One-Way Abyss

在每一層深度至多只有一個水平隧道，且每個隧道連接兩個豎井。由此，我們可以做出以下觀察：

如果某一層深度只有一條水平隧道，我們可以「移除」這條隧道，並透過「交換兩個豎井的 index」，再將寶藏價值分配給兩者來完成計算。

透過從上到下套用此過程並移除所有的水平隧道，這樣我們可以追蹤每個起點的最終目的地和可以獲得的寶藏價值。答案就是這些之中最大值。

## Problem D - Palindromic Distance

由於字串可以長得相當複雜使最少操作數很難想像，不妨嘗試將字串慢慢進行簡化。

一個很長的字串 $S$ 會有兩種情況，開頭與結尾的字元相同或是不同。在相同的情況下我們可以無視開頭與結尾的字元，將 $S$ 進行簡化，但若是不同的情況，我們可以透過嘗試枚舉各種操作來簡化字串，並繼續計算每種簡化操作後剩餘字串的最小操作數：

+ 在結尾加入一個與開頭相符的字元
+ 在開頭加入一個與結尾相符的字元
+ 將開頭的字元換成與結尾相同的字元

這裡可以發現到，刪除開頭或是結尾的字元以及將結尾的字元換成與開頭相同的字元，這些操作所簡化出來的字串都分別與上面三種簡化操作後所需計算的剩餘字串一致，所以可以省略。

而經過上面的觀察，我們會發現每次都暴力向下計算剩餘字串的最小操作數是相當沒有效率的，因為過程中總是在計算相同的剩餘字串，也就是 $S$ 的子字串，所以我們以透過動態規劃來將每個 $S$ 的子字串記錄下來，進而防止重複計算的事情發生。

所以我們定義動態規劃的狀態 $\mathrm{dp}_{l,r}$ 會是 $S$ 在區間 $[l, r]$ 的子字串變成迴文的最小操作數，那就能得到以下式子：

+ 若 $S_l$ 與 $S_r$ 相同
$\mathrm{dp}_{l, r} = \mathrm{dp}_{l + 1, r - 1}$
+ 若 $S_l$ 與 $S_r$ 不同
$\mathrm{dp}_{l, r} = \min\{\mathrm{dp}_{l + 1, r}, \mathrm{dp}_{l, r - 1}, \mathrm{dp}_{l + 1, r - 1}\} + 1$

整體可以在 $O(n^2)$ 時間內計算完畢。

## Problem E - Explosive Slabstones Rearrangement

假設花費能量不能超過 $x$，也就是可移動的最大石板編號是 $x$。把石板全部移出矩形範圍需要滿足兩個條件：

1. 沒有編號超過 $x$ 的石板在矩形內。否則那些石板會固定在矩形內。
2. 編號超過 $x$ 的石板會把花園分成連通塊，且如果滿足條件 (1)，矩形會完整屬於某個連通塊。在矩形所在的連通塊中，矩形的大小不能超過沒有石板的格子數量。否則無論如何移動，都會有石板在矩形內。

條件 (1) 只要看矩形內的石板編號即可判斷；條件 (2) 可以用 DFS / BFS / Disjoint set 根據 $(u_1,v_1)$ 所在的連通塊的大小與空位數量來判斷。

使用二分搜尋法可以得到滿足上述兩個條件的最小 $x$，時間複雜度是 $O(nm \log k)$。需要特別注意答案是 $0, -1$ 或 $k$ 的情況。

## Problem F - Fruitful Compression

給定一個 $4\times4$ 的盤面，每一格會是 “GLMS” 其中一個英文字母，或是 “X” 代表是空的，保證給定的盤面只有一種合法排列方式將 X 填滿，一個合法的排列方式為每一行每一列一個英文字母只會出現剛好一次，接下來要從給定盤面玩一個遊戲，遊戲由兩個人參與，每個人每一回合都要拿走一個字母使得該格變成空的，拿走這個字母後，須保證這個新的牌面也僅存在一個唯一一個合法排列方式，假設兩個人都會採取最佳策略，若能贏則會採取贏的策略並希望結束時剩下的字母越少越好，若會輸則會希望結束時剩下的字母越多越好，問最後會剩下幾個字母。

這題做法為 bitmask DP

$DP[S]$ 代表當下的盤面狀況為 $S$ 時，在雙方進行這個最佳策略下的答案多少。
轉移則是當我把在 $v$ 那格的字母拿掉，先判斷 $DP[S/v]$ 的數字奇偶性跟 $|S|$ 的奇偶性是否一樣，若一樣代表會走到一個對於當下這個盤面先手會輸的盤面，反之則會贏，因為奇偶性相同代表拿走的過程中拿走數字為偶數，因此結束時先手還是先手，因此若存在一個贏的盤面，則從裡面選剩餘數最小的，反之則選數字最大的，每個盤面是否合法可以先預處理掉後用 $O(1)$ 判斷，因此這部分複雜度為 $O(2^{n^2}\times n^2)$。

而判斷一個盤面是否合法可以直接採用暴力枚舉，由每一行去暴力枚舉，第一行有 $4!$ 種，最後一行的話只會有唯一一種，因此每一個盤面的複雜度可以用 $O((n!)^{n-1} \times n^3)$ 限制住，後面 $n^3$ 為每填一格後去驗證同一行同一列使否有相同的字母，而總共只會有 $O(2^{n^2})$ 個盤面。

## Problem G - Gamer Bafuko

給定一個 $n$ 個節點的樹狀圖，樹上的每一條邊的權重是 $1$。現在加上指定兩個節點之間的一條邊 $(x,y)$，權重是 $0$。問使用這些邊，將所有節點都拜訪一次的最小路徑權重和。

這題需要考慮一些情況。

1. 如果 $(x,y)$ 是樹的其中一條邊，那我們可以把 $x$ 和 $y$ 視作同一個節點，題目就相當於問說將一棵有 $n-2$ 個節點的樹的節點都經過一次的最小路徑權重和。這是很經典的問題，可以證明只要將起點和終點選在樹直徑的兩個端點就能最小化權重和，權重和是 $2(n - 2) - d$，其中 $d$ 代表樹直徑上的邊數。
2. 若 $(x,y)$ 不是樹的其中一條邊，則將 $x$ 和 $y$ 視為同一個節點以後，會是 $n-1$ 個節點和 $n-1$ 條邊的圖，圖上會形成一個長度至少是 $2$ 的環，移除這個環以後會形成很多有根樹。如果起點和終點位於同一個有根樹裡，令 $e$ 是環上的邊數，$d$ 是起點和終點之間的距離，可以說明最小權重和是 $2(n-1) - e - d$（走法如下面示意圖）。因此只需要找到這些有根樹裡最大的直徑就能最小化權重和。
3. 如果起點和終點位於不同有根樹裡，令 $d$ 是起點和終點之間的兩條簡單路徑中較長的，可以說明最小權重和是 $2(n-2) - d$（走法如下面示意圖）。
找最大的 $d$ 有多種可能的做法，這裡示範其中一種。我們首先先找出對於每個有根樹，從根到任意節點的最長距離，記為 $a_1, a_2, \ldots, a_l$，其中 $l$ 是有根樹的數量。則可以發現 $$d = \max\left(\max_{i<j} \left(j - i + a_i + a_j\right), \max_{i>j} \left((i - 1) + (l - j) + a_i + a_j\right) \right)$$
可以發現兩種情況都可以把 $i$ 和 $j$ 的部分拆開不相關的式子，就可以使用前綴 max 算出答案。

考慮以上情況以後，取最小的答案即可。

## Problem H - Chopsticks

容易發現當我們已經決定好筷子的分佈時，沒拿到類型成對筷子的人數數量是「奇數雙筷子的種類數 / 2」。

若我們以此為依據列期望值出來，可以得到：
\begin{align*}
\mathbb{E}[\mathrm{ans}] &= \mathbb{E}\left[\frac{1}{2}\sum^{m}_{i=1}\text{number of chopsticks }i\text{ is odd}\right]\\
&=\frac{1}{2}\sum^{m}_{i=1}\mathbb{E}\left[\text{number of chopsticks }i\text{ is odd}\right]
\end{align*}

下方的式子是利用期望值的線性可加性替換而成的，如此一來我們就可以針對每一種筷子去計算他是奇數的期望值，令這個布林 event 為 $\mathrm{odd}_i$。

對於第 $i$ 類筷子，我們不妨窮舉這類筷子實際拿了奇數 $j$ 雙。再乘上其他筷子的排列的方法數後，我們可以寫出式子得到：

\begin{align*}
\mathrm{E}[\mathrm{odd}_i] &= \frac{1}{\binom{s}{2n}}\sum_{1\leq j\leq k_i, j\text{ is odd}}\binom{k_i}{j} \cdot \binom{s - k_i}{2n - j}\\
&=\frac{1}{\binom{s}{2n}}\sum_{1\leq j\leq k_i, j\text{ is odd}}\frac{k_i!}{j!(k_i-j)!}\cdot \frac{(s-k_i)!}{(2n-j)!(s-k_i-(2n-j))!}
\end{align*}

令 $j^\prime=k_i-j$，重新整理式子後我們可以得到

$$
\frac{k_i!(s-k_i)!}{\binom{s}{2n}}\sum_{1\leq j\leq k_i, j\text{ is odd}}\frac{1}{j!(2n-j)!}\cdot \frac{1}{j^\prime!(s-2n-j^\prime)!}
$$

注意到我們希望對於每一個 $k_i$ 都算出這個值，而同樣的 $k_i$ 對應的值是一樣的。這代表我們是要對於每個 $x$ 算：

$$
\mathrm{val}_x=\frac{x!\cdot (s-x)!}{{\binom{s}{2n}}}\cdot\sum_{j+j^\prime=x, j\text{ is odd}}\frac{1}{j!(2n-j)!}\cdot \frac{1}{j^\prime!(s-2n-j^\prime)!}
$$

$\sum$ 後面的兩項各都分別只跟 $j$ 和 $j^\prime$ 有關，因此可以使用 NTT（建議）或 FFT 進行卷積在 $O(n\log n)$ 的時間內算出。

不過這題有一個小陷阱，就是 $\frac{1}{j^\prime!(s-2n-j^\prime)!}$ 這項可能會在 $s$ 是 $998244353$ 的倍數附近時，發生分母沒有模反元素的問題造成錯誤。

有若干條解這題的路線會遇到這個困難，這裡示範如何在上面的做法進行修正。實際上，我們可以把式子變成：

\begin{align*}
\mathrm{val}_x&=\frac{x!\cdot (s-x)!}{s!}\cdot\sum_{j+j^\prime=x, j\text{ is odd}}\frac{(2n)!}{j!(2n-j)!}\cdot \frac{(s-2n)!}{j^\prime!(s-2n-j^\prime)!} \\
&= \frac{1}{\binom{s}{x}}\cdot\sum_{j+j^\prime=x, j\text{ is odd}}\binom{2n}{j}\cdot \binom{s-2n}{j^\prime}
\end{align*}

這樣的話，右邊的卷積部份就可以正常計算，只剩下對於每個 $x$，需要再乘上 $\frac{1}{\binom{s}{x}}$ 的問題。

不過，因為答案有要求要在最後再乘上 $\binom{s}{2n}$，所以因為 $x<2n$，我們便會有辦法把所有 $x$ 的 $\frac{\binom{s}{2n}}{\binom{s}{x}}$ 在 $O(n)$ 時間內算出來，進而通過這題。

### Bonus

1. 如果不特別限制 $k<2n$，例如 $k<4\times 10^5$，你能夠處理嗎？
2. 如果 $k$ 甚至大到 $10^{18}$，你能夠處理嗎？

## Problem I - Reactor

考慮使用線段樹解決這個問題。

令當前第 $i$ 個 reactor 的 pressure 是 $s_i$。

對於線段樹代表區間 $[l, r]$ 的節點，維護以下三種資訊：
- `mival`：在那些 $p_i>1$ 的 reactor 中，最小的 $p_i-s_i$，注意到該值必須要 $>0$。
- `cnt`：這個區間內 vent 的次數。
- `donecnt`：這個區間內的 reactor，$p_i$ 已經被降至 $1$ 的個數。

當進行區間加值時，令當前加值的數值為 $k$，如果 $k$ 比 `mival` 還小，我們就可以直接原地打懶標返回；如果 $k$ 比 `mival` 還大，我們就可以暴力往下遞迴來找到需要 vent 的 reactor。

對於那些 $p_i=1$ 的 reactor，每一次加值都會讓他們得進行 vent，因此可以直接使用懶標維護。

這樣暴力遞迴為什麼是好的呢？因為每個 reactor 至多只會被 vent $O(\log \max\{p_i\})$ 次就會讓 $p_i$ 變成 $1$，每個 vent 會貢獻 $O(\log n)$ 的暴力遞迴花費，所以我們會得到整體複雜度是 $O(q\log n + n\log n\log \max\{p_i\})$。

## Problem J - Gas Station

觀察到如果選擇了一個比正確答案還要小的 $d'$，則需要的加油站數量會大於 $k$，反之小於等於 $k$。因此藉由二分搜尋法，透過指定的 $d'$ 計算所需要的加油站數量，來檢驗選定的 $d'$ 是太大或是太小。

對於計算加油站數量的部分，由於我們固定了 $d'$，因此可以簡單的使用 DFS 來計算。設 $\mathsf{dfs}(r)$ 為以 $r$ 為根的子樹，$r$ 到最近的加油站距離。對於 $r$ 的子樹 $(u, l)$，若

1. $l > d'$ 則明顯無解
2. $\mathsf{dfs}(u)+l>d'$ 則我們應設一個加油站在 $u$

最後，如果存在 $r$ 的兩個子樹 $(u, l_u)$, $(v, l_v)$ 他們之間加油站的距離 $\mathsf{dfs}(u)+l_u+l_v+\mathsf{dfs}(v) > d'$，則我們應設一個加油站在 $r$。

該 $\mathsf{dfs}$ 可以在 $O(n)$ 的時間完成，二分搜尋法檢驗的範圍不大於 $\sum l$，因此整體時間複雜度為 $O(n\log \sum l)$ 。

## Problem K - Move Stone

給定一個 $n\times n$ 的棋盤，格子 $(i,j)$ 內有 $a_{i,j}$ 顆石頭，且總石頭數恰為 $n^2$。一次操作可將一顆石頭移到同一列或同一行的任一格。 題目目標是用最少的操作，使每格都剛好有一顆石頭，輸出所需的最小操作數。

### 使用最小費用最大流模型建模
我們將每顆石頭對應到一個目標格子。若將石頭從 $(i, j)$ 指派到 $(x, y)$，其花費定義如下：

$$
\text{cost} =
\begin{cases}
1 & \text{若 } (i = x \text{ 或 } j = y),\ (i,j) \ne (x,y) \\
2 & \text{其他情況}
\end{cases}
$$

### 使用 Dinic 最大流演算法優化時間
由於所有花費僅為 $1$ 或 $2$，我們可以重新描述問題：

設 $x$ 為花費為 $1$ 的指派數量，我們的目標是**最大化 $x$**。

此問題可以透過 **Dinic 的最大流演算法**來解決。

節點數與邊數都可以壓縮到 $O(n^2)$ 的量級。

## Problem L - Stapler

給一個實心長方形以及一條線段，目標是判斷他們是否有交集。

如果線段和長方形的任何一條邊相交，那答案一定是 `STOP`。線段是否相交可以從端點之間的順/逆時針方向判斷，另外也可以用公式求出直線交點座標之後檢查是否在線段上。要特別注意有其中一個端點在另一條線段上的特別情況。

否則如果線段沒和邊相交但端點都在長方形內部，那答案也是 `STOP`。因為長方形的邊和座標軸平行，可以分別檢查 $x$ 和 $y$ 座標範圍來判斷。

如果以上條件都不成立，可以得出兩者沒有交集，答案為 `OK`。