# 2023 ICPC Taiwan Online Programming Contest 簡易題解/提示
###### tags: `TOPC` `ICPC` `Competitive Programming`
## Advance to Taoyuan Regional 極易
乍看之下，需要計算日期的資料，判斷出 ICPC 桃園區賽前 35 天是哪一天，並比較日期前後。但日期是固定的，可以透過人力計算，或是透過作業系統的日曆查出 9 月 16 日是最後一個可行日期。加上有觀察到 ISO-8601 格式的日期，可以直接透過字串比較大小來判斷日期的前後，那答案會非常簡單。以下為 Python 3 範例解答。
```python=
if input() <= '2023-09-16':
print('GOOD')
else:
print('TOO LATE')
```
## Better Chance 易
仔細讀完規則後，會發現只需要比較 $\frac{R_T-1}{S_T}$ 跟 $\frac{R_J-1}{S_J}$ 的大小關係，小的那一邊比較容易晉級。只是直接拿輸入來做計算，會因為浮點數誤差，難以判斷相等的情形。要避免浮點數誤差，一種方式是採用整數運算來避免。如範例程式的方式進行。
```python=
rt, rj, st, sj = [x for x in input().strip().split()]
rt, rj = int(rt), int(rj)
st = int(float(st) * 100 + 0.5)
sj = int(float(sj) * 100 + 0.5)
# 改用移項乘法比較大小，避免產生浮點，造成誤差
if (rt - 1) * sj < (rj - 1) * st:
print('TAOYUAN')
elif (rt - 1) * sj > (rj - 1) * st:
print('JAKARTA')
else:
print('SAME')
```
多數語言浮點數型態轉整數型態的時候，並非轉為最靠近的整數，而是捨去小數點後的資料居多，因此在後面加上 `0.5` 才會有把正小數轉換為最靠近整數的效果。另外也可採用 `round` 函數來達到轉換為最靠近整數值的效果，只是要注意 `round` 傳回值仍是 `float` 型態，要記得轉型為整數，雙精度浮點數(double-precision floating-point number)在絕對值不超過 $2^{52}$ 時，記錄的整數不會有誤差。
## Cutting into Monotone Increasing Sequence 中偏易
本題問最少需要插入多少個逗號，讓一個數字 $x$ 變成一個單調遞增數列且滿足下列條件：
1. 最後一項不大於 $b$
2. 逗號不能插入在 $0$ 之前
切不出來要印出 `NO WAY`
許多隊伍採取貪婪演算法，從數字最低位開始，切出比 $b$ 小的數字中，最長的一個。但是有一些特別的測資會導致切不出來。如：
```
1234569009987999 90000
```
這題的作法，是使用動態規劃。假定 $x$ 有 $n$ 位，從高位到低位，將位數編號為 $0,\dots,n-1$。先定義一個輔助用的問題：「令 $x_{i,j}$ 是 $x$ 編號 $i$ 的位數開始的 $j$ 位數所代表的數字，在數列的第一個數字是 $j$ 位數的前提下，最少需要 $dp(i,j)$ 個逗號才能將 $y_i$ 變為單調遞增數列。」
$$dp(i,j)=\left\{\begin{array}{ll}
0&,i+j=n=1\mbox{ and }x\le b\\
\infty&,i+j=n=1\mbox{ and }x > b\\
\infty&,i+j>n\\
\infty&, i+j=n>1\mbox{ and } x_{i,1}=0\\
\infty&, i+j=n>1,x_{i,1}>0\mbox{ and } x_{i,j} > b\\
0&, i+j=n>1,x_{i,1}>0\mbox{ and } x_{i,j} \le b\\
1+\min_{x_{i,j}\le x_{i+j,k}\le b}dp(i+j,k)&,\mbox{otherwise}
\end{array}\right.$$
以上 $\infty$ 視為無解。前兩個類型，是處理特例，當 $x$ 長度只有 $1$ 時，只要看 $x$ 跟 $b$ 的大小即可知道有無解。第三個是處理長度不足 $j$ 時，無解。第四個例子是需要把逗號塞到 $0$ 前面，無解。第五個是處理 $x_{i,j}$ 比 $b$ 大，無解。第六個是 $x_{i,j}$ 剛好就是結尾 $j$ 為，且不超過 $b$，一個逗號都不用就是單調遞增數列。最後一個是其餘的通例，只要 $x_{i+j,n-i-j}$ 可以切出合乎要求的遞增數列，且第一項 $x_{i+j,k}$ 不超過 $x_{i,j}$，即代表一種可能的解是逗號塞在編號 $i+j$ 之前，取其中最小再加一就是 $dp(i,j)$。
另外，有一些特殊測資要別小心處理，比如：
```
0 0
```
這部分的處理，就請參考範例程式。
```c++=
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
// s 為代表 x 的字串
static char b[32], s[100001];
static int dp[100000][20];
scanf("%s %s", &s, &b);
int n = strlen(s), m = strlen(b);
for (int i = 0; i < n; i++)
for(int j = 0; j <= m; j++)
dp[i][j] = 1e7;
for (int i = 1; b[i-1]; i++)
dp[n-i][i] = (s[n-i] != '0') ? 0 : 1e7;
if (strncmp(s+n-m, b, m) > 0)
dp[n-m][m] = 1e7;
if (strcmp("0", s) == 0) dp[0][1] = 0;
for (int i = n-2; i >= 0; i--) {
if (s[i] == '0') continue;
for (int j = 1; j < m && i + j + j <= n; j++) {
if (strncmp(s+i, s+i+j, j) <= 0)
dp[i][j] = min(dp[i][j], dp[i+j][j] + 1);
for (int k = j+1; k < m && i + j + k <= n; k++)
dp[i][j] = min(dp[i][j], dp[i+j][k] + 1);
if (i + j + m <= n && strncmp(s+i+j, b, m) <= 0)
dp[i][j] = min(dp[i][j], dp[i+j][m] + 1);
}
if (i + m + m > n) continue;
if (strncmp(s+i+m, b, m) > 0 || strncmp(s+i, s+i+m, m) > 0) continue;
dp[i][m] = min(dp[i][m], dp[i+m][m] + 1);
}
int ans = 1e7;
for (int i = 1; i <= m; i++)
ans = min(ans, dp[0][i]);
if (ans < 1e7)
printf("%d\n", ans);
else
puts("NO WAY");;
return 0;
}
```
## Divide a Convex 中偏久
依照提議算出凸多邊形之後，設計一個類似旋轉卡尺(rotating calipers)的雙指標(2-pointer)演算法的，去找出切割線段有一端點落在每一條邊上的最短切割線段長，這個長度可以透過三分搜尋法找出。答案就是過程中所找到最短的那一個。雖然實作的程式碼不短，但有準備的話，大部分是可以直接抄參考資料的。範例程式請參考[官網](http://topc2023.icpc.tw/2023-topc-sample-code.zip)。
## Exponentiation 中偏易
有許多隊伍可能直覺想先解出 $x$ 再透過快速冪演算法求出答案，但面對分母有個 $2$ ，對合數 $m$ 取模數下的反元素沒信心就做不出來。
這邊提供兩個做法，可以迴避模反元素的計算。共同一個重要的觀察是對正整數 $p$ 和 $q$ ，
$$\left(x^p+\frac{1}{x^p}\right)\left(x^q+\frac{1}{x^q}\right)=x^{p+q}+x^{|p-q|}+x^{-|p-q|}+x^{-(p+q)}$$
$$x^{p+q}+\frac{1}{x^{p+q}}=\left(x^p+\frac{1}{x^p}\right)\left(x^q+\frac{1}{x^q}\right)-x^{|p-q|}-\frac{1}{x^{|p-q|}}$$
由此，可以推出對一偶數 $2p$ ，
$$x^{2p}+\frac{1}{x^{2p}}=\left(x^p+\frac{1}{x^p}\right)\left(x^p+\frac{1}{x^p}\right)-1-1=\left(x^p+\frac{1}{x^p}\right)^2-2$$
對一奇數 $2p$ ，
$$x^{2p+1}+\frac{1}{x^{2p+1}}=\left(x^{p+1}+\frac{1}{x^{p+1}}\right)\left(x^p+\frac{1}{x^p}\right)-x-\frac{1}{x}$$ \\ $$=\left(x^{p+1}+\frac{1}{x^{p+1}}\right)\left(x^p+\frac{1}{x^p}\right)-\alpha$$
令答案為 $f(\alpha,\beta,m)$ ，我們可以得知：
$$f(\alpha,1,m)=\alpha \mod m$$
$$f(\alpha,2p,m)=f(\alpha,p)^2-2 \mod m$$
$$f(\alpha,2p+1,m)=f(\alpha,p+1,m)f(\alpha,p,m)-\alpha\mod m$$
如果將計算過的 $f(\alpha,p,m)$ 都記錄下來，利用 Memoization 的技法，以下的範例解答只需要 $O(\log \beta)$ 的四則運算就能做出答案。過程中會用到的 $p$ 只有 $O(\log_2\beta)$ 個。
```python=
a, b, m = [int(x) for x in input().strip().split()]
lookup = {}
def sol(a, b, m):
if (ret := lookup.get(b)) != None:
return lookup[b]
if b == 0: ret = 2 % m
elif b == 1: ret = a % m
elif b % 2 == 0: ret = (sol(a, b//2, m) ** 2 - 2) % m
else: ret = (sol(a, b//2, m) * sol(a, b-b//2, m) - a) % m
lookup[b] = ret
return ret
print(sol(a, b, m))
```
另一個方法是觀察 $f(\alpha,\beta,m)=f(\alpha,\beta-1,m)f(\alpha,1,m)-f(\alpha,\beta-2,m)f(\alpha,\beta-2,m)\mod m$
將上述等式寫成：
$$\left(\begin{array}{cc}\alpha&-1\\1&0\end{array}\right)\left(\begin{array}{c}f(\alpha,\beta-1,m)\\f(\alpha,\beta-2,m)\end{array}\right)=\left(\begin{array}{c}f(\alpha,\beta,m)\\f(\alpha,\beta-1,m)\end{array}\right)$$
可以推出利用矩陣快速冪運算的解題方法：
$$\left(\begin{array}{cc}\alpha&-1\\1&0\end{array}\right)^{\beta-1}\left(\begin{array}{c}f(\alpha,1,m)\\f(\alpha,0,m)\end{array}\right)=\left(\begin{array}{cc}\alpha&-1\\1&0\end{array}\right)^{\beta-1}\left(\begin{array}{c}\alpha\\2\end{array}\right)=\left(\begin{array}{c}f(\alpha,\beta,m)\\f(\alpha,\beta-1,m)\end{array}\right)$$
## Finding Bridges 中偏難
這個題目沒有任何強制在線的手段，可以反過來離線做：把刪除邊的操作反過來看成把邊加進來。從完全空的一張圖，把沒有被刪除的邊先一一加入，之後再反序加入被刪除的邊。加邊的過程中，維護一個與原圖有相同點集合的 undirected forest $G$，如果邊在加入的當下是橋「加入前不在原圖的同一個聯通塊」，則將該邊加入$G$，反之，不將該邊加入。所有的到這一步為止，花費對 $G$ 進行 DFS ，依照 DFS 拜訪順序，做成一個 directed forest $G'$，並將所有點標上深度。到這一步為止，花費 $O((n+m)\alpha(n+m))$。雖然 $G$ 上面的橋，在後續的邊加入之後，可能不再是橋，這部分的維護，就靠做第二輪。
接下來，把圖清空，重新把邊加回去，每次加上一條邊時，先檢查當下是否同在一個雙聯通元件，如果是，那就可以略過。如果不是，則有兩種可能：
1. 兩端點間原先就存在路徑，在對應的 undirected forest 中，同在一棵樹上，這樣要把加入後形成迴圈(loop)的邊，全部標為非橋，計數器扣除對應數量，並且把對應的雙聯通元件黏成一塊。
2. 兩端點間原先不存在路徑，那在對應的 undirected forest 中加上一條邊，並標記為樹邊。計數器加一。
黏成一塊的操作跟檢查一個點落在哪個雙聯通元件的操作可以透過 Union-Find Disjoint-Set 來實作。由於整個過程中只會出現 $O(n)$ 的樹邊，總共的 union 操作也不會超過 $O(n)$ 個。找迴圈的程式碼如果適當時做，則均攤下來，找迴圈總複雜度夠好，就不會超過時限。
```c++=
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2000005;
vector<int> G[MAXN];
int p[MAXN], depth[MAXN];
void dfs(int now, int par) {
p[now] = par;
for (int i : G[now]) {
if (i == par)
continue;
depth[i] = depth[now] + 1;
dfs(i, now);
}
}
struct DSU {
vector<int> p;
void init(int n) {
p.resize(n + 1);
for (int i = 1; i <= n; i++)
p[i] = i;
}
int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
void Union(int x, int y) {
x = Find(x), y = Find(y);
if (x == y)
return;
else if (depth[x] < depth[y]) {
p[y] = x;
} else {
p[x] = y;
}
}
} dsu;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> edges(m);
vector<unordered_map<int, int>> edge_tag(n + 1);
for (auto &[u, v] : edges) {
cin >> u >> v;
if (u > v)
swap(u, v);
edge_tag[u][v] = 0;
}
int cur_tag = m;
for (int i = 1; i <= q; i++) {
int u, v;
cin >> u >> v;
if (u > v)
swap(u, v);
edge_tag[u][v] = cur_tag--;
}
for (auto &m : edge_tag)
for (auto &[v, idx] : m) {
if (idx == 0)
idx = cur_tag--;
}
sort(edges.begin(), edges.end(), [&](pair<int, int> e1, pair<int, int> e2) {
return edge_tag[e1.first][e1.second] < edge_tag[e2.first][e2.second];
});
dsu.init(n);
map<pair<int, int>, int> is_tree_edge;
for (auto [u, v] : edges) {
if (dsu.Find(u) != dsu.Find(v)) {
dsu.Union(u, v);
is_tree_edge[{u, v}] = 1;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
}
for (int i = 1; i <= n; i++) {
if (dsu.Find(i) == i) {
depth[i] = 0;
dfs(i, -1);
}
}
dsu.init(n);
int cur_ans = 0;
vector<int> ans = {0};
for (auto [u, v] : edges) {
if (is_tree_edge[{u, v}])
cur_ans++;
else {
u = dsu.Find(u), v = dsu.Find(v);
while (u != v) {
if (depth[u] > depth[v]) {
dsu.Union(u, p[u]);
u = dsu.Find(p[u]);
} else {
dsu.Union(v, p[v]);
v = dsu.Find(p[v]);
}
cur_ans--;
}
}
ans.emplace_back(cur_ans);
}
reverse(ans.begin(), ans.end());
for (int i = 1; i <= q; i++)
cout << ans[i] << '\n';
}
```
## Gadget Construction 難
待命題人提供題解。
## Heap Structure 中偏易
依照 Heap 的結構，我們將點從根開始編號 $1,\dots,n$ ，同一層填滿後，從下一層的最左邊繼續編號。第 $k$ 小的元素能夠放在某節點，有兩個條件要滿足：
1. 有不能有超過 $k-1$ 點在從 Root 到該節點的 Parent 最短路徑上，因此編號超過 $2^{k}-1$ 的，都不可能是答案。另一方面，不存在編號超過 $n$ 的點，因此最後一個可行的位置，編號為 $\min(n,2^k-1)$。實務上計算時，$2^k$可能很大，依照測資範圍，當 $k$ 超過 $64$ 時，取 64 即可。此部分的計算瓶頸為指數計算，但因為以二為基底，可以透過位元左移完成。
2. 該節點作為根的子樹，要有足夠多的值能夠放在該子樹的節點。即 $k,k+1,\dots,n$ 要能夠放在該子樹。子樹的大小，是隨著點編號遞減的，具單調性。可以透過二分搜尋法，找出第一個可以放 $k$ 的位置，或是說前面若干個位置，不能放 $k$。
詳細做法，請參考範例程式。
```python=
def test(n, k, pos):
L, R = pos, pos
cnt = 0
while L <= n:
cnt += min(R, n) - L + 1
L = 2 * L
R = 2 * R + 1
return n - cnt < k - 1
n, k = [int(x) for x in input().strip().split()]
ok = min(n, 2 ** min(65,k) - 1)
cannot = 0
step = 2 ** 63
while step > 0:
if test(n, k, cannot + step):
cannot += step
step //= 2
print(ok-cannot)
```
## Introversion 難
命題人提供之[題解](https://hackmd.io/@j8wK34P3RD2vfebYLWy2VA/SJ29U8qea)。
## Java Warriors 簽到
一隊報名費 $4000$ 元，有 $n$ 隊答案就是 $4000 \times n$。
```python=
print(4000 * int(input())
```
## Kicks 簽到
由 ChatGPT 命題。只要對任何一種語言的字串熟悉，應該都能做。
```python=
s = input().strip()
n = len(s)
cnt = 0
for i in range(n-3):
if s[i:i+4] == 'kick':
cnt += 1
print(cnt)
```
## Location, Location, Location 易
由 ChatGPT 命題，但調整難度為簡單題。由於曼哈頓距離總和其實是 X 軸方向跟 Y 方向可以拆開來看的。於是問題就變成在找 X 座標的下中位數 $x$ 配上 Y 座標的下中位數 $y$，答案是在 $(x,y)$ 蓋充電站。
```python=
n = int(input().strip())
x = []
y = []
for i in range(n):
p, q = [int(v) for v in input().strip().split()]
x.append(p)
y.append(q)
x.sort()
y.sort()
print(x[(n-1)//2], y[(n-1)//2])
```
至於下中位數為何是答案，首先，選在任何一個中位數，都會達成 X 分量的總距離和最短：移動所選的點，如往左會導致在選點右方的點貢獻距離，左方的點減少貢獻，每個點增減量絕對值會相等。因此最佳解必須落在中位數之上或之間，不然往某邊移動會得到更好的解。依照題目要求，下中位數是唯一合法的答案。
Sign in with Wallet
Connect another wallet