美国计算机奥林匹克竞赛USACO题型分析

USACO(United States of America Computing Olympiad, 美国计算机奥林匹克竞赛) 是一项针对全世界所有的高中信息学竞赛选手的一项竞赛。专门为信息学竞赛选手准备,但必须在注册后才能进入题库。这项赛事不仅可以培养学生的算法和编程思维,好的竞赛成绩还能给孩子大学申请加分。

由于有些编程题跟谷歌,脸书等顶级科技公司面试题类似,好的USACO竞赛成绩对孩子以后申请实习也大有裨益。AI时代,计算机编程是一项不可或缺的能力,理工院校对其青睐有加。

MIT 2024届早申录取的两名大陆学生中,其中一名学生在中国的NOI比赛(美国对应的是USACO比赛)中获得金牌(全国前50名),入选信息学国家集训队,同时保送清华大学(这是公开政策,获得金牌可保送清北)。

USACO含金量

对于准备出国留学,打算申请理工科,尤其是计算机/编程方向的孩子来说,USACO不仅培养学生的算法及应用和编程思维,成绩含金量也不言而喻,获得黄金级、白金级的参赛者将大大增加被藤校录取的概率!

USACO不仅在美国大学中认可度高,在美国国内参与度广,而且在全球也具有比较广泛的参与度。上赛季首场比赛参赛人数达到10752人,同比增长了40%!USACO真的是一场国际赛事!

在MIT(麻省理工学院)本科招生官网中,可以赫然看到USACO是被“点名”推荐的课外活动。

而且,大家说USACO是免费的CSP-J/S也不是没有理由的。

在美国,USACO是可以直接对标国内的NOI竞赛的,每年也会举办多次选拔赛,分为铜、银、金、白金四个奖项。无论是NOI还是USACO都是为IOI选拔人才的竞赛。

所以,能在USACO竞赛中取得一定成绩的学生,绝对是妥妥的背景提升!

适合学生

任意年级中学生

USACO在每年12月至次年4月间,会举办4场比赛,参赛者可在同一年内多次参赛。与其他全球性赛事出分、晋级最少需要10天不同,USACO采用机器评分机制,代码提交后系统会自动给出评分。

注意考生提交代码后,会立即得到反馈结果。通常的反馈结果包括:全部通过、部分通过、编译错误、超时、运行错误等。虽然能立即得到反馈,但只有在比赛结束后,才能看到测试数据哦!

赛制规则

赛制规则

在赛事窗口开放的三天时间内,选择任意时间开始比赛,只要实力足够,一场可以升到白金级。

其他选手需要等3天赛程结束后,根据分数线决定是否晋级。

铜级

参赛资格:一进入USACO注册帐号即为铜级

难度等级:铜级考试只要基本编程常识,会至少一种编程语言。根据以往比赛来看,铜级的比赛时间还是较为宽裕的,大部分选手能在一次比赛中进入到银级。一般USACO银级的题目可以等于国内NOIP(现CSP)普及组试题难度

需要考核知识点:基础数组,多重循环,复合判断、枚举算法

银级

参赛资格:通过铜级比赛的选手

难度等级:需要基本的问题解决能力的简单算法(例如:贪心算法、递归搜索等),还需了解基础数据结构。从银级开始,选手需要寻找更好的的算法才能使程序在规定时间内跑完。一般USACO白银级的题目可以等于国内NOIP(现CSP)提高组试题难度

需要考核知识点:基本数据结构、贪心、递归、递推等基本算法

金级

参赛资格:通过银级比赛的选手

难度等级:需要有一定的算法基础,理解一些抽象的方法(例如:最短路径、动态规划),并对数据结构有比较深刻的了解。IOI试题>金组试题>NOIP试题

需要考核知识点:堆、栈、树、链表等高级数据结构,动态规划等高级算法,算法时间和空间复杂度

白金级

参赛资格:通过金级比赛的选手

难度等级:需要有很高的编程基础,对算法有深入的了解。部分试题最后的优化方案,可能不止一个,得出的答案也不止一个

需要考核知识点:各类高级的数据结构,尤其是需要算法的时间和空间复杂度,总分1000分。每道题333.3分。每道题有10个测试点,通过一个可得33.33分。青铜、白银、黄金、铂金级别的比赛都是3道题。

考试的进阶

USACO 每年举办好几次考试,其中最后一次考试叫US Open。在US Open之前有3次考试,前3次考试各有4个小时,最后一次考试是5个小时。在规定的时间之内,考生需要把复杂的题目进行理解和分析然后推导,并且使用算法来解决它,最终需要再把这个代码提交到官方网站上,然后通过官方网站的测试数据判断,获得那道题目的分数。

当考生考完某个级别的考试,达到了一定的分数线,这位学生就可以被 promote 到下一个级别。那么当学生到了 Platinum 级别之后,他将有可能获得一个该年度进入国家集训队的机会。

支持的语言

USACO 竞赛支持不同的语言,但支持最多的还是 C++,当然也有参赛者使用 Java,少量使用 Python 以及 C语言。C++ 在编程竞赛的效率方面更加占有优势。

通过率

看了每个级别的考试的参赛的人数,那么有多少人能够考过?在2019~2020赛季, Bronze 过的人数比较多,通过率大概在19%左右。到了去年和今年,就在10%出头以及15%左右。

综合来看,过去三年 Bronze 通过率就在15%左右。

Silver 在前年也就是2019~2020赛季,是在5%;在2020~2021赛季是6%左右;到今年的话也是有所降低。

而 Gold 的通过率大概在 2% 到 3% 左右。

题目的难度也是在逐渐增加。尤其是在今年,我们明显感觉到有个别题目原来应该出现在 Gold 这个级别,但现在开始出现在 Silver 这个级别的最难那道题。

Gold 那就更不必说,在两年前 Gold 和 Bronze 以及 Silver 类似,是偏知识性的这种级别,只要把知识点学过了,那么孩子就能够比较舒服的通过 Gold,当然也要做适当的练习。但是从去年开始包括今年,我们明显发现 Gold 题目出现了更多的套路,需要孩子投入更多的时间来做模拟测试,然后做更多练习。

题型分析

首先说 Bronze。我们对过去三年的题目做一个大致分析,题目有三种。

1. simulation

考生只需要用 algorithm 和 coding 实现一个process就可以。

2. greedy algorithm

这类题目相对有一点tricky,需要孩子有更多的 observation 以及 analysis 方面的训练。

3. search

这也就是我们俗话说的暴力法,就是要能用一种枚举的思路来思考问题。

Bronze 级别,掌握了这三种基本题型的解题方法,在知识角度就没有太大问题,剩下的主要在编程能力方面,是否能够把这三种题目的 algorithm 转化为 coding,并且能够正确的通过 test case。

Bronze 总共三道题。很多时候 USACO 可能认为把第一道题放在最简单的一个位置,但其实从结果来反推并不是这样,有时候最后一道题反而是最简单的,所以推荐孩子上来不要看了第一题之后就立刻去写,而是先把三道题都看一遍。

我们应该努力把简单和中等难度两道题目拿满分。总共满分是1000分,Bronze 分数线在 700-750,两道题差不多是666分左右,也就是说我们并不需要最难的第三道题目完全做出来,只要能拿到一部分分数超出分数线,就能够通过 Bronze 考试。

● Simulation题注意点

Simulation 这种题目推荐孩子掌握一个比较稳固的编程基础,另外读题目一定要小心,有时候读错一道题的话,可能花了更多的时间在思考上面,最后突然发现题目读错,那就损失比较大。

● Greedy Algorithm题注意点

Greedy Algorithm最重要的其实不是编程,编程部分通常来讲都非常的容易,更加难的一点是什么?是判断这道题是否能够用 greedy algorithm 来解决,这反而是最难的。

这里有很重要的一点:我们很多时候不需要去证明 Greedy 的性质,因为证明有的时候会更加复杂更加难,很多时候是需要做一个假设,然后再找找看有没有反例能够推翻。如果没有发现很明显的反例,其实就可以试一试,因为 Greedy Algorithm 在写程序的时候往往简单,通过几个循环就能解决掉。所以我们一直告诉孩子,在遇到 Greedy Algorithm 的时候该怎么做。同时,Greedy 的算法因为复杂度较低,所以通常它的数字非常大,就是题目所出的数据范围会非常的大。

● search题注意点

search 题目主要是 dfs 和 bfs,然后需要孩子对 complexity 有一定的了解。这种题型有一种偏几何的题目,往往是跟矩形的边界判定,或者是坐标系有一定关系,但还没有难到计算几何的难度,所以这个地方只要把往年的一些几何题过一过,也就够了。

对于比较难的问题,我们不是特别推荐在 Bronze 级别做专门的准备,更需要的是什么?更需要的是孩子往更高的知识点学习,去学习 Silver 知识点,或者更高级的知识点。那么等到某一天回过头来,其实就已经形成了一个降维打击。

来到 Silver级别,很明显就多了很多 topics,比如除了刚才的 simulation 以及 search 之外,增加了graph 还有DP,DP就是 dynamic programming 动态规划,还有 counting 和 data structure。其中 dynamic programming 这种题型是 21年新出现的,以前从来没有在 Silver 出现过,都是在 Gold 出现。本赛季 Silver 级别考试 Graph 出现的也越来越多,这样 Silver 也会比以前更加有挑战性。

竞赛常见问题

1.对于没有编程基础的学生如何备赛?

建议从python或者java入手,上手较快。学习主要内容为数据结构,编程语法,配合一定强度的练习,可以初步通过第一轮铜级的选拔。


2.对于有部分编程基础的学生如何备赛?

比如在读AP计算机的高一高二同学可以从C++或者C入手。作为编程语言中强大且基础的两门,无论是应付比赛还是在以后读本科或者工作中使用,提前学习C++和C都是不错的选择。


3.对于有编程基础及编程经验的学生如何备赛?

比如参加过国内NOI的同学,设定的目标可以直接冲击至少金级别以上的奖项。

在有数据结构和编程语法的前提下,需要系统的学习一些常见算法,比如排序等等。同时大量练习官方的金,白金级别的真题。

下一篇

2022HiMcM【A/B题】中文最新翻译

你也可能喜欢

评论已经被关闭。

插入图片
微信咨询 微信咨询
微信咨询
在线咨询 在线咨询
在线咨询
返回顶部