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

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

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

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

01 USACO計算機(jī)學(xué)術(shù)活動的簡介

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

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

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

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

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

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

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

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

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

考試形式：

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

計分方式：

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

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

比賽的計時形式是什么？

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

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

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

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

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

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

關(guān)于Division specific topics:

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

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

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

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

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

07?USACO計算機(jī)學(xué)術(shù)活動的報考指南

適合學(xué)生：

任何對編程語言有中級知識的學(xué)生都可以參加比賽。可能學(xué)生會覺得很難，但嘗試挑戰(zhàn)不會有什么壞處，可以按照自己的程度不斷挑戰(zhàn)提高！當(dāng)參加比賽時，可能會學(xué)到比你以前知道的更多的東西，從而在下一輪比賽中取得更好的成績。無論你的成績?nèi)绾?，你仍然可以在你的履歷或大學(xué)申請資料中體現(xiàn)而超越競爭對手。

何時參加比賽：

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

如何參加比賽：

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

比賽報名費用：

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

參賽形式：

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

學(xué)術(shù)活動獎項：

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

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

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

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

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

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

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

白銀級：Date Structures,Prefix Sums,Binary Search,Graphs,etcAP CS A 會涵蓋50%的主題項目

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