【分享】IOI Camp 2019 一些O(1)的心得

所謂的 IOI Camp 就是”程式解題競賽集訓營”,由一群台大資工學生負責主辦的訓練營。
由於營隊期間網路上出現了 Fibonacci number 只需要 $O(1)$ 如此神奇的言論,現場學員都是圈內人自然就討論得相當熱烈,講師偶爾都還會拿出來消遣一下 XDDDD

時間過得真快,五天的營期(1/28-2/01)一下子就結束了呢~
雖然是台大主辦的解題訓練營,但據說參加的70位學員中有5x位是”國高中生” …對你沒聽錯,還有國中生(抖),而且各個實力堅強,在一些閒話家常中聽到來自不同領域的國手,包括數奧、資奧、甚至還有物奧,讓我回想起高中時代都在考卷堆中玩沙的日子,不禁想到這些擁有國手背景的高中看到的事物應該都不太一樣吧 : )

說實在,這次參加營隊看到參加學員一位比一位兇殘,讓我不禁懷疑自己是不是跑錯場了,嗯、事後證明我真的跑錯場了(掩面)。 而主辦方方面,自然都是台大資工人居多,而且還不少在程式競賽常看到的熟面孔,當然、這裡指的是在臺上領獎的常勝軍,那些不認識都難的等級www 總召更是去年ACM Taipei的隸屬於隊號1的”JAW”,有點像是報名營隊見見神人的感覺XDDD

這次有個小遺憾,那就是我感冒了QQ
我在營隊前一週就提早上台北,可能是溫差太大導致喉嚨就有點不舒服,結果反而太早去掛號看醫生,有些鼻塞、咳嗽都是隔天才發生,然後就一路咳到營隊結束都還沒好嗚嗚,對當時坐在身邊的學員感到抱歉 <(_ _)>

本次競賽使用的online judge是用 TIOJ,看得出營隊期間工人們都有在用心維護,有趣的是暱稱還可以用latex語法修改,所以看得到各種神奇的ID,各種玩上下標、顏色等等的公式梗。

下面就大概就概分五天簡單描述一下心得,至於課程內容我希望能簡單整理一份Note,算是作為高大競程一員去IOI Camp取經 (´・ω・`)

混了一張結業證書,然而這都是假象 ᕕ ( ᐛ ) ᕗ


Day 1

報到。
因為在進大學前的暑假我有去台大資工系館「德田館」上過幾次課,所以路線上不算陌生,報到稍微瞄過參加學員的名單…嗯 高大沒有人報上呢。雖然聽說有幾位學弟有報名,但似乎報名人數超乎預期還是沒成功進camp,另外唯一認識的就只有前中央霸主宇航哥,感覺他在競程的等級應該遠超過這次camp,所以合理懷疑是來拆台的(O)。

然後看著一群不認識的學員在互相認親,事後看FB心得才曉得原來很多高中生學員早在 IMO 或是 TOI 之類的場合就認識了,覺得自己被孤立只好硬著頭皮找旁邊的學員搭話0.0

OK, 我的團體賽的隊友是一位清大的大四生+實中的高一生,簡單介紹一下:
高一的同學很沈默,這幾天下來也看他一直在刷codeforces的題庫,努力聊一下才曉得他去年九月才接觸程式競賽,不過他的Rating比我高很多,程度進步到讓我hen害怕。
另一位清大生是位高手,團體賽靠他排名很前面,另外他似乎坐不住,時不時就突然消失跑到教室外面閒晃,常常去廁所的路上都會碰到XDDDD


上午是**Eddy時間**,算是朝聖codeforces紅人,畢竟他在我的追蹤清單內算出盡風頭(?)
從他的競賽經歷分享聽到不少有趣的事,附上我當下的筆記可以參考看看~

下午是**組合賽局**,自然又再一次提到Nim,讓我想起2016年參加交大PCCA寒訓的第一堂課,講到理論就是看台下各種硬撐(頭痛),從之後的練習題稍稍有抓到一點感覺,但大部分的題目還是推不出來啊…慘。

晚上是趣味賽,題目超多~ 23題分成除蟲題、駭客題、構造題、填空題。

不得不說出題方面很用心,從一些除蟲題可以感受到命題者的惡意(X) 親身經歷(O),還要求在edit distance的指定字數內完成修改。重點是有追加EX難度,也就是把題目設計和原題相同,但指定字數會隨著隊伍的最佳解再Rejudge,甚至逼到工人下場跟著打XDDD 像是pU遞增路徑應該rejudge有6,7次了吧,還有一題的edit distance從4字元一路下修成2字元,最後變1字元實在太神啦www

其中pI & pJ有讓我驚訝到,是個轉置矩陣的除蟲題(noraml & EX)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

int a[3636][3636];

int main(){
int n; cin>>n;
int sum=0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin>>a[i][j];
sum+=a[i][j];
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cout<<a[j][i]<<" ";
}
cout<<endl;
}
cout<<sum<<endl;
}

sample code 看起來完全沒有問題,畢竟只是簡單的 i,j 互換輸出,但全場這題的TLE數卻相當可怕,試過cin.tie()加速或是陣列倒存後原本也是要放棄的,我索性看看隊友其他AC的題目,然後發現某個除蟲題要把#define內的int8_t改成int16_t,所以我就嘗試把陣列改成int16_t居然意外壓線AC。
最後題解是因為int(int32_t)的3636*3636 array剛好卡在memory上限,導致輸入無論是cin還是scanf都會爛掉,在不曉得吃了鬼什麼的情況下就會持續跑到TLE,藉由改成short(int16_t)壓低memory,讓我一整個覺得很神奇!!!

最後 兩位隊友很carry,第一天團賽 11’AC、Rk’9 收場。
22點結束、23點到家,真的累 Orz


Day 2

上午是**數學**,講師不得不說真的很有趣XD
開場的視力檢查真的快笑死,一開始拿 < 來問開口方向就算了,後面跑出真的很鬧,還有一分鐘找快速冪的10個bug,結果最後有藏全形空白,笑死XD

主要講了很多關於數學的想法,數論的部分原本講到CRT(中國剩餘定理)Euler's formula 我還算是勉強可以理解,畢竟是競賽常會碰到的題目,但之後冒出什麼卷積解離散傅立葉轉換、FFT 就真的不太行了…回憶起工數的惡夢www 讓我不禁嚴重懷疑在場的高中生們究竟有多少人聽得懂呢(思)。

下午是**圖論**,在camp開始前的預備知識就已經要有DFSBFS的知識,所以開場講師補充幾個DFS的 tree edgeback edgeforward edgecross edge 後就直接開始介紹BCC(無向圖的雙連通) & SCC(有向圖的強連通)開始講,然後認識了TARJAN這個找割點的演算法,對於我這種圖論極慘的人好像有那麼…一點點的幫助(?) 不過後段講師有分享幾個經典問題都蠻印象深刻,例如 著色問題、2-SAT(我以前還嘗試用很多層loop硬爆XD)、一筆畫問題(Hamiltonian path)。

晚上是個人賽,我這三個小時寫到連助教都來關心,掛蛋真的太丟臉了QQ
但是那個pA的陷阱也太多了逆,給N個邊詢問是否可以湊成N邊形,可以輸出NO/不可以輸出YES,還在不明講的前提下給了一個input的驗證測試(如下code),簡單講測出來的結果就是輸入不一定是整數…有浮點數甚至還有負數wwwwww 心機hen重ˋ^ˊ

下面code表示出現數字九個以上就成立,但出題範圍只有到1000 >>>> 表示有浮點數可能。

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main(){
int t; cin >> t; assert(t == 1 || t == 37); while (t--) {
int n; cin >> n; assert(3 <= n && n <= 100000);
vector<int> v(n);
for_each(v.begin(), v.end(), [](int x){ string s; cin >> s; assert(accumulate(s.begin(), s.end(), 0, [](int a, char c) -> int { return a + isdigit(c); }) <= 9);});
}
cout << 0 << endl;
}

掛蛋自然就倒數那幾名,不放Dashboard獻醜了。
學到東西比較重要(但好像也沒學到多少XDDD)


Day 3

上午是**資料結構**,由總召大人擔任講師,不得不說課程內容和我以往接觸的資料結構差蠻大的,當初報名前看到預備知識包含 queue,stack,DFS,segment tree,hash,分塊,Treap,BIT(Binary Indexed Tree),二分搜 真的有嚇到,事實上從線段樹開始就已經不是我認識的資結了,僅限於聽過看過但還是不會用的樹 XDDD

課程集中在線段樹 & 切塊 & 分治,一路聽下來其實概念都不難,甚至還蠻有趣的(?),只是平常光是一般的tree都寫得亂七八糟,練習賽要把搜尋的概念應用在題目還是挺困難的,像是有個很經典的區間眾數(如下),如果用平常的思維寫下去應該 TLE 八九不離十,線段樹好強大> <

1
2
3
4
給定一個序列 $S_1 , \ldots , S_N$,接著有$Q$組詢問,
每次詢問$[L_i, R_i]$出現最多的數字出現幾次。

$(1 \le N,Q \le 10^5)$

下午沒有課程,直接團賽開打!
這回我就真的都在打醬油了,隊友太給力沒機會寫XDD 頂多幫忙讀長篇題目再講做法(某osu!題目計分題),另外值得一提的是總召出了一題如下,完全沒人想碰www 之後才知道要用13個DP解,幹!(嫌棄XD

晚上是題解時間,也就是這三天趣味賽、個人賽、團體賽的解說。
每個出題者都輪流上台解釋,從每個字裡行間不難看出他們的用心!而且還聽到了不少小知識,下面就簡單列出幾點~

  • 有些需要大量mod數字建議常數改成const減少%的速度

  • call by value & call by reference 注意

  • Day 1 提過 若array卡在memory上限可能會TLE

  • 駭客題解法: 1.認真看code 2.寫對拍程式測試

  • 善用srand的技巧可以hack (e.g. 生日悖論)

  • 題目限制不准用time(),結果出題者講完,就被其他講師拆台用邪門歪道可以解掉(鬧)

    • ??在c++會被吃成空白,/作為跳脫自元把預設換行吃掉,寫成下面這樣:

      cout << ti??/
      me(0) << endl;

    • ##在define作為concat會把前後字組合起來

      #define abc ti##me

  • <bits/stdc++.h>好用歸好用但要小心使用,例如有題構造題出現
    ______r(__a__b(_d___ _*_?_n_[_d__]__n)?_(_*_)__1__.____n__a_);
    在引入過程有個奇怪的header也會被引入…那就是<regex>,會把那串誤認成regex function而吃鱉。

  • 善用模板(e.g. Dinic’s Algorithm JAW-codebook)

  • 其他還有很多技巧,只是可能要搭配題目比較好懂就不贅述了~

照慣例附上 Day 3 團體賽的成績,兩位隊友依舊carry,以 5’AC、Rk’2 收場。


Day 4

上午是**網路流Flow**,聽完才發現其實有不少題目可以用flow解掉(前提要先想到是flow),而且我的graph非常有障礙,只能靠刷些裸題練練。課程內容不外乎是一些競賽會看到的最小割(Minimum Cut)最大流(Maximum Flow)最小點覆蓋…etc,然而不意外都會被我跳過不敢碰,下次也許可以嘗試寫寫看!

下午是**動態規劃**,也是我一直以來的罩門。講師從基礎開始講,甚至連專有名詞都講,讓我非常感謝!

  • 狀態 (n.):子問題、其形式與定義
  • 轉移 (v.):從子問題的答案計算原問題答案
  • 轉移 (n.):轉移的這個動作或方法
  • 滾動 :簡單來說就是把不會再被轉移的狀態丟掉,重複利用空間

不過後段就開始飆車了XD 分配上大概是兩小時基礎、一小時進階的概念,後段的證明完全無法聽進腦袋內,一直認為 DP 跟 greedy 是很吃感覺的演算法,如今也是只能刷題拼感覺了(?)。

另外這天的晚餐不同於之前的便當,居然是pizza + KFC!
感覺這類的營隊最後一餐都吃得特別好,應該是慣例了XD

晚上是個人賽… 嗯、除了pA時事題送分,之後就完全無解。
事實上Dashboard也很慘,只有14人寫出2’AC以上,最高還只有4’AC(全部8題)
也是一樣太爛就不放上來獻醜啦www 這幾天以來感受到精神上的疲倦了(#

另外有個小插曲是關於Day1~Day4問卷調查,結果有人似乎填了神奇的喵喵語,總召還特地拿出來翻(ㄒㄧㄚ)譯(ㄅㄞ),真的快笑死w


Day 5

最後一天的營隊。
一種名人見面會的概念,繼Day 1見到 eddy 後就是這天的講師 dreamoon ,兩位都是codeforces上厲害的臺灣coder,這天上午教的是**從枚舉到K短路**。

開場就在曬女友,不得不說打程式競賽打到有女朋友實在很令人羨慕啊,但連codeforces的handle都改loveXX實在太閃啦QQ 課程內容比起講義上的東西,聽到更多競賽經歷,但其實簡單講就是暴搜,結果看到投影片出現了我在 競程日記@FB 寫的爛code被dreamoon拿出來鞭屍XDDDDD 回憶起當時為了拼AC直接硬爆15層for loop,寫完真的頭hen痛,如今用遞迴跑就簡單許多(嘆)。

下午拍完大合照就是final團體正式賽了(5hr),還有亂入一隊工作人員隊「utaha」真的很刺激(?)
原本有一題看起來可以用字串反轉LCS的,結果我寫完發現隊友已經AC掉了…之後就真的躺到底QQ 反而高一隊友還解了2,3題(像是關鍵的nim變形),其他都是清大隊友寫掉,猛!!
其中有個物理的電學看到傻眼,腦袋開始回憶自己高中物理到底學了什麼公式,結果還現場重新推一遍頭痛,最後聽隊友用x,y分力算總和就行了= =a

雖然不是第一次打5hr的競賽,但我精神上還是很累(即便我躺得很兇),外頭的把廢實在是精神糧食,真的很好吃,不信放圖片給你看(扔

最後封板1.5hr留給開獎,結果最後一名意外爭奪得相當激烈(X)。

除了前三名的頒獎外,主辦方還加了奇怪的成就任務在裡面,像是全場尾殺、全場第3個AC/WA、全場33AC、全場第333非AC、最多WA隊伍,諸如此類,有一項「最會抓蟲隊伍」居然真的送捕蟲網XDDDD 實在黑人問號.jpg

之後就散會了,和這五天的隊友道別。
我還打包了一些剩下的把廢帶回家(抹臉)


總結一下,這次營隊應該算是接觸競程最挫折的一次QQ
連我去交大PCCA的進階組營隊都沒這麼慘烈(雖然一樣聽不懂w),可能對象都是國高中生的緣故吧,年齡層差到讓我有點來錯地方的錯覺,也讓我後悔太晚踏進這個圈子,何況進入圈子還沒好好認真打QQ 直到現在快要大四畢業還是跟廢柴一樣嗚嗚嗚。

在此
謝謝總召電仁
謝謝兩位凱瑞隊友
謝謝這五天營隊的講師們
謝謝在身邊默默協助的工人們
謝謝這群讓我看清實力界線的學員們
如果有緣希望未來還能繼續待在這圈子,之後World Final就靠你們啦(๑•̀ㅂ •́)و ✧

最後的最後 附上大合照結束這次營隊,聽說 O(1) 就要這樣比!?