Codeforces Round #289 (Div. 2) (pD ~ pF)

problem D --- Restoring Numbers

題意：你有個長度為 $n$ 的陣列 $a$ 以及長度為$m$ 的陣列 $b$以及一個正整數 $k$，並且有個 $n \times m$ 表格 $w$，並把格子 $v_{i,j}$ 填入 $a_i + b_j$。如今你已忘了陣列 $a$ 和 $b$以及數字 $k$，但還留有表格 $w$，請給出一組能得到表格 $w$ 的 $a, b$以及 $k$，或者輸出無解。

數據範圍：$1 \le n,m \le 100, 0 \le w_{i,j} \le 10^9$

tag：[ 數學 ]

先想想簡單版的題目：沒有 $mod k$ 這件事且填入的數可正可負。

題目若變成這樣，我們只要令 $a$ 為 $w$ 的第一行(column)，並令 $b$為 $w$ 的第一列並再把所有數減去 $w_{0,0}$，再用這裡得到的 $a$ 和 $b$ 去構造回 $w$ 表格，若吻合就得到答案，若不吻合就無解(why?列一些代數式可得到此結論)。

再看回來原來的題目，若我們使用同樣的做法會怎樣？是否能只修改一些地方就能得到答案呢？

先不考慮構造出來的 $a$ 和 $b$ 可能有負值的問題(實際上若有負值，輸出答案時 mod 最後求出來的 $k$ 後取正就好了)，原本我們要考慮的是藉由構造出來的 $a, b$是否能滿足 $a_i + b_j = w_{i,j}$，但現在我們要的是：能否存在 $k$ 使得所有 $a_i+b_j \equiv w_{i,j}$ (mod $k$)，再換成更好懂的條件： $k \mid a_i + b_j - w_{i,j}$。

於是我們就得到，$k$ 為所有 $a_i + b_j - w_{i,j}$ 的公因數時，用這樣的 $a,b$ 構造出的來表格mod $k$ 後會和 $w$ 一樣，由於實際上還必須使得k大於所有 $w$ 裡的數，所以我們可以直接令 $k$ 為那些數的最大公因數。並且若其大於 $w$ 裡所有數就有解，否則就無解。

最後要注意一個 special case：$w_{i,j}$ 都剛好為 $a_i + b_j$。(想想看會發生什麼事？)

Problem E --- Pretty Song

題意：給一個字串求所有此字串所有 substring 的母音比例總和(母音為AEIOUY)

數據範圍：字串長度不超過 $5 \times 10^5$

tag：[ dp ][ 數學 ]

看到這個問題大概就會想到把 sigma 求和的式子轉換一下可能可以換成比較好算的式子。但這題的式子很直白，我們可以不介由式子，直接把所求想像成每個母音會對一些 substring 貢獻一些值，例如說，若第一個字母是母音，並且它被包含在長度 $1$ ~ $|s|$ 的子字串各恰一個裡，那第一個字母就會貢獻給總和 $1/1 + 1/2 + ... + 1/|s|$。再觀察仔細些，你會發現若第二個字母是母音，將會貢獻給總和 $(1/1 + 1/2 + ... + 1/|s|) + (1/2 + 1/3 + ... + 1/(|s|-1))$。

實際上，對於所有$2 \le i \le |s|/2$，第 $i$ 個字母會比第 $i-1$個字母多貢獻 $1/i + 1/(i+1) + ... + 1/(|s| - i + 1)$的值(Why?)，並考慮到第 $i$ 個字母和第 $|s| +1-i$個字母的貢獻的值一樣的對稱關係，我們就藉由先dp好調和級數求解了。

P.S. 實際上求和的式子可以直接 dp 後計算，請參考官方 Blog 解答

Problem F --- Progress Monitoring

題意：給一個長度為 $n$的 DFS 序列問有多少 tree可以產生這樣的 DFS 序列(同一層 DFS 裡由編號小的先走訪)

數據範圍：$n \le 500$，第一個數一定為 $1$

tag：[ dp ][ 區間型dp ]

有沒有發現 tag 和上一場 Codeforces pE 一樣呢～那我可不可以不要寫這題的題解了啊Orz

就大略解釋一下同個區間我們要記錄什麼狀態。

實際上同個區間我用了兩個狀態：1. 若此區間第一個點為root，有多少種可能 2.若此區間為拜訪額外的root後所得到的序列，有多少種可能

若第一個dp值記作dp1(L1, R1)，第二個記作dp2(L2, R2) (區間為[L1,R1] or [L2,R2])

我們可以列出狀態轉移式：

dp1(L1, R1) = dp2(L1+1, R1)

dp2(L2, R2) = dp1(L2, R2) + dp1(L2, k) * [b(L2+1) $\lt$ b(k+1)] * dp2(k+1,R2) for k from L2 to R2-1

([]的意思是裡面成立的話值為 $1$，否則為 $0$)

若很相信這類的 dp 能解它的話這題應該不會很難才對？

在這裡提供另外一題和本題和像但難度差了十萬八千裡的題目！

UVa 11738 --- Few Teams will Solve this

這題連題目名稱都很潮XD

大意是：給你一個 tree 的 BFS 走訪序列以及 DFS 走訪序列，求有多少種 tree 能產生這樣的序列。

歡迎想出這題的人 PO 出作法和大家分享XD

Codeforces Round #289 (Div. 2) (pA ~ pC)

這場比賽同時也是俄羅斯某個營隊的資格賽，採 ICPC 制，就我看來 pC~pF 難度沒有太大差別。

Problem A --- Maximum in Table

題意：有一個 $n \times n$ 表格 $a$，第一行和第一列所有格子都是 $1$，而其它的格子都滿足 $a_{i,j} = a_{i-1,j} + a_{i,j-1}$ ，求此張表格內最大的數。

數據範圍：$1 \le n \le 10$

tag：[ dp ] [ 數學 ]

就是個希望所有人都 AC 的題目，由於 $n$ 很小，直接從左到又再從上到下 dp 就行了，你只要這麼做之後再從表格中找最大的數就可以 AC。

但你可以再進一步的推論出

1. 表格中最大的數一定在右下角 (why?)

2. 表格中每個數會對應到巴斯卡三角形的某一個數。(想想看 $a_{i,j}$ 會對應到 $C^?_?$？)

所以實際上題目變成 $n$ 若高達 $1,000,000$ 並求最大的數 mod $1,000,000,007$ 也是可解的。

Problem B --- Painting Pebbles

題意：有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 顆石子，你有 $k$ 種不同顏色的油漆，要把所有石子都塗上顏色，使得同一種顏色的石子個數在不同堆裡至多差 $1$。若有辦法塗就給出一種塗法。否則輸出 NO 即可。(可以有顏色在某堆個數為 $0$)

數據範圍：$1 \le n, t \le 100$，$1 \le a_i \le 100$

tag：[ greedy ]

乍看之下可能會不知道從何想起，這種時候我們就從簡單的 case 想起吧！怎樣叫做簡單的 case ?例如說，當只有一堆的時候，但在這題只有一堆的結論太顯然了 XD，所以我們從兩堆開始考慮。我們會發現，當兩堆的個數差不超過 $k$ 時總是可以構造出解 (how?)，並且你可以推出不等式 $\sum_1^k{b_{1,c}} - \sum_1^k{b_{2,c}} \le k$，於是當 $n$ 為 $2$ 時我們會做了！

接著考慮有 $n$ 堆的情形，不難想像結論就是最大堆的個數和最小堆的個數不超過 $k$，至於怎麼構造呢～就留給大家自己想吧～

我的構造法：(以下反白) 設最小堆的石子個數為 $mi$，則每堆石子都先塗上 $mi$ 個第一種顏色，之後若某堆石子數還有 $s$ 顆石子尚未塗色，就分別塗上第 $1$ 至第 $s$ 種顏色。

Problem C --- Sum of Digits

題意：有一個數列 $a$ 含 $n$ 個數，且為嚴格遞增，已知第 $i$ 個數所有位數總和為 $b_i$，求最小的可能 $a_i$ 值。

數據範圍：$1 \le n \le 300$，$1 \le b_i \le 300$

tag： [greedy] [進位]

這題雖然是 pC，主要的 idea也不難，但我卻最後寫它，因為我覺得他很容易寫出 bug (事後看 scoreboard確實如此)。

首先會發現我們一直貪心的構造 $a_i$，構造的方法為令 $a_i$ 為大於 $a_{i-1}$ 且總合為 $b_i$ 的最小的數 (可以假設 $a_0 = 0$)，如此一來一定能使 $a_n$是所有可能中最小的。

所以此問題可以藉由解 "求大於 $x$ 且位數和為 $y$ 的最小的數(問題1)" n 次得到。

若第一次接觸到這類問題可能會覺得並不簡單。我們先想想一個比較簡單的問題：

請求出位數和為 $y$ 的最小的正整數。

這應該不太困難，貪心地從位數低到高一直都填 $9$，直到總和快要超過 $y$ 時改成填 $y mod 9$。

會做這個問題後再回來解問題1，我們枚舉 $x$ 有變動的最高位數，有變動的最高位當然位置愈小愈好，接著我們再枚舉該位要變成哪個數字，例如說若該位是 '7' ，那就只能變成 '8' 或 '9'。枚舉完後，由於我們已經確定 $x$ 已經變大了，剩下的比較低的位數就貪心的填最小的數即可。但若就算全填 '9' 也無法使得總合為 $y$，則繼續枚舉下一個。

看到這裡或許你已經知道怎麼做了，但實作過程還是可能有很多大大小小 bug，請自己多家小心吧Orz

最後我想再考考大家一個問題：在這樣的數據範圍下，答案最多可能會有幾位呢～？
(我想有些人的 bug 是因為這樣產生的，翻了幾份 code 也確實有這樣的 bug)

Codeforces Round #288 (Div. 2)

 pA --- Pasha and Pixels

題意：最初有一個全白的 $n*m$ 的表格，之後有 $k$ 次操作，每個操作會把某格塗黑 (可能去塗已經塗黑的格子)，問第一次出現大小為 $2*2$ 的黑格是什麼時候？

數據範圍： $1 \le n, m \le 1000$，$1 \le k \le 100,000$

tag：[ 模擬 ]

這種類形 (對表格做顏色改變的操作，問什麼時候會出現什麼 pattern 或總共出現幾次) 的題目很多，我敢說近 $30$ 場內有出現類似的題目，$n$ 和 $m$ 的範圍加大也都可以做，做法本質上是模擬，重點約略有二：

1. 用適當的資料結構存取格子的狀態，以這題來說用一個二維陣列就可以了，可以想想看若 $n$ 和 $m$ 很大的時候該怎麼辦。

2. 每個操作後，只去檢查有包含該操作所影響的格子的 pattern，是否已經滿足。

常見會 fail 的地方就是1. 檢查 pattern 時超過存取的資料結構範圍 2. 某次都去檢查所有可能 pattern。

pB --- Anton and currency you all know

題意：給一個位數為 $n$ 的奇數，請問交換兩個位數所產生的偶數最大值為多少？不可能產生偶數則輸出 $0$。

數據範圍：$2 \le n \le 100,000$

tag：[ adhoc ]

交換兩個位數看看會怎樣的題目也蠻常見的，例如說今年 (2015) Facebook Hackercup R1的第一題。

由於要變成偶數，所以一定是拿個位數和某個偶數去交換，最直覺的方法就是都換換看然後使用 strcmp 去比較大小，但這樣會 TLE，因為 #使用太多次可能很花時間的內建函式，這是很多人寫程式生涯中都會犯過的 bug，我也因為這個 bug challenge成功三份 code。

可改成把所有偶數的位數分成比個位數大和比個位數小去討論。

pC --- Anya and Ghost

題意：有 $m$ 隻鬼魂，第 $i$ 隻會在時間 $w_i$ 出現，恰出現一秒。你要在某些時刻花一秒鐘去點蠟燭，蠟燭可以持續燒 $t$ 秒。你希望每隻鬼魂出現的時段都至少有 $r$ 隻蠟燭是正在燃燒著，請問全程至少有點幾隻蠟燭。(可在負的時間點蠟燭)

數據範圍：所有數字皆介於 $1$ 至 $300$

tag：[ greedy ]

從最早出現的鬼魂開始考慮，可以發現為這隻鬼魂點蠟燭的時間愈晚愈好。

數據範圍小小的，所以用任何方法去模擬都幾乎都可 AC。

如果有注意到在考慮第 $i$ 隻鬼魂時，所為他點的蠟燭一定都在第 $i-1$ 隻鬼魂出現之後 (可以想想看為什麼)的話 code 會更好寫。

pD --- Tanya and Password

題意：給 $n$ 個長度為 $3$ 的由大小寫字母及數字組成的字串，問能否找到長度為 $n+2$ 的字串使得此字串所有長度為 $3$ 的子字串恰是所給定的 $n$ 個字串，若能找到請輸出解

數據範圍： $1 \le n \le 200,000$

tag：[ 圖論 ][ 尤拉路徑 ]

這也是經典的尤拉路徑題，第一次遇到這個模式的題目可能會覺得很難，可是由於這類的題目真的很常出現，之前小月的朋友想要辦場 Codeforces 的比賽時也有問過我出這樣類似的題目如何。

解法就是把所有兩個字母組成的字串視為點，並把所有題目給定字串 $c_1 c_2 c_3$ 想像成由點 $c_1 c_2$ 指向 $c_2 c_3$ 的有向邊，可以發現在這張圖上找到尤拉路徑就能找到一組解。

要注意的是由於這題的 n 很大，請務必使用 O(邊數) 的尤拉路徑求法。

pE --- Athur and Brackets

題意：給出一個長度為 $2n$ 且由 '(' 和 ')' 所構成的合法括弧序列，使得第 $i$ 個左括弧與其所對應到的又括弧距離介於 $l_i$ 和 $r_i$ 之間。

數據範圍：$1 \le n \le 600$

tag：[ dp ] [ 區間型dp ]

看到這是括弧類的題目嘛，再看看數據範圍，很容易就想到作法是 $O(n^3)$ 的 dp 類題目了。(再舉個例子：UVa1626)

這類型的dp的狀態往往都是由所有可能的閉區間 $[i, j] (1\le i \le j \le n)$ 所構成，區間長度愈小的狀態在dp過成的愈底部，以這題來說，一個狀態就是記錄僅看邊號在區間 [i, j] 內的所有括號是否有合法的序列，轉移時則枚舉第i個左括號距離對應的右括號的長度，看看是否存在合法序列，若有的話就把此長度記錄下來。

這類的題目我所寫的 code 架構通常如下：

舉個這題實際的轉移的例子。對於第 $1$ 個至第 $6$ 個左括號來說，若第 $1$ 個左括號和對應的右括號距離為 $7$ 是合法的，且只看第 $2$ 個至第 $4$ 個括號能夠成完整括弧序列，以及只看第 $5$ 個至第 $6$ 個左括號也能構成完整括弧序列，那我們就找到了一種把第 $1$ 個至第 $6$ 個括號構成括弧序列的方法了。

去看了官方BLOG，發現其實這題可以做到 O(n)，作者也沒想到 XD (O(n) 的 code)