real: 2010-08-17 Team Training

2010年9月2日星期四

(一些細節後補...)
2010-08-17 Tue
HKG Time - 1915 to 2415

CTLi is back!!

今天是首次 Full-team Training

Ehime 是日本賽區

日本的題目類別/特色包括：{普通、麻煩} × {暴力、Simulation、幾何}

表現還不錯
9 題之中
AC 7題

剩下兩題包括：

題 I (3D Geometry)
原本 CTLi 想出了一個非常漂亮的算法！
但由於抵受不住 jet lag
他沒有精神處理一些 degeneracy
提早回家 @@ (若否，Training 期間理應一定能解掉此題)
題 H (3D Geometry)
這題 Joe 之前已經 AC 過
所以把這題留到最後才開始 code (當時尚餘 1X 分鐘)

題A - ICPC 3185 The Balance
解(CTLi)： 擴展歐基里得算法 (Extended Euclidean Algorithm)

CTLi 面帶慚愧地說，平日的他寫 EGCD 時不會卡這麼久...

題B - ICPC 3186 Make a Sequence
解(Kn)： 簡單 Simulation

題C - ICPC 3187 Leaky Cryptography
解(CTLi)： Simulation (?)

CTLi 沒有想到可以直接讀入及輸出 16進制 (%llx)... 因而卡了一小段時間 orz

題D - ICPC 3188 Pathological Paths
解(Joe)： Simulation?

沒有參與閱題
這題卡了比較久

題E - ICPC 3189 Confusing Login Names
解(Joe)： 暴力枚舉 + Cut

一開始 TLE 了相當多遍
RP?

題F - ICPC 3190 Dice Puzzle
解(Kn)： 暴力搜索 + Cut

下了相當多決心去做...

(詳細搜索方法後補)

按：因為 AC 此題曾經一度感到非常滿意
可是，不久便發現 PKU OJ 上非常多人通過此題
所以 AC這一題並沒有甚麼大不了.....

題G - ICPC 3191 Color the Map
解(Kn)： 簡單2D幾何 → 暴力搜索 + Cut

題目有點長 @@
一開始以為是四色定理
再仔細閱題
才發現原來一個國家能夠擁有 > Disjoint 的 Polygon 國境

基於兩個原因，決定在比較前期做此題：

WA 了一下... 是因為打錯了某一個 variable

題H - ICPC 3192 Inherit the Spheres
解(Joe)： 3D Geometry (Sphere)

開始 coding 之時只剩 1X 分鐘，前面慢了，所以時間不足

題I - ICPC 3193 Crossing Prisms
解(CTLi 中途放棄)： 3D Geometry

(他想出一個簡單的算法... 後補...)

按：這曾經是一道我想了很久
依然覺得不論怎麼做還是極之麻煩的 3D Geometry 題目
Training 期間，CTLi 三兩下功夫漂亮地解決了

日本賽區傾向在題目提供較多極限數據
一旦通過 Sample，只要沒有TLE/RTE，通過的機率已經很高
所以... 在此情況下，有比較高的 AC rate 是理所當然的
另一個極端：大陸某些難題只提供僅此一個 N=1 或 2 的 Sample... 感覺比較...-___-
在 Code 之前，該停一停，想一想，有沒有必要花一點時間討論算法
在 Code 之前，宜先 estimate 一下 coding time
── 硬道理：Machine time == 最珍貴的 resource

real