21-22年USACO計(jì)算機(jī)競(jìng)賽全解

申請(qǐng)全球TOP大學(xué)無論是美國(guó)藤校還是英國(guó)G5都需要通過層層選拔，在眾多學(xué)生的申請(qǐng)資料中，如何才能脫穎而出？獲得全球重量級(jí)學(xué)術(shù)活動(dòng)金獎(jiǎng)或者優(yōu)異排名，幫助你成為閃亮的那顆星。而國(guó)際學(xué)術(shù)活動(dòng)的作用還不止于此，在學(xué)術(shù)活動(dòng)的過程中拓展相關(guān)領(lǐng)域的學(xué)術(shù)知識(shí)，讓參賽同學(xué)感受到學(xué)科的樂趣, 激發(fā)主動(dòng)求學(xué)的好奇心，并能與全球出類拔萃的學(xué)子們以公平的方式同臺(tái)競(jìng)技，以賽代學(xué)為未來打下扎實(shí)基礎(chǔ)的同時(shí)升華學(xué)術(shù)背景。

如今進(jìn)入一所你夢(mèng)寐以求的頂尖大學(xué)的競(jìng)爭(zhēng)程度比以往任何時(shí)候都要激烈。對(duì)于國(guó)際TOP大學(xué)看重的不僅僅是一份漂亮的履歷、優(yōu)異的常規(guī)成績(jī)或高GPA。招生官同時(shí)希望看到你的學(xué)術(shù)成就和豐富的課外活動(dòng)。這些活動(dòng)可以包括優(yōu)秀的暑期項(xiàng)目、學(xué)術(shù)比賽、志愿者項(xiàng)目和在你感興趣的領(lǐng)域的實(shí)習(xí)。USACO可以提升你申請(qǐng)任何一所大學(xué)的背景。那么今天就來全面剖析一下這項(xiàng)重量級(jí)賽事吧！

PART ONE --學(xué)術(shù)活動(dòng)介紹--

01 USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的簡(jiǎn)介

美國(guó)計(jì)算機(jī)奧林匹克(The United States of America Computing Olympiad)是為美國(guó)中學(xué)生舉辦的計(jì)算機(jī)編程比賽。USACO在學(xué)年期間為學(xué)生提供四個(gè)越來越難的水平的比賽:銅、銀、金和白金。USACO的參與者提交五種語言之一的程序:C、c++、Java、Pascal和Python。參與者通過在當(dāng)前部門表現(xiàn)良好而晉級(jí)。為期一周的夏季訓(xùn)練營(yíng)將從24名決賽選手中選出4名代表美國(guó)參加國(guó)際奧林匹克信息學(xué)學(xué)術(shù)活動(dòng)(IOI)。

02 USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的歷史

IOI國(guó)際信息學(xué)奧林匹克學(xué)術(shù)活動(dòng)是最負(fù)盛名的國(guó)際高中計(jì)算機(jī)學(xué)術(shù)活動(dòng)，由聯(lián)合國(guó)教育、科學(xué)及文化組織(教科文組織)于1989年發(fā)起，是根據(jù)其他幾個(gè)著名的國(guó)際高中奧林匹克學(xué)術(shù)活動(dòng)的精神設(shè)計(jì)的。1992年，威斯康星大學(xué)帕克賽德分校(University Of Wisconsin Parkside)的數(shù)學(xué)教授唐·皮勒(Don Piele)博士聽說了IOI，并成立了USACO，以便從美國(guó)帶來一個(gè)團(tuán)隊(duì)來參加這次活動(dòng)。參加1992年IOI的第一支美國(guó)隊(duì)是由國(guó)際計(jì)算機(jī)問題解決大賽的頂尖個(gè)人組成的。

在最初的20年里，USACO由Don、主教練Rob Kolstad博士和一支敬業(yè)的志愿者團(tuán)隊(duì)領(lǐng)導(dǎo)，他們中的許多人都是過去IOI的前美國(guó)隊(duì)成員。唐和羅布從管理USACO退休后，該組織目前由克萊姆森大學(xué)(Clemson University)計(jì)算機(jī)科學(xué)教授布萊恩·迪恩(Brian Dean)博士領(lǐng)導(dǎo)，并已經(jīng)在USACO工作了20多年。

03 關(guān)于IOI國(guó)際信息學(xué)奧賽

The International Olympiad in Informatics (IOI)國(guó)際信息學(xué)奧林匹克學(xué)術(shù)活動(dòng)是一項(xiàng)年度學(xué)術(shù)活動(dòng)項(xiàng)目，也是面向中學(xué)生的國(guó)際科學(xué)奧林匹克學(xué)術(shù)活動(dòng)之一。這是繼國(guó)際數(shù)學(xué)奧林匹克之后的第二大科學(xué)奧林匹克學(xué)術(shù)活動(dòng)，參與國(guó)家數(shù)量眾多。1989年在保加利亞普拉維茨舉行了第一次IOI。2021年的國(guó)際信息學(xué)奧賽則在新加坡舉行。

比賽包括兩天的計(jì)算機(jī)編程/編碼和解決算法性質(zhì)的問題。要處理涉及大量數(shù)據(jù)的問題，不僅需要程序員，還需要有創(chuàng)造性的程序員，他們可以想出程序員需要告訴計(jì)算機(jī)做什么。最難的部分不是編程，而是背后的數(shù)學(xué)。IOI的學(xué)生以個(gè)人為基礎(chǔ)進(jìn)行比賽，每個(gè)參賽國(guó)最多有4名學(xué)生參賽。

PART TWO? --學(xué)術(shù)活動(dòng)深度解析--

04?USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的考試形式及計(jì)分方式

考試形式：

USACO有四個(gè)學(xué)術(shù)活動(dòng) Divisions級(jí)別，Bronze, Silver, Gold,和Platinum。所有參賽者都是從銅級(jí)賽區(qū)開始的。在每個(gè)比賽賽周之后，如果參賽者有足夠高的分?jǐn)?shù)就會(huì)被“promoted”到下一個(gè)級(jí)別--通常是600-800分(滿分1000分)。你還可以在contest weekend中所有問題獲得滿分直接獲得晉升。每一組都比前一組困難得多。這通常需要相當(dāng)多的學(xué)習(xí)、訓(xùn)練，試圖提升到一個(gè)新的水平需要耗費(fèi)的時(shí)間，每一個(gè)等級(jí)長(zhǎng)達(dá)一年或更長(zhǎng)時(shí)間。USACO在2015年增加了Platinum級(jí)別。在此之前，每一個(gè)division的難度都比現(xiàn)在大，大約相當(dāng)于今天的division“one step up”。例如，一般來說，“old Bronze”問題最接近“modern Silver”問題的難度。

計(jì)分方式：

提交的3-4個(gè)程序中的每一個(gè)都要對(duì)10個(gè)或更多的“test cases”進(jìn)行測(cè)試——用已知的結(jié)果輸入程序中的數(shù)據(jù)集。您可以為每個(gè)給出正確結(jié)果的測(cè)試用例獲得學(xué)分。在一個(gè)contest weekend的比賽中，一個(gè)組別的所有問題總共有1000分。如果您的程序運(yùn)行時(shí)間太長(zhǎng)，占用太多內(nèi)存，或者崩潰，那么您將在測(cè)試用例中失去分?jǐn)?shù)，因此代碼的效率是一個(gè)因素!這在Silver及以上級(jí)別的賽組中尤其突出。

05 USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的考試計(jì)時(shí)形式

比賽的計(jì)時(shí)形式是什么？

在賽周的任何時(shí)候，進(jìn)入網(wǎng)站并點(diǎn)擊按鈕啟動(dòng)你的個(gè)人比賽計(jì)時(shí)器，時(shí)間為3-5個(gè)小時(shí)。出發(fā)前你會(huì)被告知確切的時(shí)間限制，通常是4小時(shí)。然后，選手將獲得學(xué)術(shù)活動(dòng)問題的訪問權(quán)限。

可以休息或提前停止，但一旦你在那個(gè)周末點(diǎn)擊了“開始”按鈕，你的時(shí)間就會(huì)一直在滴答作響，直到到期--不允許暫停。如果你只是想檢查一下題目，那么你可以隨意花時(shí)間嘗試它，想花多少時(shí)間就花多少時(shí)間。如果你的目標(biāo)是做好，試著提前計(jì)劃一整段時(shí)間，這樣你就可以不分心地工作了。

比賽開始后會(huì)發(fā)生什么？

在啟動(dòng)計(jì)時(shí)器后，會(huì)被允許回答3-4個(gè)問題(通常是3個(gè))，選手必須在個(gè)人時(shí)間窗口中解決。每一個(gè)都將提供一個(gè)背景問題，必須編寫一個(gè)程序進(jìn)行分析。在選手的時(shí)間窗口內(nèi)的任何時(shí)候，都可以通過網(wǎng)站提交您的程序進(jìn)行測(cè)試。選手可以在的時(shí)間窗口內(nèi)自由切換或返回到任何問題，并繼續(xù)提交解決方案，直到的時(shí)間截止或者選手覺得已經(jīng)全部完美為止。可以選擇在同一周末的任何時(shí)間使用新的計(jì)時(shí)器開始新部門的比賽。

06 如何選擇USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的語言

USACO接受多種語言主要包括Java、C++和Python。Java和Python提交的時(shí)間限制是C++的兩倍，因?yàn)樗鼈兊倪\(yùn)行時(shí)間更長(zhǎng)。然而，USACO官方描述并不推薦使用Python，因?yàn)樗倪\(yùn)行速度往往比Java慢，而且在某些情況下，即使是問題的最佳解決方案也可能無法在時(shí)間限制內(nèi)完成。發(fā)布在USACO網(wǎng)站上的解決方案供學(xué)生學(xué)習(xí)如何使用C++來解決包括大多數(shù)“training problems”在內(nèi)的老問題，但隨著時(shí)間的推移，Java已經(jīng)變得越來越流行。所以在為USACO編程時(shí)，有什么特殊的Java注意事項(xiàng)是我應(yīng)該知道的嗎？您可以導(dǎo)入與Java 8一起安裝的任何標(biāo)準(zhǔn)庫(kù)，例如java.util.*和java.io.*。您的Java文件必須使用“default package”；源代碼中不應(yīng)該有“包”行。完成問題需要讀寫文本文件。

關(guān)于Division specific topics:

青銅級(jí)別除法問題通常可以使用數(shù)組(有時(shí)是二維數(shù)組，有時(shí)也可以使用類或ArrayList)來解決。白銀組競(jìng)爭(zhēng)者應(yīng)該熟悉java.util包中的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)，如List/ArrayList、Set/HashSet/TreeSet、Map/HashMap/Treemap、Deque/ArrayDeque和PriorityQueue，以及比較器/可比接口。黃金組的競(jìng)爭(zhēng)對(duì)手往往不得不對(duì)自己的數(shù)據(jù)結(jié)構(gòu)進(jìn)行編程。C++的運(yùn)行速度確實(shí)比Java快，但USACO允許Java程序使用的時(shí)間是Java的兩倍。使用Java應(yīng)該不會(huì)出現(xiàn)無法在合理時(shí)間內(nèi)完成的問題。建議使用一種適合學(xué)習(xí)的語言。對(duì)于學(xué)習(xí)美國(guó)AP課程的學(xué)生來說，這種語言通常是Java。其他比賽可能有不同的設(shè)置，可能需要使用其他語言。真正的知識(shí)在于算法，而不是語言。學(xué)習(xí)C++是一個(gè)很棒的推薦，如果您有時(shí)間和動(dòng)力，鼓勵(lì)您這樣嘗試。

Java程序的內(nèi)存和時(shí)間限制是什么？

對(duì)于Java，每個(gè)輸入測(cè)試用例都被給予“大約”4秒的時(shí)間，盡管這在不同的問題或測(cè)試用例中可能有所不同。通常，對(duì)于最壞的輸入場(chǎng)景，粗略估計(jì)您的程序需要10億次或更多的“operations”會(huì)花費(fèi)太長(zhǎng)時(shí)間，而1億次或更少通常是可以的。介于兩者之間的任何地方取決于細(xì)節(jié)。

每個(gè)輸入案例都有“大約256MB”的內(nèi)存可供運(yùn)行。100萬個(gè)整數(shù)的數(shù)組僅占用4MB內(nèi)存(4字節(jié)*100萬)。假設(shè)有一種合理的數(shù)據(jù)存儲(chǔ)方法，時(shí)間限制幾乎總是內(nèi)存限制之前的限制因素。

PART THREE --學(xué)術(shù)活動(dòng)備賽指南--

07?USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)的報(bào)考指南

適合學(xué)生：

任何對(duì)編程語言有中級(jí)知識(shí)的學(xué)生都可以參加比賽。可能學(xué)生會(huì)覺得很難，但嘗試挑戰(zhàn)不會(huì)有什么壞處，可以按照自己的程度不斷挑戰(zhàn)提高！當(dāng)參加比賽時(shí)，可能會(huì)學(xué)到比你以前知道的更多的東西，從而在下一輪比賽中取得更好的成績(jī)。無論你的成績(jī)?nèi)绾危闳匀豢梢栽谀愕穆臍v或大學(xué)申請(qǐng)資料中體現(xiàn)而超越競(jìng)爭(zhēng)對(duì)手。

何時(shí)參加比賽：

USACO 每年有 4 個(gè)周末舉辦主要比賽。在從周五到周一的這些周末期間，學(xué)生可以選擇任何時(shí)間為該賽周啟動(dòng)他們的個(gè)人計(jì)時(shí)器。每個(gè)學(xué)生每個(gè)周末的時(shí)間通常是 4 小時(shí)，但有時(shí)是 3 或 5 小時(shí)。
每年賽季時(shí)間會(huì)有微調(diào)，但是大致差距不大，以21年賽季為例

如何參加比賽：

事先在www.usaco.org網(wǎng)站上注冊(cè)一個(gè)免費(fèi)賬戶。你不需要提前注冊(cè)一個(gè)具體的比賽日期！一旦您擁有帳戶，您就可以參與競(jìng)爭(zhēng)，還可以通過您自己的門戶訪問所有培訓(xùn)課程和資源。在網(wǎng)站上創(chuàng)建帳戶后，請(qǐng)登錄您的帳戶。如果是比賽周末，你會(huì)在首頁看到一個(gè)開始按鈕！

比賽報(bào)名費(fèi)用：

USACO 是完全免費(fèi)的，對(duì)任何人開放。只需注冊(cè)一個(gè)帳戶并進(jìn)行一些練習(xí)，就可以開始了。

參賽形式：

必須以個(gè)人參賽者的身份參加比賽，并且在比賽期間不允許與其他人合作。但是，您可以與喜歡的任何人一起學(xué)習(xí)和準(zhǔn)備！比賽規(guī)則詳細(xì)說明了官方學(xué)術(shù)誠(chéng)信準(zhǔn)則。

學(xué)術(shù)活動(dòng)獎(jiǎng)項(xiàng)：

USACO是沒有“prizes”的，但學(xué)生通過的難度學(xué)術(shù)活動(dòng)會(huì)獲得認(rèn)可鑒定，這將使您的名字列在您晉級(jí)的周末的比賽結(jié)果中。這個(gè)可以在任何大學(xué)申請(qǐng)的履歷上體現(xiàn)出來成為公認(rèn)的成就。

08 USACO計(jì)算機(jī)學(xué)術(shù)活動(dòng)備賽建議

學(xué)術(shù)活動(dòng)參考資料：

需要初步認(rèn)知這個(gè)學(xué)術(shù)活動(dòng)，建議首先在USACO官網(wǎng)上回顧過去的比賽，該網(wǎng)站提供了一系列學(xué)術(shù)活動(dòng)材料。這種比賽風(fēng)格通常被稱為“online judge”系統(tǒng)，你可以通過在線搜索找到許多例子。USACO官方還提供其他鏈接和資源的列表。

如何開始學(xué)術(shù)活動(dòng)：

選擇一種熟練的編程語言比如（推薦等級(jí)：C++>Java>Python），找尋大量拓展課題內(nèi)容，持續(xù)挑戰(zhàn)難題。初期的青銅及白銀等級(jí)，你需要對(duì)這些知識(shí)點(diǎn)做好儲(chǔ)備。

青銅級(jí)：Time Complexity,Basic Data Structures,Basic Complete Search,etc熟悉（Java/AP CS A class）語言項(xiàng)目就足夠

白銀級(jí)：Date Structures,Prefix Sums,Binary Search,Graphs,etcAP CS A 會(huì)涵蓋50%的主題項(xiàng)目

以上基礎(chǔ)準(zhǔn)備完畢后就可以開始選擇優(yōu)秀的導(dǎo)師指導(dǎo)，助力層層沖關(guān)晉級(jí)了。