模擬工作流程，在一個 $N \times N$ 的網格 (左邊界可以通到右邊界，上邊界可以通到下邊界) 上有三種狀態紅 $R$, 藍 $B$, 空格 $W$，每次模擬分成兩個步驟
請問模擬 $M$ 次後盤面為何？
輸入只有一組測資，第一行有兩個整數 $N, \; M$，分別為盤面大小以及模擬次數。接下來會有 $N$ 行，每一行上會有 $N$ 個字元。
輸出 $N \times N$ 盤面。
|
|
|
|
模擬工作流程，平行計算下一個狀態，利用兩個滾動數組的方式交替使用。
|
|
每一字串 $S$，可視為一串操作，依序讀入一個字元 $C$，可以選擇把字元 $C$ 插入字串首或尾，請問字典順序最大為何？
類似 ZJ. 一串數字 之類的貪心方式，優先考慮最大字元在哪一個位置，抓取之後拆分兩串分開貪心合併，每一次由後往前找到第一個最大字典順序字元 $T$，$T$ 移到最前方，此時會將字串分成前半 $A$ 和後半 $B$，然而後半 $B$ 要排在 $T$ 字元之後，勢必只能按照順序丟入隊尾。因此 $\textit{MAXEXPR}(F) = T + \textit{MAXEXPR}(A) + B$。
給定一個 $N \times N$ 方格，每一行或列都是嚴格遞增，現在給定數個行、數個列的排列情況，請問缺漏的那一行或列的序列為何？
明顯地每一個數字都恰好出現偶數次，按照大小順序印出奇數次數字即可。
給同學都有一位摯友，給定 $N$ 個人的好友資訊，現在要求盡可能多的人圍成一圈，並且每一個人其中一側是他們自己的摯友，請問圈最多幾個人。
明顯地，若不看方向性，每一個連通圖至多一個環。若一個連通圖式一個環，保證無法與其他方案合併在一起，因此用 $\mathcal{O}(N^2)$ 優先排除是環的解，在其中找最大圈即可。
接著考慮有觸手的水母圖，當水母大小恰好由兩個點構成時才會有解，因為三個點以上不符合題目要求的環。最後找到經過兩端點的最長觸手，這些點可以自我滿足，把所有最長觸手合併在一起可以構成一組特殊解。兩種方案取最大。
|
|
|
|
|
|
一年一度的 GCJ 資格賽又開打了，這次的題目類型挺開放的，也就是有很多不同的解法可以通過。也許是因為都用了奇怪的方法解決。全寫完 Rank 400 名以內。
打完比賽完全沒心情寫水泥數學的作業證明。不！其實是不會寫。
睡覺前數羊，從一個基數 $N$ 開始，數 $N$, $2N$, $3N$, …, $?N$，直到 10 個位數都出現過，請問最後一個數的數 $?N$ 為何。
除了 $N = 0$ 的特殊情況外，直接模擬即可。最重要的是它不只有看個位數字，把每一位全看的狀況下，要湊滿 0-9 所有 digits 都出現過就不是難事。
現在 $N$ 個煎餅位於堆上，並且有分成兩個正反面狀態，每一次可以把煎餅從堆頂開始連續得拿出，並反轉序列放回堆中，同時把煎餅正反反轉，請問從一個開始序列轉移到全部皆為正面的操作次數最少為何？
一開始的策略是亂貪心一番，甚至題目看錯都能亂過小測資。必要任務一定是先把堆底那片煎餅翻成正的，這時一定堆頂為反，進行一次反轉讓堆底便成正的，為了讓堆頂為反，貪心策略盡可能讓堆頂一連續全部變成反。不斷地模擬此步驟即可。
產生一個數字 $X$，$X$ 長度恰為 $N$，必須首尾皆為 1，只能由 0/1 構成。請產生數字 $X$，滿足在二進制、三進制 … 到十進制下皆為合成數。
這題莫名其妙指定 $N = 16, \; 32$，特殊的 $N$ 使得找到 $J$ 個 $X$ 並不難，更由於 $J$ 不大，各種解法都可以完成。從以往得概念，假設有一個數字 $A = 123123$，那麼保證不進位的情況下，找得到一組 $A = 123 \times 1001$，因此指定 $A = 1????1$，湊滿 $X = AA \cdots A$，不管在哪個進制下，勢必被 $A$ 整除。
詭異的數學碎形考古，給一個長度為 $K$ 的起始字串 $X$，$X$ 只由 $G$ 和 $L$ 構成。碎形迭代 $C$ 次，產生長度為 $K^C$ 的字串。現在雇用 $S$ 個學生，每個學生只能檢查一個位子，只要確定那一個位子有 $G$，那麼原始字串保證有 $G$。在限定學生數量下，請問要怎麼安排學生們的檢查工作。
由於長度為 $K$ 的起始字串有 $2^K$ 種，實際上只要剃除 $LL \cdots L$ 的字串。為了要在最少檢查位置下處理，必然要一個位置能否有 $G$，就能檢查原始字串的數個位置是否有 $G$。
窮舉只有 1 個 $G$ 個字串 $GLL...L$、$LGL...L$、… 等 $K$ 個，追蹤迭代 $C$ 次後，$K^C$ 長度下，每一個字串 $G$ 的出現位置。當 $C = 2$，可以讓位置 1, 2 的 $G$ 可以同時被檢查，同理位置 3, 4 的 $G$ 可以同時被檢查。當 $C = 3$ 時，位置 1, 2, 3 的 $G$ 可以同時被檢查。根據觀察，至少要 $\textit{ceil}(K/C)$ 個學生就能滿足需求。
第 $i$ 個學生要檢查的位置為 $1 + \sum_{0 \le j < C} (C(i-1)+(C-1-j))K^j$。
|
|
|
|
|
|
|
|
運行平行程式之前，要將資料切成很多塊，每一塊之間獨立。從邏輯上看來有 row-based, column-based, matrix-based, tree-based 等平行方法。在許多方法中，最容易入手的就是 row-based。
假設有 $n$ 個元素，編號介於 $[0, n-1]$ 之間，要分成 $m$ 組。每一組得編號都要連續，以增加資料局部性 (data locality) 並且每一塊大小盡可能一樣，請問要怎麼分割才好？這樣的數學問題要做出來並不是件難事，但強迫症的人來說，在程式中零碎的判斷相當折騰。
若有 $n$ 個元素分成 $m$ 組，每一個組至少有 $\lfloor n / m \rfloor$ 個元素，其中 $n \mod m$ 組會額外多一個元素。因此，對於第 $i$ 組滿足 $i < n \mod m$ 都會多一個元素。
|
|
這方式屬於懶惰程序員，根據整數的性質會得到刻度，在計算第 $i$ 個刻度採用 $\lfloor \frac{in}{m} \rfloor$，自然而然地可以與下一個刻度形成一個區間。不幸地，若 $m > n$ 時，有些刻度會重疊，導致重複計算的情況發生。
|
|
從《具體數學》第三章節的介紹，得到幾個簡單的數學公式
$$\begin{align} n = \left \lceil \frac{n}{m} \right \rceil + \left \lceil \frac{n-1}{m} \right \rceil + \cdots + \left \lceil \frac{n-m-1}{m} \right \rceil \end{align}$$第 $i$ 團 ($0 \le i < m$)，要處理 $\left \lceil \frac{n-i}{m} \right \rceil$ 個元素。
|
|
又或者使用 floor 表示法
$$\begin{align} n = \left \lfloor \frac{n}{m} \right \rfloor + \left \lfloor \frac{n+1}{m} \right \rfloor + \cdots + \left \lfloor \frac{n+m-1}{m} \right \rfloor \end{align}$$第 $i$ 團 ($0 \le i < m$)，要處理 $\left \lceil \frac{n+i}{m} \right \rceil$ 個元素。
|
|
不管怎樣，前 $i$ 就拿取 $\lceil \frac{n}{m} \rceil$，最後一組拿少一點。
|
|
|
|
這有一份由 pthread 撰寫的序列總和計算，假設不開任何的優化參數，在快取處理會有嚴重缺失。
輸入序列長度 $n$，計算 $m$ 次經由 $\text{key}, \; \text{key} + 1, \; \text{key} + 2, \; \cdots, \; \text{key} + m-1$ 加密的序列總和。這部份將不提供修改。
|
|
計算工作交由 void f(int n, int key, int *p1, int *p2, int *p3, int *p4); 完成最後四個參數，將會由 4 個 thread 計算分別儲存在位址 p1, p2, p3, p4 中。
|
|
平行計算序列總和，特別注意到 void* subtask(void* argu) 中存取的記憶體位置。
|
|
你的工作要改善下方代碼的效能。
|
|
輸入只有一行三個整數 $n, \; m, \; \text{key}$。
輸出 $m$ 序列總和結果 (無視 overflow)。
|
|
|
|
|
|
由於茵可大神給予我參考的簡報 Mind Cache 中提到不少的快取實驗，其中一部份就是在 thread 使用上，於是就拿來出題測試測試一番。
通常講到數據局部性 (Data Locality) 都希望資料盡量集中，但一不小心會犯下錯誤，就是在多個 thread 儲存答案時，雖然不會共用同一個位址，但相鄰的位址在另一個核 (core) 使用，由於彼此之間相互修改，兩個相鄰位址若放在同一個 cache line，dirty bit 勢必要讓他們從 cache line 掉到 L1 -> L2 -> L3，進行資料同步。
目前 cache line 普遍上設計大小為 64 Bytes，相當於間隔 16 個 4 bytes Integer 的差距，所以儲存答案間隔遠一點會比近一點好。當然，編譯器優化參數開到 O2 以上時，似乎就直接先存放到暫存器裡頭，不會不斷地存取 global memory 部份，如此一來，就不會發生 cache miss 問題。實驗結果效能可以差到四倍左右。
|
|
給予序列 $A \left[ 1 \cdots n \right]$，請計算前綴和序列 $S \left[ 1 \cdots n \right]$，其中 $$S \left[ i \right] = \sum_{k=1}^{i} A \left[ k \right]$$
為了檢測方便，移除輸入和輸出時間，序列 $A$ 由一個簡單加密 $\textit{key}$ 得到序列 $$A \left[ i \right] = \textit{encrypt}(i, \textit{key})$$以及輸出部分直接呼叫$\textit{output}(\textit{S}, n)$。注意$S\left[ 0 \right] = 0$，儲存答案的範圍為$S\left[ 1 \cdots n \right]$。
可以直接 #include "utils.h" 在你的程式中。
|
|
請修改這份程序。
|
|
實際情況會用助教寫好的平行方式進行計算且雜湊公式不同。
|
|
輸入有多組測資，每組測資一行兩個整數 $n$, $\textit{key}$，分別為序列長度 $n$，加密金鑰 $\textit{key}$。
對於每一組測資呼叫 output(uint32_t presum[], int n)，隨後會輸出一個數值。
|
|
|
|
|
|
推薦使用 4 個執行緒解決此問題，平行效能接近 2 倍改進。若使用過多的執行緒，將因為要排到另一個處理器上運行而變慢。
|
|
利用 $P$ 的 thread，分開計算區間 $[1, N/P], \; [N/P+1, 2N/P], \cdots$ 的前綴和，由於前綴和只有利用加法計算，加法具有結合律，隨後傳遞前 $i$ 段的和，可以循序 $\mathcal{O}(P)$ 完成，或者利用樹形平行 (tree-based) 的方式在 $\mathcal{O}(\log P)$，在實務上直接循序即可。
由於採用分治方式，需要平行兩次，時間複雜度為 $\mathcal{O}(2 \frac{N}{P} + P)$。
|
|
兩個人均分一個簡單凸多邊形的蛋糕，蛋糕高度為 2。第一個人 $A$ 選擇一個頂點 $u$，第二個人 $B$ 選擇另一個頂點 $v$，兩點連線後，將蛋糕分成兩塊，最大那一塊會被 $A$ 拿走，小的那一塊會被 $B$ 拿走，請問在各自最佳策略下，盡可能拿到最大塊面積的結果為何？
|
|
|
|
首先，在最佳策略下，當 $u$ 已經固定，接下來選擇頂點 $v$，$B$ 的決定必然要使最小塊最大化，而對於 $A$ 而言，選擇 $B$ 已經使最小塊最大化的所有方法中，使得最大塊最大化。
明顯地兩塊面積近似一半，由於是凸多邊形，可以根據掃描線的方式推動頂點 $v$，使得 $\overline{uv}$ 切分的面積近似一半，對於簡單多邊形面積計算由行列式計算，但行列式計算時的變數呈現環狀，先把首尾變數提出，維護中行列式中間一大段的計算，最後補足首尾變數來計算面積。
|
|
ACM 辦公室在銀河的各處，辦公室編號 $1$ 到 $N$，辦公室 $i$ 和辦公室 $j$ 之間的移動費用隨著時間 $t$ 成線性關係，假設移動不消耗時間，請決定移動時間 $t$，從辦公室 $1$ 移動到辦公室 $N$ 請問最少花費為何。
給定時間必須在一天以內完成，意即 $0 \le t \le 24 \times 60$。
|
|
|
|
明顯地，每一條邊花費都呈現線性關係，假設一張圖只有一條邊，依序加入新的邊進去，時間 $t$ 對應的路徑花費呈現凹性，因此三分搜尋時間 $t$，做一次 Dijkstra $\mathcal{O}(V \log E)$。由於需要精準度到小數五位，估計要到至少三分 50 次，總時間複雜度 $\mathcal{O}(100 V \log E)$。
|
|
有 $N$ 道關卡，每一道關卡需要消耗能量 $E_i$ 才能通過，每一個關卡有能量商店，只能進行一次交易，一旦交易成功，不管先前的剩餘能量為何，直接消耗 $C_j$ 元補能量到 $S_j$，請問至少花費多少錢才能闖完所有關卡。
|
|
|
|
明顯地，維護一個最小堆，每一個元素紀錄 <在哪一關買商店, 累計多少花費, 購買時有多少能量>，隨著掃描線移動，依序出隊那些無法抵達的元素，並且隊首花費就是到這一關的最少花費 $C$，再依序嘗試在新的商店購買能量，累計花費後入隊。
時間複雜度 $\mathcal{O}(N \log M)$
|
|
馬戲團河馬過門，單一隻河馬過門需要時間 $T_a$，兩隻河馬疊在一起且滿足總高度小於 $H$，需要花費 $T_b$ 的時間。
不管任何順序過門，請問最少時間為何？
|
|
|
|
明顯地，最矮的那隻盡量跟最高的那隻配在一起過門，反之考慮分開過門，看哪一種好就選擇哪一種。
|
|