Codechef 2015 JULY Long Challenge

趁著ProjectEuler Summer Break的時候，抽空做了一下Codechef 七月的Long Challenge。由於我的算法很弱，不求高位，但求前一百名。


最後我終於做到了，擠進到前100名。
以下是我解題的小小心得。
照例先從有興趣的題先看起。

第一題先做的是這個：Rohith and Circles

大圓內切三小圓，三小圓又兩兩互相外切的問題
如下圖:

給定R₁、R₂、R₃、R₄，找出R_N1,R_N2, R_N3,....,R_Nt的總和值，1≤ t ≤ 10⁷
N₁,N₂,...,N_t由下列公式決定之
N_t = (P * N_{t - 1}) % M + B
題目會給N₀, P, M 和 B的值，且保證存在著一組R₁、R₂、R₃、R₄的值使得C₂,C₃,C₄任兩圓相互外切，且又和C₁內切。

一開始誤讀題目，結果做好久。題目並沒有說R₁、R₂、R₃、R₄一定是整數值啊，我卻腦補成這四個半徑都是整數值，所以提交了好多次的程式還是一直吃WA。

用Google找到R₁、R₂、R₃、R₄的關係式:
http://blog.xuite.net/isdp2008am/wretch/123045919-從一個問題看數學的對稱性

大圓內三互切小圓的半徑是a,b,c，外切的大圓半徑是d
則有如下的關係式：

如圖，要求出C₅的半徑R₅，則將R₁、R₂、R₄代入方程式內，設R₅為未知數，變成一元二次方程式，會得出兩根，其中一根是R₃(因為C₂、C₃、C₄也是兩兩互切)，所以就是不等於R₃的那根就是R₅。若是重根，R₃=R₅。同理，要求出R₆，則將R₁、R₂、R₅代入方程式內，設R₆為未知數。一樣得到兩根R₄跟R₆。如此持續計算下去，可得到R₇、R₈、R₉、...

理論上可以一項一項求下去直到算到題目要求的R_Nt值，但根據題目所給的計算方式及N₀, P, M 和 B的Constraint值，最壞情況是有可能到R_{2,000,000,000}。一項一項求下去一定會吃TLE。所以只好另外想辦法。

沒想到一開始的誤讀題目反而幫助我解了這題。如上所述，要求出R_t(t≥5)，必須將R₁、R₂、R_t-1代入方程式內，設R_t為未知數，得出兩根為R_t-2及R_t。若R₁、R₂、R_t-1都是有理數，通分化簡後可得R_t的一元二次整數係數方程式，若其中一根為有理數，另一根當然也是有理數。若R₃是有理數，R₅當然也是有理數；若R₄是有理數，R₆當然也是有理數。一直推論下去可得出R₇、R₈、R₉、...R_N、...皆是有理數。

所以我就找了一個例子來看 ，跑程式Brute-force得到滿足題目描述的一組整數值：{R₁=20，R₂=12，R₃=5，R₄=3}。用wolfram alpha計算R₅、R₆、R₇、R₈...的值得出R₅=15/8，R₆=5/4，R₇=15/17，R₈=15/23，...若將R₃到R₁₀的倒數排成一列並將分母通分則可得到一個有趣的數列{3/15,5/15,8/15,12/15,17/15,23/15,30/15,38/15}。數列中每兩個相鄰位置的數字的差值以1/15的值遞增之。換句話說也就是

為什麼會有這種結果呢？我決定把R_N的兩根求出來，令R₁=R，R₂=a，R_t=b，代入上述方程式：

解出1/R_N的兩根，也就是1/R_t-1跟1/R_t+1為

兩者相加得出

又R=R₁，a=R₂，b=R_t

得出

就是之前所述的R_N半徑倒數的關係式，當R₁=20，R₂=12，則(2/R₂) - (2/R₁)=1/15。
根據上述公式，那麼對於任意整數N且N≥3的R_N可寫成下列表示式

 如此一來，對於任意第N項的半徑R_N可在O(1)的時間內求出。


但是提交了好多次，還是一直吃WA，最後才發現自己是sb的事實。原來R₁、R₂、R₃、R₄並沒有說是整數啊，只說是四個實數。所以我一開始用了scanf("%lld %lld %lld %lld", &R1, &R2, &R3, &R4);當然讀不到正確值了！改了一下就過了此題。上述的R_N通項公式還是可以用在實數。

這題是2015 JULY Long做得最久的一題。

接下來做的是這題：Sereja and Game 2

題目大意是Sereja和朋友玩遊戲，連Sereja在內一共有n個人玩遊戲(n≤13)，Sereja是第一個玩的人，遊戲一共有m回合(m≤10000)。遊戲的內容並不重要，重點是對於每一回合，每一個人在此回合中皆有一個勝率。定義一個set為執行完所有m回合遊戲的一個歷程，如果有一個人在第一個set中，在m回合的遊戲中每一回合皆獲勝，稱為全勝，則此人為溫拿(winner)，遊戲結束。若無人在第一個set中拿到全勝則第2個set開始，再執行m回合的遊戲....如此持續下去。直到有人拿到全勝成為winner為止。

令第i個玩家在第j回合獲勝的機率是P_i,j，求Sereja在10^(10^(10^(10^(10^10))))個sets後成為溫拿的機率？題目保證對於某一回合所有人的勝率的總和為1。

10^(10^(10^(10^(10^10))))個sets ，其實就是無限個sets的意思。

簡單的機率問題，經過簡單推論後得到以下結論。
令P_i = P_i,1*P_i,2*...*P_i,m，Sereja獲勝的機率就是$\frac{p_1}{\sum_{k=1}^{n}P_k}$ (注意！Sereja是第一個玩家)

當m很大時，由於P_i,1*P_i,2*...*P_i,m乘起來很小，小於double所能表示的範圍，必須注意，所以我是用Log下去做的。

水題一枚，不知道為什麼做出來的人這麼少？

接下來是這題：Bread

簡單題，第i-1天留下來的麵包數r_i-1、第i天需要吃的麵包數A_i與第i天所需開的麵包盒數q_i有這樣的關係式：r_i-1+q_i*k≥A_i。求出q_i的最小值q_i,min，若r_i-1≥A_i，則q_i,min為0。計算出第i天留下來的新麵包數r_i=r_i-1+k*q_i,min-A_i，r_i若大於0，r_i減去一。將i加一，則原來的i變成i-1，重覆上述步驟直到計算出N天所需的麵包盒數總和。

當i=1，前一天(也就是第0天)留下來的麵包數r₀=0

接下來是這兩題：Na2a and lucky stone、Chef and Cube
簡單題，太過簡單，BJ4。

然後是：Master Chef
找出每一道菜撤銷掉評分的所需最小花費+ 0/1背包
一道菜的評分若是正的，則不需要花錢撤銷，因為他會使得評分總和值更大。
找出每一道菜撤銷評分的最小花費的方法如下:
第i位裁判可以撤銷掉[L_i,R_i]區間內菜餚的評分，所需花費為C_i。我們可以用STL的set記錄兩項資料：花費值C_i跟這筆花費所能及的R_i。若有N道菜，那麼我們可以從陣列的第1位走到第N位，當走到第 j 道菜餚時，把所有L_i=j的裁判i的資料加進set內，然後把所有R_k=j-1的裁判k的資料移除(除了j=1以外，這時還沒有任何資料在set內，沒東西可移除)，使得在set內的資料永遠是L_i≤j≤R_i，C_i在前R_i在後，那麼set內的資料就會按照花費大小C_i排序好，所以set內第一筆資料就是撤銷第 j 道菜的評分所需花費的最小值。

另外，大家都曉得是0/1背包呢，只有我不曉得，寫了很醜的DP還是過掉了。
(咦? 01/背包不就是DP嗎?不是啦，我是說我寫的不是0/1背包那種簡潔的DP)

接下來是：Addition and Multiplication
四種操作：
1. [L,R]區間內所有數皆加上某定值
2. [L,R]區間內所有數皆乘上某定值
3. [L,R]區間內所有數皆設成某初始值
4. 印出[L,R]區間內所有數的總和值。
這四種操作都要取模

又是區間更新 and 區間查詢的問題，好像CodeChef Long十題中一定會出現至少一題區間查詢的問題。一開始想用芬威克樹去做，因為線段樹的實作太麻煩了。後來發現用芬威克樹根本做不出來，只好用線段樹去做。

好像有人這麼說過：「平生不識線段樹，PE全解也枉然」(誤)，可見線段樹的重要，幾乎是所有程式競賽跟On-Line Judge最常用的技巧之一。

懶操作的方法就是設兩個變數v和m，v表示節點中每個數要乘的值，m表示節點中每個數要加的值，父節點傳來的是v'和m'，子節點原來的v和m則變為v=v*v'和m=m*v'+m'。

v=1且m=0表示此節點的延遲標記已被清除。

最後是這題：Maximum Difference Walk 
沒有最佳解的問題，或者說依現有的計算機科學理論還無法在有效時間內找到最佳解的問題。所以大家各憑本事找到最優的次佳解，找到最優次佳解的那個人得到100分。其他人去跟他比較，依等比例給分之。(這題我的理解是這樣，如有錯請見諒。)

亂搞一通的解法，還有70幾分，賺到了。就是憑這一題，才能進到前一百。基本上只要不吃WA，這題應該是很好賺的。

然後，有兩題不會解。

Easy exam

題目叫Easy，一點都不Easy，題目太神不會解。

A game on a graph

好像跟Nim有關，題目太神不會解。

最後成績，解出八題。
雖然只有八十幾名，但能在前一百位，總算達到目標了。dreamoon在第13位，好強，和我根本是不同等級的人。