2015年6月2日 星期二

BeverageCup2ChallengeProblems



原始題目連結

好讀gitbook版

E - Kirino in Google Code Jam

中文題目

桐乃最喜歡哥哥了!現在她的哥哥為了專心準備大學聯考而搬出去一個人住,桐乃為了慰勞哥哥所以每天幫哥哥做早餐!今天 (2015/4/8) 桐乃和哥哥約好早上十點要送早餐過去,可是一早醒來卻發現早上 9:00 ~ 11:30 是 Google Code Jam 的 Round 1A,好在這個 Round 的題目對桐乃來說並不太難,她在三十分鐘左右就完成了所有題目。但要上傳答案前卻發現有一些測試資料能讓她的程式碼 WA 掉,但桐乃一時間不知道該如何解決這個 Bug,桐乃心想:「啊啊啊算了啦,就放它去吧,哥哥比較重要!我就直接上傳並趕緊幫哥哥做早餐!」於是桐乃如期送早餐去給哥哥了。
送完早餐回到家後,比賽已經結束了,桐乃發現她所有上傳的答案都被評為正確!?這時她傻笑的說:「嘿嘿嘿~這一定是我對哥哥的愛所賜的祝福吧 :D」

從這個故事我們可以注意到,要生測資實屬不易,實際上能讓桐乃 WA 掉的測資,可以讓不少人的 code 都 WA 掉,若比賽的正式測資存在這樣的測資的話,比賽結將會大大的不同吧?
現在問題來了,你能夠生出讓桐乃該題 WA 掉的測資嗎?
要看該題題目敘述請點這 ( Problem C Logging )
要找到桐乃(Kirino)的程式碼請點這

簡化題意

請找到一組能讓 2015 年 Google Code Jam Round 1A 第三名第三題的 Code WA 的測資。

原題解答

在解這題之前請先了解原題的做法,可參考 官方題解jo4 的 BlogMorris 的 Blog
P.S. 我出這題的靈感如下:某天我看到 jo4 的 Blog 題到我的 Code,我就感到非常慌張,因為我不確定我的 code 中 EPS 值是否恰當,深怕其他人看到我的 code 會誤以為只要為 就夠了,仔細研究一下就發現我 EPS 真的設太大了…

題解

要生出讓該 code WA 掉的測資,首先,你要知道 Bug 在哪。但這份程式碼若只考慮它的邏輯正確性,大概是找不出任何 Bug 吧?若非邏輯錯誤,Bug 會是在哪呢?答案是浮點數的精確度不足。該份 code 的浮點數誤差(EPS)使用的數值為 ,但在本題的數據範圍下,這樣的數值並不夠小,有機會產生誤判。
以下為導致 WA 的程式碼區塊:
for(int j=0;j<vn*2;j++){ // 原code這個for迴圈是使用Macro
    while(v[ll]+PI+1e-12<v[j])ll++;
    if(j>=vn)ma=max(ma,j-ll+1);
}
在 while 迴圈裡想要判斷是否 v[ll] + PI < v[j],因為浮點數的運算有機會產生非常小的誤差,使得運算的結果比真實數值還小,於是通常我們會額外加一個稍為比電腦的計算誤差大一點的數值 來避免誤判,但 若設太大,就會有機會使得原本不等式會成立卻變成不成立了。而我們要讓這份程式碼 WA 掉,至少要先找出什麼時候會不等式本該成立卻變成不成立。這這個問題可根據 v[ll]v[j] 產生的方法追本溯源變為尋找平面上夾角介於 之間的三個整數座標點
現在把此問題轉為數學式:請找出兩個整數座標的向量 ,使得這兩個向量夾角 滿足
很接近 的夾角對大家來說可能比較難想像,那我們把向量 反向,於是所求也可想像成 的夾角必須小於
現在我們就來想想,平面上給定座標範圍最接近的兩個夾角可以多小?這個問題在 Codefoces 的 Blog 上有某人給了解答。但我用我自己的方法來解釋,因為兩向量夾角 很小時,擁有公式 ,其中分子 由於座標都是整數又非零,所以最小的可能值為 ,而分母最大的可能情形為在限制範圍內最遠的兩個點座標距離平方,也就是 ,於是我們就能估出任兩個不同方向的最小夾角至少為 。哇!!!原來有辦法估出那麼精準的下界!有沒有很驚訝呢?(小月自己發現這件事時是非常驚訝啦!因為類似題目見了超多次,我都是隨便使用一個 EPS 值,從沒好好估過,經過這次經驗以後就知道要怎麼估了。)
但只是估出下界還不足以解出這題,現在我們不是要解出原題,而是要構造一組極限的測試資料。這時我們就要利用一個簡單的恆等式: 而構造出三個座標點 用電腦算一下這三個點最小的夾角是 ,和我們估出來的下界非常接近吧!但實際上,我們要找的是接近 的角度而不是接近 的角度,這樣的話用類似方法構造出來的三個點應該會是 其夾角和 的差距約為 ,仍舊比 Kirino 所設的 EPS 還小。
找出很接近 的角後我們還差一步,雖然我們已經讓 while 迴圈判斷錯誤,但若只有三個頂點, Kirino 的 Code 無論如何都還是能跑出正確答案,你至少要再加一個頂點才能讓此 Bug 產生對答案的副作用,而這最後這一步就留給大家自由發揮吧~
順帶一題,小月在測試的時候是生了一個 的答案,而至今為止 AC 的四個人有三個人八成也是用類似方法構造出了 的答案,而還有另一個參賽者採取完全不同的策略解這題:隨機生出大量的點來尋找夾角超小的頂點們,在想辦法用他們找到一組能使 Kirino WA 掉的測試資料,詳情請參考該參賽者(Morris)的 Blog

F - No challenge No life

題解

這題我想是沒啥特別的地方,我只是想藉由這題告訴大家,不要太相信網路上所看見的題解或 code,據我經驗,網路上的題解及 code 有誤或複雜度來亂的情況非常多,高達一成以上吧?(亂估 XD) 也請不要太相信小月寫的題解們,請務必好好自己想過 >_<
想要真正的題解,請參考 Morris 的 Blog

題目由來

原本這個quota是要出另外一題計算幾合的,但那題正解太難了,我不會做,之後的某天… Morris大大敲了小月…
conversation