USACO全稱USA Computing Olympiad
http://www.usaco.org
本文有幾個(gè)故事，如果你留意，故事中會(huì)有一些對(duì)孩子學(xué)習(xí)編程非常有價(jià)值的福利。這些是發(fā)生在我身上的故事，一切要從2017年的冬天講起。
大亮老師曾經(jīng)是一個(gè)程序員，從業(yè)近20年，20年的職業(yè)生涯中，我寫過各種各樣的程序，開發(fā)過各種各樣的軟件，從桌面軟件到網(wǎng)站到手機(jī)上的游戲，可謂見多識(shí)廣經(jīng)驗(yàn)豐富。然而，從編程算法的角度來看，我這20年從來沒有碰到信息學(xué)競賽這樣高難度的挑戰(zhàn)。
我的信息學(xué)奧賽入門就是2017年在USACO的在線訓(xùn)練營學(xué)習(xí)和刷題開始的，當(dāng)時(shí)是很偶然的，看了國內(nèi)外很多的刷題網(wǎng)站，最終看上了這個(gè)土土的USACO在線訓(xùn)練營，一股互聯(lián)網(wǎng)1.0時(shí)代網(wǎng)站的味道。憑直覺知道這可能是個(gè)深藏不露的地方。果然，網(wǎng)站內(nèi)容組織很好，面向所有人開放，不關(guān)心你是誰，只有你和前方一片知識(shí)的海洋，哦不，應(yīng)該是前面一座知識(shí)的雪山，它不撩你，也不拒絕你，靜靜的，很佛系，愛來不來。我受不了這種，就開始了。
在線訓(xùn)練營的地址是這個(gè) https://train.usaco.org
是的，這么一個(gè)首頁，連網(wǎng)頁內(nèi)容居中，他們都懶得弄。
注冊的時(shí)候不用輸入密碼，太極客范了，這個(gè)設(shè)計(jì)師他肯定猜到你不打算認(rèn)真選擇一個(gè)八成會(huì)忘記的密碼，所以干脆，生成一個(gè)密碼發(fā)到你的郵箱。
進(jìn)入訓(xùn)練站，網(wǎng)頁頂部有個(gè)位置顯示了全世界多少人同時(shí)在線，也就是十幾個(gè)的樣子，這感覺挺好，爬雪山的你不是一個(gè)人，足夠緩解你的孤獨(dú)感。當(dāng)然，網(wǎng)站并不提供這些人都是誰，也不會(huì)顯示誰做了多少題拿到多少分，這是我最欣賞的地方，這個(gè)網(wǎng)站是有設(shè)計(jì)的，設(shè)計(jì)就是選擇，做出選擇很簡單，源于網(wǎng)站的世界觀：你來這里，是來面對(duì)題目挑戰(zhàn)的，是來提升自己的，不是來看別人的。
所以安排在更明顯位置的內(nèi)容，是你要面對(duì)的下一個(gè)問題。嗯，我的下一個(gè)問題是我媽媽的牛奶，Mother's Milk。
告訴你一件事，這個(gè)網(wǎng)站的題目都是一個(gè)叫做約翰的農(nóng)夫(Farmer John)和農(nóng)場以及他的奶牛的故事，這一點(diǎn)確實(shí)暴露了美帝是個(gè)大農(nóng)村的真相。
記住，你是來接受專業(yè)信息學(xué)訓(xùn)練的，忽略這些花邊，開始學(xué)習(xí)吧！
整個(gè)訓(xùn)練分成6個(gè)章節(jié)Chapter，每個(gè)Chapter又分為幾個(gè)Section，每個(gè)Section里面有一些講解（圖文，沒有視頻）和一些題。你必須通過了前面的題，才能解鎖下一個(gè)。
訓(xùn)練課程體系，循序漸進(jìn)，組織合理
好吧，我Chapter1還沒畢業(yè)，慚愧10秒。我完全可以說18年下半年太忙了，其實(shí)不是，真相令人淚目。
Chapter1介紹了搜索算法，一開始是暴力法(Brute Force)，暴力法思路簡單，就是把所有可能都試一遍，比如你的6位數(shù)字的銀行卡密碼，挨個(gè)嘗試，計(jì)算機(jī)只需要一瞬間就試出來了。有一首歌的歌詞，一定是一個(gè)程序員寫的：在一瞬間，有一百萬個(gè)可能……
一百萬是7位數(shù)，其實(shí)你把密碼改成9位數(shù)字，也是一瞬間，所以說，當(dāng)銀行卡余額的位數(shù)還沒有銀行卡密碼位數(shù)多的時(shí)候，真的不用太操心這個(gè)密碼的問題，沒必要。
Chapter1接下來講了貪心算法(Greedy)，深度優(yōu)先搜索，寬度優(yōu)先搜索……他們反反復(fù)復(fù)的提到一個(gè)概念：算法復(fù)雜度，很快我發(fā)現(xiàn)其中出現(xiàn)了可怕的符號(hào) O(logN) ，這讓我意識(shí)到，關(guān)于指數(shù)、對(duì)數(shù)的數(shù)學(xué)知識(shí)好像已經(jīng)，忘卻了，于是我停了下來，回去補(bǔ)習(xí)數(shù)學(xué)了。
這就是令人淚目的真相，我得補(bǔ)習(xí)數(shù)學(xué)才能理解教程中講的內(nèi)容。
每次家長問我，您教C++信息奧賽班嗎，我就很自信的回答：不，我教不了，真心的。如果家長繼續(xù)追問，為什么呀，不可能呀，我就很自信的回答：因?yàn)槲覕?shù)學(xué)很渣。
我們信息學(xué)的擔(dān)綱老師：老喬，小麥，文婧，明?！瓟?shù)學(xué)奧賽都是拿過一等獎(jiǎng)的。
其實(shí)我也差點(diǎn)拿過數(shù)學(xué)競賽的一等獎(jiǎng)，那是在初中，我代表我們礦山子弟學(xué)校去參加了一個(gè)數(shù)學(xué)競賽，參賽的同學(xué)有很多來自當(dāng)?shù)孛Ｒ恢械耐瑢W(xué)，我記得有一道題是：一個(gè)正方形用剪刀剪一刀之后結(jié)果是幾邊形。這個(gè)題我太擅長了，我從小最喜歡的就是用剪刀剪紙的手工制作。這場考試結(jié)束后，我自我感覺良好，但可能名校同學(xué)沒發(fā)揮好。后來我聽我們數(shù)學(xué)老師說，舉辦方不太滿意考試結(jié)果，決定再考一次！ 我不知道真相哈，也不打算檢舉揭發(fā)誰哈。但這是我距離數(shù)學(xué)一等獎(jiǎng)最近的一次。
不如還是來看看我的媽媽的牛奶的問題吧。
這類問題有幾個(gè)特點(diǎn)，請(qǐng)注意
1 第一遍通常不知道題目要干啥，辦法，多讀幾遍。
2 把題目給的示例搞清楚，在紙上寫寫畫畫的，弄明白題目是第一步。
3 找到問題的解法或快或慢，我有個(gè)題最長用了3天才想明白怎么干，如果你并不比我聰明，那就像我一樣有耐心。
既然不能通過就不能去下一題，好吧，讓我們看看我們最遠(yuǎn)可以走到哪里。作為一個(gè)不聰明的人，不放棄是唯一可以依靠的東西。
本來打算年底假期有空了再回來刷題，好巧不巧，趕上了選拔賽！
現(xiàn)在是時(shí)候介紹一下USACO的官網(wǎng)。然后給您講講我參賽的悲催故事。
官網(wǎng)：http://www.usaco.org
嗯，官網(wǎng)的賬號(hào)和訓(xùn)練營的賬號(hào)，不是一個(gè)賬號(hào)，兩個(gè)網(wǎng)站不共享賬號(hào)，這點(diǎn)也很偷懶，我忍了，并借機(jī)注冊了一個(gè)很有錢的名字：Jack Fang。
網(wǎng)站封面 http://www.usaco.org
網(wǎng)站首頁的右側(cè)，顯示了2018年-2019的日程表，毫不起眼，但是雷霆萬鈞。
這一系列的活動(dòng)，最終指向2019年在阿塞拜疆舉辦的IOI（國際信息學(xué)競賽）。
所以有必要放大了看看。
我趕上的，就是18年12月14-17號(hào)舉辦的1試（First Contest）。具體情況一會(huì)再說。我先介紹一下，這一系列的比賽，對(duì)家長有什么意義。
假設(shè)您家里有兩個(gè)男孩，哥哥是美籍，弟弟是中國籍，別問為什么，我還真認(rèn)識(shí)這樣的。
他們都是高中生，哥哥在美國，他參加USACO First Contest，Second Contest, Third Contest比賽不斷晉級(jí)，然后在3月底參加US Open（全美公開賽），獲得了參加訓(xùn)練營(Training Camp)的機(jī)會(huì)；5月底他來到Clemson University，和全美的其他編程高手歡聚在一起，由競賽專家專門進(jìn)行培訓(xùn)指導(dǎo)，幫助選手們進(jìn)一步提升水平，最終在訓(xùn)練營的考核中脫穎而出，入選美國國家隊(duì)(USA IOI team)，代表美國，參加8月份的國際信息學(xué)競賽。
所以現(xiàn)在您知道了，這是一個(gè)美國國家隊(duì)的選拔體系，牛不牛。
現(xiàn)在說弟弟，他是中國國籍，在中國上學(xué)，弟弟也酷愛編程，經(jīng)常和哥哥一起討論難題。他在中國參加NOIP，成績不錯(cuò)進(jìn)入省隊(duì)，參加全國賽（NOI），參加NOI冬令營，進(jìn)入國家集訓(xùn)隊(duì)，最后在5月份通過國家集訓(xùn)隊(duì)的選拔，也進(jìn)入了國家隊(duì)，代表中國，參加國際信息學(xué)競賽。
最終，兄弟倆相遇在國際信息學(xué)競賽的賽場，同場競技，完美。
這里的福利在哪里呢？ 弟弟，不用報(bào)名，和我一樣，用Email注冊一個(gè)賬號(hào)，就可以參加美國的比賽來檢驗(yàn)自己的水平，只是最后沒有資格參加訓(xùn)練營的選拔而已。 在這些方面，您不得不服老美在公平、開放方面，有一種令人欽佩的精神力量。
2019年2月22日的晚間，弟弟收到了哥哥的消息，說今年的第3試開始了。哥哥之前已經(jīng)晉級(jí)了金牌，這次比賽直接挑戰(zhàn)白金級(jí)別的題；弟弟上次晉級(jí)到銀牌，這次登錄，首先面對(duì)的是金牌級(jí)別的3道題。
比賽沒有統(tǒng)一的開始時(shí)間，在比賽時(shí)間窗口（2月22到2月25日）內(nèi)，每個(gè)人有4個(gè)小時(shí)，完成3道題，如果得分足夠，將晉級(jí)下一階段。
這次比賽對(duì)弟弟來說有點(diǎn)挑戰(zhàn)，因?yàn)檫@次的題目沒有提供中文翻譯。好在弟弟的英語水平還不錯(cuò)，順利讀懂題目只是多費(fèi)了點(diǎn)時(shí)間。
我曾經(jīng)疑惑，這樣一個(gè)無人監(jiān)管的比賽，作弊也太容易了吧，弟弟把哥哥的代碼要過來，提交，通過。
這樣的話，成績有什么權(quán)威可言呢。
對(duì)于心存僥幸的同學(xué)，我的忠告是仔細(xì)看看下面這段，大意是：自己做題，不能團(tuán)隊(duì)做，不能請(qǐng)教別人，不能用以前自己寫的代碼，不能用別人的代碼，不能網(wǎng)上搜代碼，別注冊兩個(gè)號(hào)來玩，考試進(jìn)行期間不要公布自己的代碼……
如果你非要這么做，犯規(guī)的成本是極高的：終身禁賽，沒有第二次機(jī)會(huì)。
還想憑自己的比賽成績申請(qǐng)美國的學(xué)校，別想了。
遵守競賽規(guī)則，尊重自己，是從事高科技活動(dòng)：編程的小朋友應(yīng)該具有的文明素養(yǎng)。
講講我是如何被比賽題目虐的死去活來的吧。
2018年12月，我參加了USACO的First Contest，順利通過了銅牌，最終折戟銀牌。
銅牌考察的是編程基礎(chǔ)知識(shí)，語言結(jié)構(gòu)，簡單的數(shù)據(jù)結(jié)構(gòu)知識(shí)。正常學(xué)完了我們P1階段的同學(xué)，完成銅牌第1，2題的知識(shí)是足夠的（有些班進(jìn)度稍慢要到P2）。所以這學(xué)期我們安排部分P1階段同學(xué)做銅牌第1題，用來檢驗(yàn)自己的學(xué)習(xí)水平，有的同學(xué)可以順利通過，有同學(xué)經(jīng)過掙扎能夠通過，部分高水平同學(xué)能通過第2題，挑戰(zhàn)第3題。
每個(gè)題包括了10個(gè)測試案例，如果都通過了，就全是綠色。
每通過一個(gè)測試，會(huì)得到一部分分?jǐn)?shù)。
銅牌3個(gè)題都完美通過之后，我得到1000分，晉級(jí)下一輪。真是喜悅呀。
抱著必死的決心，我在當(dāng)天傍晚接著開始了銀牌的挑戰(zhàn)，又獲得了4小時(shí)的考試時(shí)間。
沒想到第1題這么難！讀完題之后完全不知道如何下手，真的。讀了半天題，不知道怎么辦。在籃球場比賽經(jīng)驗(yàn)極其豐富的我，果斷開始下一題。第2題還行，有辦法，提交之后，過了7個(gè)3個(gè)超時(shí)。
什么是超時(shí)呢，就是你的C++程序需要在2秒內(nèi)得出答案，如果是Python程序是4秒的時(shí)間限制。
所以算法不僅要正確，還得高效。
做第3題的時(shí)候還剩2小時(shí)，讀完題我就笑了，這是一個(gè)消消樂游戲的消除算法。作為一個(gè)游戲程序員，這種算法搞不定還怎么編游戲？傳出去還不被同行恥笑？
題目并不簡單，我用了遞歸和深度優(yōu)先搜索，這和我編掃雷游戲的時(shí)候用到的算法類似，測試數(shù)據(jù)通過了，我自信滿滿的提交了代碼。系統(tǒng)開始判題，接著是殘酷的結(jié)果，只過了2個(gè)，8個(gè)錯(cuò)誤！當(dāng)時(shí)，真的不知道哪里錯(cuò)了，總覺得寫的程序，沒毛病啊，老鐵！
想想自己將近20年的程序員職業(yè)生涯，都在進(jìn)行著低水平的重復(fù)，如今竟然在一個(gè)消消樂游戲面前敗下陣來，內(nèi)心無比的凄涼。
想起有些同樣是程序員粑粑麻麻，認(rèn)為自己完全可以教孩子編程的，我就微微一笑不好評(píng)論了。
最終，銀牌考試得到了300分，750以上的可以晉級(jí)下一輪。
整體來看，銀牌會(huì)考察到貪心算法，搜索算法。我們的Python同學(xué)需要進(jìn)行專門的算法學(xué)習(xí)，才能搞定這些挑戰(zhàn)。
后記
幾個(gè)月之后，在2019年2月，大亮老師終于可以把銀牌的題全部做對(duì)。尤其第1題，從完全沒有思路，到產(chǎn)生了一個(gè)暴力法的解法，但是效率太低，然后放棄暴力法，考慮集合合并，又考慮集合拆分，實(shí)在無解了，最后請(qǐng)教小麥老師，用貪心+二分解決了第1題。
當(dāng)我把學(xué)到的知識(shí)編排在我們的Scratch課程體系中，編排在Python課程體系中，當(dāng)我向喬博士請(qǐng)教N(yùn)OIP課程體系，向小麥老師請(qǐng)教抽簽問題到底怎么優(yōu)化的，當(dāng)我上課的時(shí)候和孩子們分析冒泡排序的算法復(fù)雜度，討論二分查找的算法復(fù)雜度，我知道這一切改變是怎么來的。感謝名單中一定有USACO。
我還會(huì)繼續(xù)在USACO刷題學(xué)習(xí)和參賽，期待明年取得更好的成績。
今年如果非要給孩子們留下一句祝?；蚬膭?lì)，那就是：
永不放棄，死磕到底。
聯(lián)系客服
