# 2022 ICPC Taiwan Online Programming Contest 簡易題解/提示
###### tags: `TOPC` `ICPC` `Competitive Programming`

[題組資料](https://drive.google.com/file/d/11o2tOppq4_3jtGoEY4ZATHz1ysVmnbt7/view?usp=sharing)

## 難 AibohphobiA

先觀察出現長度 >1 的 palindrome 一定是下列兩種情形之一：
1. 長度為偶數：必然有一個長度 2 的 palindrome ，形式是同一個字出現兩次，如 aa 。
2. 長度為奇數：必然有一個長度 3 的 palindrome ，形式是 aba 這類型的。

若完全沒有長度 2 跟 長度 3 的 palindrome ，就完全不會有長度 >1 的 palindrome。

原先 maze 可以看作是格子為點，格子的邊界為邊的一張無向圖。但透過上面的觀察，也可以把每一條格子邊界，搭配通過的方向，看作是一個點，並直接丟棄兩格相同字母的邊界。而能夠接續不產生長度 3 palindrome 的情形，再來建立一條有向邊。

如此一來，原先的問題就變成特定幾個起終點組合，是否存在路徑，是否存在無限長度的路徑等，就可以回答原來的問題。這部分需要處理 Strongly connected components ，確認是否有路徑，是否有環，以及有路無環時路徑長度計算。

## 中偏難 Balanced seesaw array

題目為給一個陣列支援三種操作：
1. 區間加值
2. 區間改值
3. 區間查詢是否可以變成平衡蹺蹺板陣列 也就是我可以找到一個支點位於整數位子，且力矩和為 $0$

想像一個array，總合為$s$，如果把支點設在第一位，並算出他的力矩合假設為$x$，不難發現如果把支點設在第2位，力矩合會變為$x-s$，支點在第k位會變成$x-s\cdot(k-1)$。
同樣的假設支點不在subarray的數字範圍內，上述的作法也是成立.
所以我們用線段樹維護，區間和與$a_i\cdot i$的和，最後區間查訊時判斷$a_i\cdot i$是否被區間和整除，且商在subarray範圍內即可，如區間和為0代表他力矩會維持不變，所以判斷$a_i\cdot i$的和是否為0即可。

## 簽到 Correct

計算在 TOPC 只有 1AC 的 Penalty 。大致上就是 $(HH-9)\times 60 + MM$。

## 中偏易 Distance and Tree

在平面上的一個圓上有 $n$ 個點，並給每個點到 root 的距離，問可否造出邊在平面上除端點外不相交的樹形圖。做法是先檢查是否有唯一一個 root ，如果沒有就無解。將點重新編號，把 root 編為 1 ，並將所有的點依照距離分類好，準備逐層建構。

維護一個 map (or set of key-value pairs)，key 放點的編號，value放對應的深度，起始只有 $(1,0)$ 被放在裡面。處理深度 $d$ 的點 (假設編號 $p$) 時，只需要將其接到某一個深度 $d-1$ 的點，並且不跟其他邊相交即可。是否相交的判斷，就可以靠 map 裡，與 $p$ 相鄰的 keys ，找前一個 $p^-$ 跟後一個 $p^+$ (不一定存在)，如 $d_{p^-}=d-1$，那就建構一條邊 $\{p,p^-\}$，如 $d_{p^+}$ 存在且等於 $d-1$，那就建構一條邊 $\{p,p^+\}$。

可以證明如果依照上法建構，必然不會建出會相交的邊。也可以證明，如果是可以建出樹的距離，則也可以證明這個過程可以建出樹。

## 中偏難 Etched Emerald Orbs

給定整數 $k$ ，求 $\frac{2}{k}=\frac{1}{x}+\frac{1}{y}$ 且 $x<y$ 的整數解 $x$ 和 $y$ 。先整理：
$\frac{2}{k}=\frac{1}{x}+\frac{1}{y}\\\frac{2}{k}=\frac{x+y}{xy}\\2xy=kx+ky\\2xy-kx-ky=0\\x(2y-k)-ky=0\\2x(2y-k)-2ky=0\\
2x(2y-k)-k(2y-k)-k^2=0\\(2x-k)(2y-k)=k^2$
因 $k$ 是整數，如 $x$ 與 $y$ 要整數解，則 $(2x-k)$ 與 $(2y-k)$ 均為整數且為 $k^2$ 的因數。因此本題可以透過檢查 $k^2$ 所有的因數，就可以找到所有的 $x$ 跟 $y$，從中選出 $x+y$ 最小的解。但要留意，並非所有 $(2x-k)$ 與 $(2y-k)$ 都可以解出 $x$ 與 $y$。

要找 $k^2$ 所有因數，可透過質因數分解 $k$ ，再列舉 $k^2$ 所有的因數。本題數字範圍，使用 C++ 可用 `__int128` ，不需實作大整數。演算法部分，可使用 Pollard's rho 演算法進行質因數分解。

註：正賽中測資偏弱，$k^2$的因數總數偏少，範例解也偏弱，最後枚舉的部份實做的不理想。如果命題者沒弄錯的話，$k^2$因數最多有 48,715,425 個，只需要試一半就可以確認答案，在 codeforces 上 C++ 應該還是可以一秒左右解開 $k^2$ 最多因數的測資。經過加強的測試資料以及修正後的程式放在題組資料 E-hack 目錄下。

## 易 Finalists

轉述 Asia Pacific 分配決賽名額的方法，並求實作。讀懂題目後，計算好各站 Site scores ，排序後依照順序發 slot 即可。

## 中偏易 Geekflix

一些節目排成一圈，一開始指在 1 號上，遙控器按一下按鈕，可以播放、選前一個、選後一個節目。第 $k$ 次播放 $i$ 號節目的時候，可以獲得 $\max\{0, a_i-(k-1)b_i\}$ 個 geekcoin，求按 $m$ 次按鈕時，可獲得的最多 geekcoin 數。

可以觀察出，如果我們只播放某一個圓弧(從 $\ell$ 到 $r$)上的節目，那這限制下，最佳的做法會是先從 1 號一直移動到 $\ell$ 或 $r$ ，接下來在按到另一端的過程中，穿插一些播放。能達到的最大值，就是從貪婪的從這圓弧上的節目，可獲得最多的 geekcoin 的開始播，播完後更新為下次播放可獲得的 geekcoin ，再反覆到可以按的次數用完為止。

由此，可以設計一個枚舉所有圓弧 $O(n^2)$ ，並且計算每個圓弧反覆貪婪所得的 geekcoin 數量，每個圓弧再使用 priority queue 需要 $O((n+m)\log n)$，總計是 $O(n^2(n+m)\log n)$。

註：有不很困難的 Dynamic programming 演算法，可做得快一點，請參照此次放出的資料。

## 中偏易 Heximal

給定十進位大數 $N$，計算 $N$ 的六進位表示法的長度。方便起見，令 $n=\log N$ 。進位制轉換是個 $O(n^2)$ ，為題組最主要的效率限制，出題時希望過程中只做一次進位制轉換，也就是將輸入讀入時之外，不再進行進位制轉換或是相同複雜度代價的操作。時限很緊，也故意卡掉 `java.math.BigInteger.toString(radix)` 因此需要盡量優化程式解答。可行的做法有採用二分搜尋法進行 $O(\log n)$ 個冪次運算，或是正確地利用 log 來進行常數個冪次運算與比較來解答。

Python 在大整數的實作效能其實是相當不錯的，包括四則運算與冪次計算，乘法部分，Python採用的實作至少具備 Karatsuba 演算法的效能 $O(n^{1.57})$ ，而冪次運算，在計算 $k$ 次方時，僅使用 $O(\log k)$ 個乘法，如此確保除第一次進位轉換外，只用了 $o(n^2)$ 的時間。在不用重新發明輪子的精神下，建議用 Python 解這個題目，但題組準備時也有用 C++ 透過二分搜、快速冪、$o(n^2)$大數乘法解此題，花費兩百行上下。

註：有隊伍抱怨這題第一時間沒有給 C++ 標程，這邊也提供一個直接採取進位制轉換的作法。觀察 $10^9\approx 2^{30}$ 以及 $6^{12}\approx 2^{31}$，將輸入看成 $10^9$-進位，做一次進位制轉換到 $6^{12}$-進位，如實做得當也可以在時限內通過。經實測，目前提供的 C++ 程式在 CodeForces 上跑起來約三秒上下。

## 難題 Invitation

關鍵字：FFT, NTT

題目為有 $n$ 個區間，問選 $k$ 個區間交集不為 $\emptyset$ 的選法有幾種 求$k=1,\dots, n$的所有答案。

假設有 $k$ 個區間，他們的交集為 $\ell$ 到 $r$，那把所有區間的右界都$-1$就會發現他們的交集變成 $\ell$ 到 $r-1$ 了。
所以要算 $k$ 個區間交集不為 $0$ 的選法就是，假設剛開始有一個array $a$對於每一個區間，把$a_{l_i}, \dots, a_{r_i}$都$+1$，接著算$C(a_i,k)$的總和$sum_1$，接著把所有區間的右界 $-1$ ，再算一次上述的答案 $sum_2$ ，答案就是$sum_1-sum_2$

那同時詢問k個區間，我們把$C(a_i,k)$拆解一下$\frac{a_i!}{k!(a_i-k)!}$假設有兩個多項式
1. $\sum (a_i!)\cdot x^{a_i}$
2. $\sum k\cdot x^{-k}$

把兩個多項式相乘發現多項式會成為 $\sum\frac{a_i!}{k!}\cdot x^{a_i-k}$的形式，而 $C(a_i,k)=C(a_i,a_i-k)$ ，所以每一項的係數除x的指數階乘，就可以算出第 $k$ 項的答案了。