---
tags: 成大高階競技程式設計 2021
---
# 2021 Week3 - Way of Thinking
註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。
---
# 解題思維
競程題目變化萬千，但大多可以分為幾種思考方向。
* 枚舉
* 分治
* 動態規劃
* 貪心
下方透過一個經典的問題，最大區間和問題（maximum subarray problem），
分別進行介紹，並引入更多例題，加深讀者的了解。
:::info
給定一個長度為 $n$ 的整數數列 $a_1, a_2, ... , a_n$，
要求找到一組 $(i,j),\,1 \leq i \leq j \leq n$，使得 $a_i+a_{i+1}+\dots+a_j$ 最大。
:::
---
# 枚舉（Enumeration）
所謂枚舉，就是透過列舉集合中，所有可能為答案的元素，進而找到正確答案。
> 枚舉並不完全等於暴力解，根據題目特性，有時可以去除一些不可能為答案的元素，
> 減少需要枚舉的數量，而每個元素的計算量也常常可以進行優化。
<hr class="thin">
最大區間和問題，枚舉出所有的區間。
```cpp!
int n;
cin >> n;
vector<long long> v(n);
for (auto& x : v) cin >> x;
long long ans{v[0]}; // 確保並非空區間
for (int i{0}; i < n; ++i)
for (int j{i}; j < n; ++j) {
long long sum{0};
for (int k{i}; k <= j; ++k) sum += v[k];
ans = max(ans, sum);
}
```
算法複雜度為 $O(n^3)$。
> 但是我們知道區間和（range sum）可以透過前綴和（prefix sum）快速計算。
令 $rs(i,j)$ 為 $i$ 到 $j$ 的區間和，$ps(i)$ 為前 $i$ 個元素的前綴和。
:::success
$rs(i,j)=ps(j)-ps(i-1)$
:::
```cpp!
int n;
cin >> n;
vector<long long> v(n + 1);
for (int i{1}; i <= n; ++i) cin >> v[i];
// 為了讓 i-1 最小是 0，所以用 1-based
vector<long long> ps(n + 1);
ps[0] = 0;
for (int i{1}; i <= n; ++i) ps[i] = ps[i - 1] + v[i];
long long ans{v[1]};
for (int i{1}; i <= n; ++i)
for (int j{i}; j <= n; ++j)
ans = max(ans, ps[j] - ps[i - 1]);
```
算法改進至 $O(n^2)$。
> 可能有讀者發現，為何不計算 $v[i:n)$ 的前綴和就好？
> 為了順便介紹如何透過前綴和計算區間和，採取一個較麻煩的作法；
> 實際上隨著 `j` 在推進，只需要一個變數，即可紀錄 $v[i:n)$ 的前綴和。
<hr class="dashed">
### [最長迴文子字串（Longest Palindromic Substring）](https://leetcode.com/problems/longest-palindromic-substring/)
:::info
給定一個字串，求所有符合迴文的子字串中，最長的一個。
:::
列舉所有的子字串，再檢查是否為迴文，複雜度為 $O(n^3)$，太慢了。
先來觀察迴文的特性，當一個長度大於 $2$ 的字串 $S$ 是迴文的時候，
令 $a$ 為第一個字元，$S = aS'a$，則 $S'$ 也是迴文；
反過來說，任何長度大於 $2$ 的迴文，都可以從其他迴文擴充而來。
> 從空字串或單個字元開始擴充。
```cpp!
int mx{1};
pair<int, int> ans{0, 0};
for (int i{0}; i < s.length(); ++i) {
// 單個字元
for (int l{i - 1}, r{i + 1}; l >= 0 && r < s.length(); --l, ++r) {
if (s[l] != s[r]) break;
if (r - l + 1 > mx) mx = r - l + 1, ans = {l, r};
}
// 空字串
for (int l{i - 1}, r{i}; l >= 0 && r < s.length(); --l, ++r) {
if (s[l] != s[r]) break;
if (r - l + 1 > mx) mx = r - l + 1, ans = {l, r};
}
}
```
算法複雜度為 $O(n^2)$。
> :bulb::bulb::bulb:此問題可透過 Manacher's algorithm 在 $O(n)$ 內求解，
> 有興趣的讀者可參考[演算法筆記](http://web.ntnu.edu.tw/~algo/Palindrome.html#3)的教學。
<hr class="dashed">
### [Manhattan Subarrays](https://codeforces.com/contest/1550/problem/C)
:::info
給定一個長度為 $n$ 的整數陣列 $a_1, a_2, ... , a_n$，
一個好的子陣列 $a[i:j]$，不存在任何的 $p,\ q,\ r{\;\vert\;}i\leq p\lt q\lt r\leq j$，
使得 $a_p\leq a_q\leq a_r$，或 $a_p\geq a_q\geq a_r$，
請問總共有幾個好的子陣列？
:::
最簡單的想法就是枚舉所有的 $(i,j)$，再來確認 $a[i:j]$ 是否符合條件，
但顯而易見地，這樣算法的複雜度太高了。
回到枚舉的說明，我們只需要確認那些「可能為答案的元素」，
如果 $a[i:j]$ 不符合條件，那對於任何的 $a[i:k]{\;\vert\;}j\lt k$ 也不符合條件；
也就是說，隨著 $j$ 的推進，當 $a[i:j]$ 不符合條件，就不用繼續了。
> 透過固定一個變數（`i`）的角度來思考，也是解題上滿常見的一個技巧。
```cpp!
int ans{0};
for (int i{0}; i < n; ++i)
for (int j{i}; j < n; ++j) {
bool check{true};
for (int p{i}; p < j; ++p)
for (int q{p + 1}; q < j; ++q) {
if (v[p] <= v[q] && v[q] <= v[j]) check = false;
if (v[p] >= v[q] && v[q] >= v[j]) check = false;
}
if (!check) break;
++ans;
}
```
> 可能讀者會疑惑，為什麼裡面檢查是否符合條件的迴圈只有兩層，
> 因為會確認 $a[i:j]$ 時，代表 $a[i:j-1]$ 已經符合條件了，
> 所以其中需要確認的 $p,\ q,\ r$，只剩下 $r$ 是 $j$ 的情況。
儘管做了一些優化，可是四層迴圈看起來複雜度還是很高啊，
不過仔細觀察就可以發現，不會存在一個太長的陣列，
這個陣列一直沒有長度為 $3$ 的非遞增與非遞減子序列（subsequence）。
因為 $3$ 很小，透過暴力列出所有可能（相對大小，並非所有數字），
可以發現符合條件的陣列，最大長度也就 $4$ 而已；
所以裡面的三層迴圈可以視為一個不大的常數，此枚舉解法複雜度為 $O(n)$ 而已。
> 內部三層迴圈實際次數可透過程式計算，最多只有 $10$ 次（`j` 跑到 `i`$+\ 4$）。
> :bulb::bulb::bulb:相關定理可以參考 [Erdős–Szekeres theorem](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem)
**枚舉若是適當地透過問題特性，減少需要列舉的元素，往往也是很有效的。**
---
# 分治（Divide and Conquer）
分治，**分而治之**，就是將一個大的問題，分為若干個的子問題，
而每個子問題也繼續進行切分，直到子問題夠小可以被輕易地求解，
再由這些子問題的答案，合併成父問題的答案，最終得到原問題的答案。
<hr class="thin">
將數列切半，左半的最大區間和，右半的最大區間和，
以及橫跨二邊的最大區間和，三者中的最大值，即為答案。
> 以下區間 $[l:r)$ 用左閉右開（left-closed-right-open）表示，
> 可以發現左閉右開的一個好處。
> $[l:r)\Rightarrow [l:m)+[m:r)$
```cpp!
long long maxsum(const vector<int>& v, int l, int r) {
if (r - l == 1) return v[l];
int m{(l + r) / 2};
long long sum{0}, mx{v[m - 1]};
// 先計算從中間往左邊的最大連續和
for (int i{m - 1}; i >= l; --i) mx = max(mx, sum += v[i]);
// 再加上中間往右邊的最大連續和
sum = mx, mx = sum + v[m];
for (int i{m}; i < r; ++i) mx = max(mx, sum += v[i]);
return max(mx, max(maxsum(v, l, m), maxsum(v, m, r)));
}
```
算法複雜度為 $O(n\log{n})$。
> 上方程式有嚴格確保 `mx` 為「橫跨二邊」（左右都有元素）的最大區間和，
> 其實這不是必要的，但還是需要注意空區間的問題。
<hr class="dashed">
### [逆序數對（number of inversions）](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=5135)
> 這也是一個經典的問題，逆序數對。
:::info
給定一個長度為 $n$ 的整數數列 $a_1, a_2, ... , a_n$，
請問有幾個 $(i,\ j){\;\vert\;}i\lt j$，使得 $a_i$ 大於 $a_j$？
:::
首先透過分治的想法，最簡單的就是把數列對半分開，
問題的答案變為左邊的逆序數對加上右邊的逆序數對，
再加上橫跨兩邊的逆序數對。那麼問題來了，
我們要如何快速計算橫跨兩邊的逆序數對個數呢？
先來舉個小例子觀察看看，$4,\ 5,\ 1,\ 2,\ 3,\ 9$，
從中間分開的話變成 $4,\ 5,\ 1$ 與 $2,\ 3,\ 9$，
先計算左邊為 $4$ 的逆序數對，有 $(4,\ 2),\ (4,\ 3)$，
下一個計算 $5$ 時，會發現由於 $5\gt 4$，
剛剛與 $4$ 配對為逆序數對的數字也都可以與 $5$ 配對。
因此得到結論，若左邊元素若為升序排列的話，每個元素都可以利用之前的結果；
而右邊也一樣進行升序排列的話，才能進行區分。
分治 $\large+$ 排序，就是合併排序（merge sort）了吧？
這邊完完全全就是一個合併排序而已，只是在過程中多計算一些變數。
```cpp!
long long mergeSort(vector<int>& v, int l, int r) {
if (r - l == 1) return 0;
int m{(l + r) / 2};
long long inv{mergeSort(v, l, m) + mergeSort(v, m, r)};
vector<int> tmp{};
int i{l}, j{m};
while (i < m || j < r)
if (i < m && (!(j < r) || v[i] <= v[j])) {
tmp.push_back(v[i++]);
inv += j - m;
} else tmp.push_back(v[j++]);
copy(tmp.begin(), tmp.end(), v.begin() + l);
return inv;
}
```
演算法複雜度為 $O(n\log n)$。
:bulb:此問題也還有許多應用樹狀結構（tree-based）的解法。
:bulb:其中 `i`, `j` 的使用，稱為 two pointers technique，
更多內容可參考 [Codeforces ITMO Academy: pilot course » Two Pointers Method](https://codeforces.com/edu/course/2/lesson/9)。
---
# 動態規劃（Dynamic Programming）
**若這部分無法理解，之後還會有章節專門講 DP。**
> "Programming" in this context refers to a tabular method, not to writing computer code.[^CLRSdp]
> 動態規劃可視為分治法的延伸。
動態規劃與分治一樣，透過子問題的答案，合併得到父問題的答案，
差別在於，這類的問題會出現重疊子問題（overlapping subproblems）；
所以動態規劃透過表格紀錄每個子問題答案，避免重複計算，從而增進演算法的效率。
> 因為父問題需要在知道子問題答案後才能計算，
> 常常會直接從最小的子問題直接開始，慢慢遞推得到答案。
<hr class="thin">
令 $dp[i]$ 為以 $i$ 結尾的最大連續和，
而以 $i$ 結尾的最大連續和只有兩種可能，
以 $i-1$ 結尾的最大連續和加上 $a_i$ 或是只有 $a_i$。
因此我們可以將原問題切分為求解 $dp[0],\ ...,\ dp[n-1]$，
$dp[i]$ 又可以透過 $dp[i-1]$ 求解。
:::success
$ans=\max(dp[0],...,dp[n-1])$
$dp(i)=\max(dp[i-1]+a_i,\ a_i)$
:::
```cpp!
vector<int> dp(n);
dp[0] = v[0];
long long ans{v[0]};
for (int i{1}; i < n; ++i) {
dp[i] = max(dp[i - 1] + v[i], v[i]);
ans = max(ans, dp[i]);
}
```
算法複雜度為 $O(n)$。
<hr class="dashed">
### [最長遞增子序列（LIS, Longest Increasing Subsequence）](https://leetcode.com/problems/longest-increasing-subsequence/)
:::info
給定一個長度為 $n$ 的整數數列 $a_1, a_2, ... , a_n$，
請找出所有遞增子序列中，長度最長的一個。
:::
光是列出所有子序列，就有 $2^n$ 個，暴力解肯定不現實。
因為子序列是遞增的，我們以子序列的最後一個數字為觀點來看，
令 $dp[i]$ 為以 $i$ 結尾的最長遞增子序列，看看 $a_i$ 的前一個數字可以是誰，
如果某個 $j\mid j\lt i$，而 $a_j\lt a_i$ ，則以 $j$ 結尾的最長遞增子序列可以再加上 $a_i$，
組成一個以 $i$ 結尾的遞增子序列，確認過所有可能的 $j$，最大值即為答案。
:::success
$dp[i]=\max\limits_{0\le j\lt i, a_j\lt a_i}(dp[j]+1)$
:::
```cpp!
vector<int> dp(n, 1);
for (int i{0}; i < n; ++i)
for (int j{0}; j < i; ++j)
if (v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1);
int ans{*max_element(dp.begin(), dp.end())};
```
算法複雜度為 $O(n^2)$。
<hr class="dashed">
### [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
:::info
有一個樓梯，你從第 $0$ 階（地板）開始，每走一次可以走 $1$ 或 $2$ 階，
請問爬樓梯到第 $n$ 階，走法總共有幾種？
:::
每次只能走一步或兩步，也就是說，到了第 $i$ 階台階，
只有可能從第 $i-1$ 階或第 $i-2$ 階走過來的。
令 $dp[i]$ 為走到第 $i$ 階的走法數量。
:::success
$dp[i]=dp[i-1]+dp[i-2]$
:::
```cpp!
vector<int> dp(n + 1);
dp[0] = dp[1] = 1;
for (int i{2}; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];
```
算法複雜度為 $O(n)$。
> 這其實就是費氏數列（Fibonacci Sequence）
<hr class="dashed">
### [Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)
:::info
給定一個 $n\times m$ 的矩陣，每個格子有一個整數，
從 $(1,1)$ 走到 $(n,m)$，只能往右或往下，求最小的路徑。
（一條路徑的大小為所有經過格子上的數字加總）
:::
令 $dp[i][j]$ 為從 $(1,1)$ 走到 $(i,j)$ 的最小總和，
$(i,j)$ 的前一個位置只能是 $(i-1,j)$ 或 $(i,j-1)$，
所以就考慮這兩種情況即可。
:::success
$dp[i][j]=\min(dp[i-1][j], dp[i][j-1])+a_{ij}$
:::
```cpp!
vector<vector<int>> dp(n + 1, vector<int>(m + 1, numeric_limits<int>::max()));
dp[1][1] = mtx[1][1];
for (int i{1}; i <= n; ++i)
for (int j{1}; j <= m; ++j) {
if (i == 1 && j == 1) continue;
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + mtx[i][j];
}
```
算法複雜度為 $O(nm)$。
<hr class="dashed">
### [Permutation Game](https://codeforces.com/problemset/problem/1033/C):bulb::bulb:
我們先來考慮這樣的一種組合遊戲（combinatorial game）[^game]：
1. 兩個遊戲者輪流操作，直到誰不能操作，誰就是輸家。
2. 它是一個公平遊戲，也就是說雙方能做的操作是相等的。
3. 遊戲不會再回到之前的狀態
* 假設有兩個遊戲狀態，
只有其中一個狀態經過多次操作後可以進入到另一個狀態，
或是兩個狀態不管怎麼操作都不會進到另一個狀態（互斥）。
> 先定義幾個名詞：
>
> * 必勝狀態：在此狀態進行操作的遊戲者，有著必勝策略
> * 必敗狀態：在此狀態進行操作的遊戲者，無論如何都沒辦法保證自己會贏
> （換句話說就是對方玩得好的話，就確定自己已經輸了）
> * 結束狀態：不能進行操作的遊戲狀態
> * 後繼狀態：進行「一次操作」可以到達的遊戲狀態
接下來考慮它的狀態圖，每個節點是一個遊戲狀態，
而每條有向邊代表遊戲從一個狀態轉移至另一個狀態。
1. 因為「不能操作者輸」，結束狀態為必敗狀態。
2. 因為「雙方合法的操作相等」，狀態不需區分遊戲者。
3. 因為「遊戲不能回到之前的狀態」，這就是一個無環的有向圖（DAG, directed acyclic graph），
因此有拓樸排序（topological sort）。
* 拓樸排序就是，對於任何一個從 A 到 B 的有向邊，A 在這個排序中都早於 B
> 這邊舉個例子，下方是一個 DAG，
> ACBDEF 或 ACEBDF 都是這張圖的一個拓樸排序，
> 但 ABCDEF 就不是，因為 C 應該在 B 之前。
```graphviz
digraph {
A -> B;
A -> C;
A -> D;
A -> E;
B -> D;
B -> F;
C -> B;
C -> D;
D -> F;
E -> F;
}
```
回到遊戲狀態圖，透過拓樸逆序，我們在決定每個遊戲狀態的結果時，
已經知道他所有後繼狀態的結果了；
這裡就出現一個有點反直覺的事，在這樣的遊戲下，
**任意遊戲狀態皆為必勝狀態或必敗狀態**（沒有不確定性存在）。
那我們要怎麼知道它到底是必勝還是必敗狀態呢？下面有兩個規則：
* 一個狀態是必敗狀態若且唯若其所有後繼狀態皆為必勝的
* 一個狀態是必勝狀態若且唯若其存在一個後繼狀態為必敗
> 請多思考這兩個規則，
> 題目都會說玩家足夠聰明的話（If they both play optimally），
> 其實跟這規則就是等義的。
> 再回到上面的例子，假設 F 是那個結束狀態，我們隨便選一個拓樸逆序，FEDBCA。
>
> 1. F 為必敗狀態，因為是結束狀態
> 2. E 為必勝狀態，因為 F 是必敗狀態
> 3. D 為必勝狀態，因為 F 是必敗狀態
> 4. B 為必勝狀態，因為 F 是必敗狀態
> 5. C 為必敗狀態，因為 B D 皆為必勝狀態
> 6. A 為必勝狀態，因為存在 C 為必敗狀態
「先手必勝局面」，代表遊戲的初始狀態是必勝狀態，
所以先操作的玩家必勝。（先手意即先操作的玩家）
> 繼續剛剛的例子，若初始狀態為 C，則為「先手必敗局面」。
<hr class="dotted">
現在回到問題本身，每個遊戲狀態都可以分為它的所有後繼狀態（子問題），
這也是為什麼這題會出現在動態規劃。
:::info
給定 $n$ 個數字 $a_1,...,a_n$（$1\sim n$ 的排列），並且有一個硬幣放在其中一個位置，
在符合下面二個條件的情況下，玩家可以把硬幣從 $i$ 移到 $j$。
* $a_j>a_i$
* $\lvert i-j\rvert\ \%\ a_i=0$
現在有二個玩家輪流移動硬幣，不能移動者為輸家。
在雙方都足夠聰明的情況下，請問誰是贏家？
:::
這題的結束狀態不止一個，看起來好像複雜一些，
但是 $a_i$ 只會往更大的 $a_j$ 移動，因此拓樸逆序就從 $n$ 開始即可。
> 剛剛的兩個規則，在實作上比較簡單的方式，
> 就是看後繼狀態有沒有存在必敗狀態，有的話才是必勝狀態。
> （結束狀態沒有後繼狀態，也為必敗狀態，剛好也符合「沒有存在必敗狀態」這個條件）
```cpp!
int n;
cin >> n;
vector<int> a(n + 1), idx(n + 1);
for (int i{1}; i <= n; ++i) cin >> a[i], idx[a[i]] = i;
vector<bool> w(n + 1, false); // 是否為必勝狀態
for (int ai{n}; ai >= 1; --ai)
for (int j{idx[ai] % ai}; j <= n; j += ai)
if (a[j] > ai && !w[j]) w[idx[ai]] = true;
```
> 競程中的遊戲題目常常是這樣的題目，讀者可能會想說，不就每題都這樣做就好了嗎？
> 的確可以獲得正確答案，但不一定會通過時間限制，
> 較難的題目就需要根據遊戲特性找規律或進行優化。
---
# 貪心法（Greedy Algorithm）
貪心法，在每個時刻，都選擇當下看起來最佳的選擇，
而期望最後也可以得到最佳的答案。
> 競程的題目需要獲得「正確答案」，而非較佳解，
> 所以我們需要一定的論證，來確保題目可以適用貪心法。
貪心法與動態規劃最大的差別在，它有一個貪心的選擇（greedy choice），
而這個選擇與子問題的結果無關，因此它可以直接做選擇，然後再繼續解決剩餘的子問題。
> :bulb::bulb:In a greedy algorithm, we make whatever choice seems best at the moment and then solve the subproblem that remains. The choice made by a greedy algorithm may depend on choices so far, but it cannot depend on any future choices or on the solutions to subproblems. Thus, unlike dynamic programming, which solves the subproblems before making the first choice, a greedy algorithm makes its first choice before solving any subproblems. A dynamic programming algorithm proceeds bottom up, whereas a greedy strategy usually progresses in a top-down fashion, making one greedy choice after another, reducing each given problem instance to a smaller one.[^CLRSgreedy]
> 競程中（或口語上）對於貪心法有著比較廣義的解釋，「每一步都做當前看似最佳的選擇，就足以漸漸求出整個問題的最佳解」。
<hr class="thin">
最大區間和問題無法透過貪心法解決，我們考慮一個再簡單一點的問題，
:::info
給定一個長度為 $n$ 的整數數列 $a_1, a_2, \dots, a_n$，
取出若干個數字加總，請問總和最大為多少。
:::
因為每個數字是否被取到，都是獨立的，我們可以判斷每個數字是否大於 $0$（貪心的選擇），
然後繼續解剩餘陣列 $a[i+1:n]$ 的最大總和（子問題），這樣的問題就適用貪心法。
```cpp!
int ans{0};
for (int i{0}; i < n; ++i)
if (a[i] > 0) ans += a[i];
```
<hr class="dashed">
像是最短路徑的 Dijkstra's algorithm，
最小生成樹的 Kruskal's algorithm 與 Prim's algorithm，
都是貪心演算法，不過也沒有一個通用的規則，
可以決定一個問題是否適用。
> 分治、動態規劃與貪心法有滿多相似之處，多少也有些模糊地帶；
> 但這些都只是演算法的「技巧」而已，重點在於**學到它們的精神**，
> 不需要過度執著在定義上的分類。
---
# References
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)"
* 劉汝佳、陳鋒（2013）。提升程式設計的解題思考力：國際演算法程式設計競賽訓練指南。
* 劉汝佳、陳鋒（2021）。算法競賽入門經典 — 訓練指南（升級版）
[^CLRSdp]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)", p.359.
[^game]: 內容參考自《劉汝佳、陳鋒（2013）。提升程式設計的解題思考力：國際演算法程式設計競賽訓練指南，2.4，組合遊戲。》
[^CLRSgreedy]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, & Clifford Stein (2009). "Introduction to Algorithms (Third Edition)", p.424.
---
# 練習題
| Problem | Tags |
|:-:|:- |
| **Basic** |
| [吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694) | `prefix sum` |
| [四、多麼OwO(OwO)](https://zerojudge.tw/ShowProblem?problemid=c412) | `Enumeration` |
| [簡單的三角形](https://zerojudge.tw/ShowProblem?problemid=c268) | `Enumeration`, `math` |
| [旅行者_九國遊歷記<7> 小紫去鷹國](https://zerojudge.tw/ShowProblem?problemid=c501) | `Enumeration`, `sorting`, `two pointers` |
| [UVa 11464 - Even Parity](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2459) | `Enumeration` |
| [00900 - Brick Wall Patterns](https://zerojudge.tw/ShowProblem?problemid=d038) | `DP` |
| [10918 - Tri Tiling](https://zerojudge.tw/ShowProblem?problemid=b587) | `DP` |
| [11310 - DELIVERY DEBACLE](https://zerojudge.tw/ShowProblem?problemid=d054) | `DP` |
| [Wilson](https://zerojudge.tw/ShowProblem?problemid=b869) | `DP` |
| [最長回文子序列（LPS）](https://tioj.ck.tp.edu.tw/problems/2061) | `DP` |
| [00993 - Product of digits](https://zerojudge.tw/ShowProblem?problemid=d418) | `Greedy` |
| **Challenging** |
| [UVa 11300 - Spreading the Wealth](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2275) | |
| [UVa 1352 - Colored Cubes](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4098) | |
| [UVa 10795 - A Different Task](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1736) | |
| [ICPC Live Archive 3695 - Distant Galaxy](https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=1030) | |
<style>
hr.thin {
height: 0.5px;
}
hr.dotted {
border-top: dotted;
height: .0em;
color: #777777;
background-color: #ffffff;
}
hr.dashed {
border-top: dashed;
height: .0em;
color: #777777;
background-color: #ffffff;
}
/* Gradient transparent - color - transparent */
hr.gradient {
border: 0;
height: 1px;
background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0));
}
/* Flaired edges, by Tomas Theunissen */
hr.flaired {
overflow: visible;
height: 30px;
border-style: solid;
border-color: black;
border-width: 1px 0 0 0;
border-radius: 20px;
background-color: #ffffff;
}
hr.flaired:before { /* Not really supposed to work, but does */
display: block;
content: "";
height: 30px;
margin-top: -31px;
border-style: solid;
border-color: black;
border-width: 0 0 1px 0;
border-radius: 20px;
}
</style>
Sign in with Wallet
Connect another wallet