2015年6月19日 星期五

2015 Distributed Code Jam Online Round 參賽紀錄

對不起又是流水帳(感覺似乎有人在抱怨... ?),不喜歡的話就不要看嘛 >_<

  Distributed Code Jam 是 Google 今年第一次舉辦,原本我都沒有特別注意這項比賽,甚至到了我進入 Round 3 以後,我才知道原來要進入 Round 3 才有資格參加,更甚者,直到剩不到一周的 Practice Round 我才知道 DCJ 的比賽內容是什麼 @@ 看來是在比我在大學時修的平行程式的東西啊... 嘛...就我當初修課的印象,程式因為平行而增加的效率也挺有限的,最基礎的平行方式就是把問題拆成可以分開計算的好幾個子問題,讓每個 Node 去各別處理這些子問題,除此之外也沒其它招了吧?

  姑且還是練了一下 Practice Round 的一些題目,Practice Round 題目還真多? pB 就只是普通的分塊,我試著寫了一下,唔... 要寫之前得先下載它提供的 tool 嘛... 我現在習慣使用的作業系統是 windows 7,並沒有裝 Python 等工具,唔唔唔好麻煩喔 >_< 我最討厭研究怎麼安裝東西了...  最後決定使用 pietty 連線到學校的工作站,並且使用 FileZilla 在 local 端以及工作站間傳送檔案... ,對不起我這種作業方式一點都不像是資工系出身的人 >_< 但是我真的不想為了不過三個小時的比賽認真花時間去研究要怎麼比才會比較有效率...

  在學校的工作站上作業起來就簡單多了,程式寫完就只要輸入官網上提供的指令救可以執行了,唉不對...還得改一下權限才行 @@ 總之 pB 並沒有太花時間的救完成了。

  接著看 Practice Round 的 pC,題目如下:給 $n$ 個數,請問是否存在某個數出現次數過半?

  這如果在一般的演算法競賽理出現這就是個簡單題,開個 map 紀錄救行了,但是啊,在這題你光是讀 input 時間就超過了!(題目有清楚告訴你讀完所有 input 需要花多久時間)所以 input 一定得由所有 node 分別讀進來,唔...讀進來然後要在把所有訊息合併嘛?可是每個 Node 可使用的記憶體諒也有限制,也不可能把所有 input 都 send 到同一個 node 裡,於是在稍微想一下後發現,若存在一個出現次數過半的數字,那它一定在至少一個 Node 理面出現次數也過半,所以我們只要去檢驗每個 Node 出現最多次的數是否維答案即可。於是我就把這題的 code 也寫了。但後來發現,每個 Node 呼叫 send 這個 function的次數不能太多次,但我在寫 code 時沒注意到這件事,於是大測資 Judge 後就炸了...

  之後在看了 Practice Round pD 的題目:數字 $1 \sim N$ 以某種順序維成一圈,給你兩個 function call 分別能得知某個數字的左邊是哪個數字,以及右邊是哪個數字,請根據這兩個 function來決定 1 和 0 的相對位置。

   這題我想了些許時間都不之到要怎麼作,總覺得... 只能 random 選 和 Node 數量一樣的數字們然後交給每個 Node 去跑,但真的是這樣嘛@@最後我就喇塞只用一個 Node 去處理整個問題,然後 pass 了小測資,大測資也隨手傳了上去, Judge 後理所當然獲得了 TLE。事後看了一下別人的 code,似乎真的是使用 random 的方式解這題@@

  寫完這三題,還剩下最後一題,但我覺得我對 api 已經熟悉的差不多了,所以就懶得在做下去了...最後一題至今都還不知道題目是什麼 :P

  來到正式 Online Round 的當天,也就是證常的 GCJ Round 3 的隔天,嗚嗚嗚 GCJ 昨天比的好慘,開場看的第一題就掛蛋了,今天比得怎樣都無所謂了啦,反正這個 DCJ 本來就只是個類似於興節目/表演賽之類的東西吧?決賽入取人數只有 10 人,第一名獎金只有 GCJ 的五分之一,規模小了好多,我把 DCJ 說成這樣那為什麼我還要比呢?我就是喜歡參加比賽不行嘛 >_<

  比賽開始。有四題,題分分別是 8、22、32、38,小測資的題目則分別只有1、2、2、1,比賽時間有三個小時是吧... 第一題應該是真的相當簡單吧?前十名的門檻會在哪呢?最簡單的 pB 肯定是得 AC的吧 ( 題號是從 pB 開始 @@)? 扣除這一題後,認兩題的題分總合都高於任一題的題分,所以要先猜門檻會是幾題大測資,應該不可能門檻是滿分吧 XD 那門檻會是兩題嗎?若門檻是兩題,我想我是一定沒機會的,在時間內我大概只能處理完一題?就算門檻是兩題好了,那應該也會是前兩題吧?以一個第一次半的比賽來說,應該會確保最後一提足夠難。所以若要寫兩題,應該要挑 pC 和 pD,但若門檻是一題呢?挑 pC 應該沒望吧?pE 對我來說可能太難了也不足以考慮,所以說,若目標仍放在進決賽的話,無論如何我都得做出 pD,來不如開場就先看 pD 吧!

  pD 題目如下:有 $N$ 張卡片,任兩張卡片都有固定的勝負關係,請把這 $N$ 張卡片分成非空的兩組 A和 B,使得 A 組的任一張卡片全輸給 B 組的任一張卡片,並且 B 組的卡片張數要盡量多。

  由於我擁有 flow 腦,所以我第一個思考方向就飄往 min-cut 了... 但是我想不到什麼好做法,甚至連是否真的存在 min-cut 的方式解這題都不知道,想了將近 20 分鐘左右以經有些許人 AC 了 pB,所以我就決定先回來把 pB 刷一下。 pB題目是:已知一個數列每個數原本的位置和自己已排序好的位置相差不超過 $D$ ($D \leq 10^6$)請輸出此數列排序後的 hash 值。這題我讀完題就知道怎麼做了,若有 K個 Node,就把序列切成 $K$ 段,第 $i$ 個 Node 就把第 $i-1, i, i +1$三段的數一起排序之類的。總之這題我沒有花太久時間救處理完了。 submit 後比賽還剩下 2時 23分。

  寫完 pB 後我決定還是先看一下 pC的題目,和 Deadlock 有關啊...我和系程最不熟了我可以直接跳過這題嗎 >_< 然後我回答自己:就跳過吧。

  於是按照原本的策略繼續想 pD,先把 flow min-cut 什麼的先從腦海裡撇掉,都想了那麼久了還是沒想到什麼,那應該不是 flow 題吧@@ 改從簡單的 case 想:如果已知 A 組有某些數,那會發生什麼事呢?如果 A組已經有第 $x$ 張卡,那麼所有 $x$ 會贏的卡片也得在 A 組!於是每新加入一些卡片時就可以再根據新加入的卡片決定哪些卡片還得加入!直到沒有必要再加入卡片時,這些 A 組的卡片就是再包含 x 卡片下的最小集合!所以枚舉一剛開始 A 組至少有哪張卡片,就可以搜出 B 組的最大 size,這樣的話複雜度是 $O(N^3)$,要平行的話也很好平行,A組不同的出始卡片交給不同的 Node 去執行就好了。但是這個做法並無法 AC 大測資,因為此做法每個 Node還是得讀入所有 input,但大測資光讀入就 TLE 啦!但我還是決定先快速的把小測資 AC一下。

  小測資 AC 後,比賽剛好勝兩個小時,我依然繼續思考 pD 的大測資要怎麼解決,過了幾十分鐘,我終於意識到這題根本就是 SCC 問題 = =,當下覺得好蠢啊.. 在一般的演算法比賽我不會花那麼久時間才注意到它只是 SCC 吧?把它變成 SCC 問題後,平行前的複雜度就降到 O(N^2) 了,但 SCC 要怎麼平行呢@@又卡住了 Orz

  不對,光是 SCC 還不足以展現這題的所有 feature,並沒有用到競賽圖的性質,一個競賽圖的 SCC會長怎樣呢?SCC縮點後會長成一個 path!我們只要找出此SCC的最前端的強聯通元件的 size,就能解出這題了!也就是說... 我們要找出dfs 離開所有點的順序?若能找到一條通過所有點的 path 的話事情就好辦了... 但這樣的 path 有那麼好找嗎?或者是說,這樣的 path 一定存在嗎? (此時完全忘記以前根本就有看過找出競賽圖上通過所有點的 path 的演算法....) 不不不要再深入的想下去,認真說起來,就算找到path還是得讀入很多邊,很麻煩的,有沒有什麼可以不每個Node都只讀完某些點的所有連出去的邊的方法呢?只讀完連出去的所有邊我們能獲得什麼資訊?我們能知道每個點的 out degree!out degree 在這個問題有什麼作用?B組的所有點都會連到 A組,所以B組的所有點的 degree嚴格大於 A 組所有的點的 degree!

  總覺得我快要接進答案了 >_< 在繼續絞盡腦汁吧 >_< 也就是說若把所有點按照 outdegree 排序,A、B組的分法一定會恰巧把此序列切兩半?所以如果我們已知 A 組有某個degree為 $v$ 的點,那所有其它 degree 小於 $v$ 的點也一定在 A 組?如果一個點 $x$ 在 A 組,它所有憐到的點也會在 A 組,但我們就只要關注 $x$ 連到的點中 degree最大的那個點就好了!?如此一來若點 $x$ 在 A 組,$x$ 連到的點 degree 最大的是 $v_x$,那麼所有degree小於 $v_x$的也必須在 A 組!於是我只要知道每個點的 degree,和每個點所連到的點中最大的 degree,就可以解這題了!

  接著是思考要怎麼平行,其實也沒有什麼好思考的啦,就每個 node 各字計算完自己所分配到的點的 out degree,在把這些資訊互相傳給所有 node,每個 node 再計算所有點連到的點中最大的 out degree,然後再把這些資訊都傳給最後一個 node,剩下的事情就交給最後一個 node 做。

  我在比賽開始後 2 時 19 分左右寫完大測資,測了一下 Sample 並修了一些 bug 後 AC  sample 了,於是我就把它 submit上去,同時我也順手把新的 code 傳上小測資,保險一下確認是否能 AC 小測資,但是,兩分鐘過去 judge的結果傳回來了,我竟然 WA 掉了!?WHY !!!

  我在認真重測一次我的 code,然後發現....我的 code 每次執行結果可能不一樣 = = 這世在搞什麼@@ nodes 間傳遞訊息出了問題?我對 google 提供的 api 還理解有誤?於是我又花了將近 20 分鐘把 code 改成我比較肯定的寫法,多測幾次每次結果都一樣後才 submit,也順手再傳一次小測資,這次兩分鐘後得到的結果是 AC,那大測資應該也沒問題了吧@@。

  比賽只剩下 23 分鐘,我的名次好後面... 六十幾名的樣子?看來進前十是沒望了吧?勝下這點時間我還能做什麼嗎?寫 pE小測資?還是寫 pC 小測資? pE小測資分數比較低,而且我連題目都還沒看,所以還是寫 pC 小測資得得分期望值比較高?但... pC 小測資要怎麼做呢@@

  雖然之前已經讀了題目,但還沒認真想過,乍看之下覺得有點難耶?但仔細想過後發現就只是個 dp 而已 0.0,於是我就很拼命的寫 code,在剩下五分鐘的時候把 code 寫完,但我並沒有那麼神的一次就把Sample AC。

  剩下的時間我就邊 printf 中間過程邊修正一些邊界加減一的 code,在剩下一分鐘時總算把 Sample 1 AC了。此時我另外兩個 Sample 都還沒下載下來傳到工作站上 (在強調一次,我是使用我的筆電,作業系統是 windows,使用pietty 連工作站用 vim 寫 code,檔案是用 FileZilla 互傳) ,在測完剩下兩個Sample可能就來不及 submit了 @@但更重要的是:若我真的測出 bug ,我幾乎沒有時間修正 bug後測試在上傳吧...?所以我就直接 submit 上去了 >_< submit 時間是比賽結束前 42 秒。

  在比賽結束過後一分鐘左右我得到 judge結果,我竟然  AC 了!!! 好感動喔 >_<,雖然 AC了,但我的排名仍就是 49 名這種怎麼看到沒機會 Judge 後前進到前十名的名次,呵呵呵,但我已經盡力了吧 >__< 在最後 1 分鐘內 AC題目耶 >_< 雖然只是小測資而已 >_< 這時系統發出公告說:大概兩三個小時後才會公佈 judge 結果。

  我就在電腦前枯等了兩個小時(?) 看了移下大家在 Codeforces 上的討論,原來 pD 只需要每個點的 out degree 資訊就得到答案啊... 所以我求出每個點連到的所有點的最大 out degree 只是多此一舉嘛 OAQ 修練還不夠啊 >_<

  這兩個小時左右我大概每幾分鐘就去 score board 按 F5一次,某次按的時候看到分數出來了!馬上瞄郭去前幾名,咦咦咦第一名竟然沒有出破台!?哇 shik 第三名耶!那我呢...於是我把頁面拉到最下面(因為 code jam若該使用者沒有出現在該頁,就會把該使用者放在最前面或最後面),咦?為什麼沒看到我?我在仔細看移下前三十名的頁面...咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦咦!???????????????????騙人的吧我第十名?咦咦咦咦咦咦???四十九名 judeg 後變成第十名究竟是發生了什麼事 >_< 嗚嗚我腦袋當機了 >_<這是整人計畫吧,過一個禮拜後我就會收到:對不起我們不小心把你的 code judge 錯誤了的通知吧 >_<啊哈哈哈哈 ....

  四天過後 Final 的邀請信正式寄到了,看來這是真的 0.0 嗚嗚嗚獲得參加 DCJ 的 final資格一點也不會開心啦 >_< 我真正想參加的是普通的 Algorithm Round 的 final 啊 >_< 嗚嗚嗚嗚

2015年6月18日 星期四

2015 Google Code Jam Round 3 參賽紀錄

  這已經是我第七年參加 Code Jam了,並且是連續第五年進入 Round 3,雖然乍看之下我可以很穩定的進入 Round 3,但離進入 Onsite Round 還是差好遠啊... 好似已到達了自己的極限,難道沒有辦法有哪一年來正正常常的去一次 GCJ 或 TCO 的 Onsite Final 嗎 >_< 像去年那樣因為出很多SRM題而被邀去現場的機會沒有也沒差啦 >_< 一直以來的夢想都是身為參賽者好好的去現場比賽,而不是只是去觀戰啦 >_< 好啦碎碎念到此... R3 就要開始了。

  看了一下今年題數和每題題分,今年總共有五題!?以前從來沒有那麼多題過吧!(事後證實這是我開始參加GCJ以來頭一次,以前都只有四題) 題分總和依序是 12、13、23、25、27。這是有兩題水題,讓基本分提高的意思嗎?看來前兩題是一定要得分了,於是我從第一題開始看。

  第一題是給一個 Rooted Tree,每個 Node 都有一個值,我們要找出盡量多的與 Root 連通的 Node,使得這些 Node上的值最大與最小的差不超過 D。數據是使用 Random Seed 產生的,小測資 $N \leq 1000$、大測資 $N \leq 10^6$ ,大測資 $N$ 那麼大啊... ,看來若要使用 dfs 要小心了 (有記得之前 Facebook Hacker Cup 的教訓)。

  小測資讀完題就知道怎麼做了,枚舉所有被選的 Node 的可能區間,從 root 去 dfs 看看最深能到哪,並把走過的點都選起來。大測資的話.... 嗯... 動態樹可以解決吧...? 可是我不會動態樹,並且也沒有動態樹模板 OAQ 但我還蠻相信這題有很簡單的作法的,於是繼續想下去,是說 ... 這真的事最簡單的一題嗎 >_< 這也太難了吧!!!以前的 GCJ 每個 Round 的最簡單一題我幾乎都能看到就知道怎麼做吧 @@

  十分鐘過去,終於有第一個人傳了 pA 大小測資,是 在 IOI 勝過 tourist 的昔日最強中國高中生 WJMZBMR m(_ _)m,唔唔唔,看來至少這題在 coding 速度而言在想下去投資報酬率是 OK 的吧?想到了應該能很快寫完。

  嗯... 這題八成還是要枚舉過所有可能區間,重點就是當枚舉某個區間時,匯有某些 subtree 的點會全不排除在外,也就是要知道每個點在什麼時候會被當成 subtree 的 root,一個點要被當成 subtree 的 root,代表他的所有祖先都有被選到,也就代表該點的值,要不是筆所有祖先的值都還小,就是比所有祖先的值都還大!嗯!這樣子再下去就能做出來的感覺!於是我決定值接開始寫 code了,邊寫邊想,並且先順手寫了一個 $O(N^2)$ 的 code 來作樸素對拍。

  大概三十多方鐘時我把能處理大測資的 code 也寫完了,但是對了一下小測資的答案和 $O(N^2)$ 的方法不一樣 OAQ Why OAQ 於是我開始漫長的 debug,時間消耗的很快,比賽已經經過了一個小時,我仍不知道我的 code 錯在哪。

  唔唔不行啦 OAQ 比賽只剩下一個半小時,而我就只為了這僅僅的 9pt 卡在這,這不是明擺著沒救了嗎?於是我捨棄了想找出 Bug 的心情,決定先搶搶其它題小測資的分數,順勢看看有否可以有所作為的題目。看了一下 score board, pD 的小測資應該是其它所有題目最簡單的吧?

  讀題...讀題...讀題... (卡住的狀態)。可惡啊,是因為前一個小時比不好太焦慮了嗎?為什麼 pD 最後關於符合條件的答案時要選擇哪組答案輸出的條件我怎麼反覆看幾次都還是看不懂 @@ 這題不過就是那個有n個數,給任兩個數得和的 set,還原這 n 個數的變型吧?感覺作法就應該會差不多嘛。看了一下小測資的條件:所有數都非負。在這個條件下肯定是唯一解,所以那個多組符合的答案要優先輸出什麼就不必管了 >_<,所以就快速把小測資 AC 掉。

  已過 1 小時 17 分。AC 掉 pD 的小測資後,由於還是不懂多組答案要優先輸出什麼,所以就決定先捨棄大測資,去看 pB。讀懂並想了一下後 ... 唔...感覺上小測資沒有比較簡單的方法啊?雖然我想到了一個作法,可是這個做法應該並不簡單耶...? 唉唉唉不對啦,這個作法連大測資都可以在時間內跑完啊 = =,於是這題就直接寫大測資了,邊界加減一的地方稍微卡了一下,但還算蠻順利的就 AC 了小測資,這題小測資過了感覺上沒道理不過大測資,就直接傳了。

  已過 1 小時 40 分。若有心還想進 final 的話... 我現在應該要...唔怎麼想都覺得沒救啦 >_< 從 score board 看來,A、B、D三題都 AC的人將會滿街都是,而在我 pA 沒有大測資的分數情況下,一定得靠 C 或 E來追分吧?稍微看了一下 C,感覺題目好常似乎會不好懂 0.0,於是反回看 pC。

       pC一臉就 O(N^3) dp 樣吧?可是...可是...他的順需要怎麼排?想必不能值接按照最初的座標順序排呀,那按照速度關係排呢?唔...感覺上不好想 or 要想清楚不簡單耶 ...,那就還是先把小測資水一下吧。

  小測資 $N \leq 25$,第一個閃過去的作法就是 O(N^2 * 2^N) dp,但 N 高達25耶 ...,我沒把握四分鐘跑的完,於是再多想一下,嗯...枚舉每追到一個寵物後,下一步要往左追還是往右追,這樣的話就是 O(N * C(N,N/2)),這個複雜度就很 OK 了!之後順利的把 AC 小測資 AC了。
  比賽經過 2小時 4 分鐘,還剩下 26 分鐘, C 和 D 的大測資感覺上都不太能在剩下的時間處理,而下就算處理完得分也不夠高,不足以逆轉結果。最後能拼的就是在剩下時間把 pE 小測資連同大測資一併解出了吧 OAQ。

  又經過了十分鐘,我還是沒有把 pE 題目看懂 OAQ 看來這場已經註定沒救了啦 OAQ 就算大家大測資都 fail,我小測資也沒有寫的比別人快啊!剩下 15 分鐘我還能做什麼呢?

  雖然心以死,但是我還是盡可能的利用剩下時間吧,回去 de pA 的 bug。在比賽剩五分鐘的時候發現我哪裡想錯了,而且只是發現哪裡"想錯",並還沒想到要怎麼改才是"對的",五分鐘覺對不夠用了啦!

  比賽結束,小月(Kirino)排在第 123名 (其實我覺的沒進 final 的話第幾名都不是很重要,因為我只要使用快速讀完所有題目並把所有看得懂題目的小測資都先做,名次一定不低啊?),結束了今年度的所有賽事(雖然 TCO 今年只取 12 個...我覺得值接認命去當兵吧 0.0),今年也是一事無成啊 OAQ

        恭喜皮皮 (peter50216) 總算是進到 GCJ 的 final,過去好多年雖然皮皮都在 Round 2表現超好,可是他在 Round 3都非常可惜 >_< 也恭喜新竹實驗中學的 betaveros ,在高中就進到 top 25超厲害的 >_<,還有凱琪也排在第三十名,之前有候補到 30 名以後,今年前 25 名也有好多無法去 final 的未滿 18 歲的人,說不定有機會候補上>_<

唔唔後年再加油吧 >_<

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