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

## Advance to Taoyuan Regional 極易

乍看之下，需要計算日期的資料，判斷出 ICPC 桃園區賽前 35 天是哪一天，並比較日期前後。但日期是固定的，可以透過人力計算，或是透過作業系統的日曆查出 9 月 16 日是最後一個可行日期。加上有觀察到 ISO-8601 格式的日期，可以直接透過字串比較大小來判斷日期的前後，那答案會非常簡單。以下為 Python 3 範例解答。

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}$ 的大小關係，小的那一邊比較容易晉級。只是直接拿輸入來做計算，會因為浮點數誤差，難以判斷相等的情形。要避免浮點數誤差，一種方式是採用整數運算來避免。如範例程式的方式進行。

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

這部分的處理，就請參考範例程式。

#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+1$ ，
$$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)$ 個。

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)$ 個。找迴圈的程式碼如果適當時做，則均攤下來，找迴圈總複雜度夠好，就不會超過時限。

#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$。

詳細做法，請參考範例程式。

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$。

print(4000 * int(input())

## Kicks 簽到

由 ChatGPT 命題。只要對任何一種語言的字串熟悉，應該都能做。

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)$ 蓋充電站。

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 分量的總距離和最短：移動所選的點，如往左會導致在選點右方的點貢獻距離，左方的點減少貢獻，每個點增減量絕對值會相等。因此最佳解必須落在中位數之上或之間，不然往某邊移動會得到更好的解。依照題目要求，下中位數是唯一合法的答案。