USACO ( 美国计算机奥林匹克竞赛)是具有一定威望的国际竞赛。如果能在美国计算机奥林匹克竞赛 USACO中获奖,无疑是美国本科申请中提升个人背景的一大杀手锏。
什么是USACO?
USACO,全称为 United States of America Computing Olympiad(美国计算机奥林匹克竞赛)是针对美国中学生的计算机编程在线竞赛。
USACO根据难度分为四个赛段:青铜、银、金和白金,分别于每年12月、1月、2月和3月举办。
每次竞赛都会带来三到四个问题,参与者可以下载问题并在线提交解决方案。每个问题都需要编写一个程序来计算出一系列测试用例的正确答案。只有等于或高于入围成绩才能进入下一等级的比赛(满分或接近满分者直接进入下一轮,无需等待入围成绩的公布)。
USACO是一次算法竞赛,这意味着它需要提出创造性的、系统的方法来分析信息,而不仅仅是将程序的描述直接转换为代码。
比赛内容
参赛者可以在比赛窗口开放的任意时间段内参与,时长为连续3-4个小时,
USACO各个赛段的各个问题都允许以C、C ++、Java、Pascal和Python形式提交,选择其一即可。
问题本质上是算法问题,分数是根据程序在允许的时间和内存范围内正确计算的测试用例的数量计算的。(对于C,C ++和Pascal,每输入案例2秒;对于Java和Python,每输入案例4秒。每个赛段或问题可能有略微不同的限制)
需要灵巧的算法与数据结构才能正确地在时限内解决所有测试用例。
(1)青铜
青铜级别的问题通常可以使用数组(有时是二维数组)或使用ArrayLists及其他基本编程常识即可解决。此赛段的主要任务是适应USACO问题的复杂性以及熟悉解决问题的格式,只要求会至少一种算法语言。
通过USACO青铜赛段的学生需要非常熟悉以下概念:
· 变数
· 循环
· 有条件的
· 功能/方法
· 列表/数组
· 套装
· 字典/哈希图
(2)银
在解决问题和简单算法(算法、资料结构等)的基础上,还要确保我们的程序在每个测试用例的时间和内存范围内运行。代码效率是USACO的关键得分因素。因此,第二阶段的时间和内存复杂性分析更为重要。
通过USACO银级赛段的学生需要非常熟悉以下概念:
· 图和树
· 堆栈,队列和优先级队列
· 二进制搜索
· 深度优先搜索和宽度优先搜索
· 充水
· 滑动窗口
· 前缀和
(3) 金,白金
第三、四阶段需要运用到抽象的方法(最短路径、动态规划等)自行对编程数据结构。该阶段中,解决问题的办法不止一个,要选择最优的方式。
这两个赛段是USACO中较难的,能够通过USACO黄金级认证的学生通常都具有计算机科学算法的高级本科水平。
通过USACO黄金级赛段的学生需要非常熟悉以下概念:
· 动态编程
· 最短路径算法
· 最小生成树
· 不相交集
· 字符串算法
· ·几何算法
· Dijkstra,Prim和Kruskal的算法
· 二叉索引树
据数据统计,从2015年1月到现在,USACO的参赛人数波动增加,这意味着USACO的受欢迎程度正在逐渐上升,随着计算机科学的发展,其推广程度只会更大程度的提高。同时,中国学生参赛比例显著增加,这表明越来越多的中国学生已经意识到了USACO的重要性和含金量。
USACO的含金量
USACO 竞赛的成绩对申请美国大学是非常有帮助的,以下是国外著名网站Quora上的回答,可以看到,大家对USACO申请美国大学的作用还是给予了非常肯定的回答的。
下图中在罗列对申请美国大学有帮助的活动时,第一项就强调了USACO。
最后这张给出了USACO等级对应的数学奥林匹克竞赛等级,很多偏理科的大学都会要求AIME(美国高中数学邀请赛)成绩,如果你有对应的USACO成绩,大学也是认可的。
USACO与数学竞赛的等级对比
目前,USACO在美国非常热衷,但是国内参与的人员还比较少,以2018年公布的数据为例,总共有65个国家3048 名学生参加竞赛,其中来自中国的学生只有280 人。相信随着STEM教育理念,及编程低龄化,普及化的发展,国内USACO 的参加人数和热度会越来越高。
为何要参加USACO竞赛
最近两年,国内的编程教育也在蓬勃发展,很多学生从小学开始已经学习编程了。但市面上的大部分机构所教授的编程,都是偏向图形化,游戏化的编程,这类编程只能让学生了解简单的概念,对于锻炼学生解决问题能力帮助不大。
USACO 竞赛的题目都是以衡量学生解决问题的能力为标准的,题目偏向于算法和实际应用,学生在解决问题的过程中,需要整合所有必备的知识,最终以编程的方式控制电脑给出解答,这个过程能够有效的提升学生的问题解决能力。总的来说,面向USACO竞赛的编程学习会建立如下优势:
- 能力证明,全球认可
信息学作为五大奥林匹克竞赛之一,其能力是被全球认可的,与之配套的知名国际竞赛体系也非常完善。最知名的国际竞赛包括 IOI(国际信息学奥林匹克竞赛)和 ICPC(国际大学生程序设计竞赛),而USACO是美国国家级别的竞赛,其目的就是要为 IOI 和 ICPC 输送人才,虽然很多国家都有类似的国内竞赛,但相比而言,USACO 是得到美国知名大学认可的,更有含金量。 - 思维训练和能力提升
接受一个编程项目,独立思考相关知识点(数学逻辑、数据结构、算法、计算机体系结构、英语理解等),运用各种能力(计算思维、资料收集、刻意练习)设计并实现,验证正确性,反复迭代修正。整个流程在普通的学制教育中往往要到硕博士才有训练机会,而参加竞赛的选手从小就在以这种方式训练着思维,对于专注力和独立解决问题的能力提升非常有帮助。
同时,参加高阶信息学竞赛的往往是最优秀的孩子,他们一起交流、学习、讨论和竞争会潜移默化地影响每个孩子的能力、习惯和学习方式。
而且竞赛的打分,不仅仅是解决问题,还要考量解决的时间效率和空间效率。不同解决策略的得分不一样。这种评价方式,培训和锻炼的就是学生的效率意识和全局规划意识。 - 对升学工作的帮助
在USACO竞赛中证明自己的问题解决能力和学习能力,会对今后的升学和工作都有很大的帮助。现在很多互联网公司内,特别是偏向于人工智能的技术公司,都在大量吸纳竞赛人才,因为这些人非常善于解决核心问题,例如搜狗的CEO王小川(IOI 1996年金牌),旷视科技CTO, 人工智能学术界陈启峰(IOI 2007金牌),陈丹琦(IOI 2008金牌),周源(IOI 2005金牌)等,信息学竞赛对于未来想从事计算机相关工作的人有很大的提升作用。人工智能的核心就是算法。
USACO 什么时候比赛?
USACO 一般是每年12 月份开始进行,会选择四个周末举办主要的比赛,从周五到周一,在这个时间段内学生可以选择在任何时间比赛,通常来说每次竞赛的时间为4个小时,但有时候是3个小时或者5个小时。
如何报名参加比赛?
在 www.usaco.org 注册一个免费账户(只需要有邮箱就能注册),注册时不需要选定特定的比赛日期,只要有了这个账户,可以在比赛开始后随时参与竞赛。
需要为USACO准备什么?
官网上有一个训练题库(https://train.usaco.org),可以登陆这个题库并进行注册,这个网站和USACO官网的注册是分开的,需要独立注册,可以这上面进行训练。同时,在官网上还能查看历年真题(http://usaco.org/index.php?page=contests),可以做一下这些题目,对题目的类型有一个基本的了解。当然,上面提到的这些都是考前的准备,但USACO的相关编程知识,还是要找一个老师好好学习下,掌握了算法和编程基础知识,才有可能在竞赛中获奖。
参加USACO需要付费吗
注意,USACO是一个完全免费的竞赛,只需要在其官网注册账号即可,任何因为参与竞赛向你收费的机构都是在骗人。
竞赛如何颁奖
竞赛会根据你的成绩来颁发对应的认证,主要有四种等级:铜牌,银牌,金牌,白金。获得相应证书的学生名单会被公布在竞赛结果中,把这些成就写在申请书或者简历中会非常有帮助。
参赛的流程是怎么样的?
在官网注册账号后,当比赛开始后,可以在指定时间内的任何时候登陆到官网上开始比赛,比赛的过程中,你可以查询任何资料,从这点足以看出,考核的内容不是死记硬背,而是真正的能力。如果你在竞赛中所有问题都取得了非常完美的分数,你将立刻就能得到升级的反馈,否则可能需要等竞赛周结束后,根据平均成绩公布哪些人通过了考核。由于每年会安排四个周末进行考核,所以你就有了四次竞赛机会,如果你的实力已经到位了,那就可以持续升级。但每个级别的难度差异很大,一般都需要很长时间的练习才能进入到下一个级别。
USACO使用什么编程语言
USACO 接受多种语言的解决方案,包括 C++,C,Java 和 Python。由于Java 和 Python 相比于 C++/C 语言运行的会慢一些,所以这两种语言所允许的运行时间是 C++ 和 C 的两倍。相比于国内 NOIP 只接受 C++ 作为考试语言,USACO 提供了更加灵活的支持,使得比较喜欢 Java 和 Python 的人也有机会参与到算法竞赛中。