21-22年USACO計算機競賽全解

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

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

PART ONE --學術活動介紹--

01 USACO計算機學術活動的簡介

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

02 USACO計算機學術活動的歷史

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

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

03 關于IOI國際信息學奧賽

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

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

PART TWO? --學術活動深度解析--

04?USACO計算機學術活動的考試形式及計分方式

考試形式：

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

計分方式：

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

05 USACO計算機學術活動的考試計時形式

比賽的計時形式是什么？

在賽周的任何時候，進入網站并點擊按鈕啟動你的個人比賽計時器，時間為3-5個小時。出發前你會被告知確切的時間限制，通常是4小時。然后，選手將獲得學術活動問題的訪問權限。

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

比賽開始后會發生什么？

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

06 如何選擇USACO計算機學術活動的語言

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

關于Division specific topics:

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

Java程序的內存和時間限制是什么？

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

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

PART THREE --學術活動備賽指南--

07?USACO計算機學術活動的報考指南

適合學生：

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

何時參加比賽：

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

如何參加比賽：

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

比賽報名費用：

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

參賽形式：

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

學術活動獎項：

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

08 USACO計算機學術活動備賽建議

學術活動參考資料：

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

如何開始學術活動：

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

青銅級：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%的主題項目

以上基礎準備完畢后就可以開始選擇優秀的導師指導，助力層層沖關晉級了。