滑铁卢计算机竞赛(CCC)数据分析报告

加拿大计算机竞赛(Canadian Computing Competition,本文简称CCC)是加拿大面向全球中学生每年举办一次的计算机程序设计比赛,比赛的目的是为广大中学生提供一个机会来测试自己分析、设计以及编程实现算法的能力。其地位相当于中国的信息技术奥林匹克竞赛。
滑铁卢大学每年2月开始举行CCC竞赛,该竞赛由全世界最大的数学学院 Waterloo滑铁卢大学数学与计算机教育中心(CEMC)举办,始于1996年,迄今已有24年历史,累计已有近10万名来自世界各地的中学生参加过该竞赛,国际影响深远广泛。
CCC竞赛具有较高的名校认可度:
CCC竞赛是滑铁卢大学的一个通行证。CCC已成为滑铁卢大学数学学院各专业以及软件工程专业入学录取的重要指标及参考,更成为学生申请该学院奖学金的重要考核标准;
CCC竞赛是北美名校的敲门砖。因滑铁卢大学在数学及计算机领域的优良声誉以及CCC竞赛考察标准的严格性和专业性,该竞赛成绩在北美名校中已经得到广泛认可;
中国高等院校认可度高。CCC竞赛自2007开始面向中国学生后,已经获得清华大学、香港大学等名校认可,成为初升高/大学自主招生的重要成绩参考,具有较高的认可度。
CCC竞赛具有初级和高级两个级别,级别不同,题目难度不同。每个级别都由五个问题组成,难度从一到五依次递增,每道题15分,总分为75分,答题时间3个小时。比赛题目通常涉及到数学、编程、算法的分析与设计,参赛选手需要具备创造性解决问题的能力以及优秀的编程能力。
CCC编程语言可以支持:C, C++, Java, Python (2.x and 3.x), Pascal, Perl, PHP。从往届示例代码看C/C++和Pascal应用最为广泛。
一般来说初级组适合任何具有基本编程技能的学生;高级组适合任何具有中级到高级编程技能的学生。参赛学生可根据自己的能力选择适合自己的级别。
考生在比赛过程中完成编码后需要提交到滑铁卢官方网站上去,不限次数提交,提交后系统会在后台运行代码并给出测评结果,测评结果立刻告诉你哪个点过,哪个点错。题目的最后得分取所有提交得分的最大值。
CCC第二阶段叫CCO(Canadian Computing Olympiad),也有的翻译为官方邀请赛,比赛将于每年5月在加拿大滑铁卢大学举行。只有CCC高级组成绩列前20个席位的同学可以被邀请出席参加CCO比赛。
CCO为期一周,包括研讨会、两天的比赛以及其他课外活动。具体行程安排以滑铁卢大学最后通知为准。
CCO最后会挑出4名最优秀的同学代表加拿大参加国际信息学奥林匹克竞赛IOI(International Olympiad in Informatics)。2018年加拿大的成绩是1块金牌,3块银牌,东部安省囊括所有名额。
下面看看2019年CCC的参赛数据:
2019年有3713名学生参加了初级组的比赛,有2719名学生参加了高级组的比赛。
虽然参加CCC的总人数不算太多(比参加数学竞赛的人少多了),但最近几年参加的人数增长比较迅速,这是最近四年参与人数情况:
2016年共有3233名同学参加;
2017年共有4285名同学参加;
2018年共有5161名同学参加;
2019年共有6432名同学参加;
每年都有25%-30%左右的增幅,发展势头强劲。
2019年CCC初级组的平均分:

2019年CCC高级组的平均分:

两张表格中,第二列表示所有同学该题的平均分;第三列表示该题所有非零分同学的平均分。从数据上可以看到,还是有不少同学得零分的。
再来看看得分排名情况。

这是初级组的得分排名总表:

 

高级组的得分排名总表:

 

 

从两张表中可以看出,初级组要进TOP 5%需要60分以上;高级组要进TOP 5%只需要36分就可以了。说明高级组题目的难度明显增加了不少。
从颁发证书上看,成绩处于全球TOP 25%的学生都会获得荣誉证书,成绩处于全球TOP 5%的学生将荣登滑铁卢官方成绩榜单。
一、数据分析报告
 
为了帮助大家了解CCC,我们对CCC自1996年到2019年24年初级组和高级组所有竞赛真题进行了分析,完成整理入库、标注、数据分析等步骤,整理出来这份数据分析报告,分享给大家。
对CCC感兴趣以及致力于从事计算机科学相关工作的同学们请继续阅读,希望本文能够对大家有帮助。
下表列出了CCC排在前6名的出题方向:

 

估计很多读友都有一个感性的认识:计算机和数学关系非常密切。
是的,我也这么认为,但我也知道很多感性认识有可能是错的,还是数据更有说服力。所以我带着怀疑的态度做完了这次数据分析报告,数据出来后发现事实与我们的感性认识是吻合的:
CCC排在第一名的出题方向就是解数学题,超过四分之一的题目都与数学相关。

其实计算机最早是为了解决数学问题的数值计算而研制的,最早的编程语言如FORTRAN也是为了解决一些数学问题。

计算机和数学相互影响。计算机的运算模型离不开数学思想,数学的发展强有力地推动着计算机技术向前发展;同时计算机的高速运算能力也大大地推动了数学的发展。

编程实际上是求解某个问题的过程,这个过程实质上是设计算法到实现算法的过程,没有良好的数学思维很难写出高质量的算法和程序。

 

一维数组二维数组是数据结构中最基本的数据存储方式,对于刚入门的程序员来说确实很重要,因此排在第二名和第四名的位置很好理解。

 

字符串是计算机软件界面最重要的展现形式,尤其是在一些商业应用软件中,随处都可以找到字符串的影子。而对字符串的理解深度和编程处理能力,是检验程序员编程经验最有效的方式,因此字符串也成为各大公司最爱出的面试题,排在CCC第三名当之无愧啊。

 

第五名是决策判断

对于数据输入流来说,计算机能够做的最有效的工作就是对于输入数据根据预先设定的条件进行逻辑判断产生分流,从而形成不同的结果和分类,用计算机语言来表达,就是会有大量的IF...ELSE...和SWITCH....CASE...,这种能力和经验对于程序员来说至关重要,决策判断自然就登上了第五名。

 

第六名是递归编程

在编程算法领域,递归编程相对前几名而言属于高级课题,一个函数自恋地调用自己无数次,对于初学编程的同学来说有一些难度,递归编程的题目大多在后面的难题部分。

将数据分析的范围限定在后面难题部分,我们发现19道递归编程题都落在第3题以后,10道题落在了最后一道第5题上面。换句话说,CCC把递归编程作为一个高难度出题方向,想要在CCC中获得高分的同学一定需要加强递归编程的练习啊。

 

下面我们以解数学题字符串递归编程为例来说明CCC是怎么玩的吧。

 

二、第一名:异曲同工-Math Problems
(解数学题)
计算机语言与数学有异曲同工之妙。
举个简单的例子:在数学中函数的概念是从自变量到函数值的一个映射关系,而计算机语言从诞生那天起就借鉴了函数这一数学理念,不管计算机软件系统如何复杂,最后都会化归为函数这一基本单元,每个函数只负责一个特定的功能,完成从输入到输出的转换。
事实上,CCC参赛选手提交的就是可运行的函数,CCC通过已经设定好的测试数据来评测选手提交函数的正确性和性能,根据测试结果来给参赛选手打分。
以1996年的第2题为例说明CCC是如何用数学题考编程的:

题目原文翻译如下:利用如下算法写一段程序,用来判断一个输入的正整数是否能够被11整除。该算法是在1897年由Charles L. Dodgson提出的:一个数能够被11整除当且仅当这个数除以10以后的商减去余数能够被11整除。
数学基础不好的同学估计理解这一算法需要一点时间。
稍有数论基础的同学都知道,一个数能够被11整除当且仅当奇数位上的数字之和减去偶数位上数字之和的差能够被11整除。对此熟悉的同学可以构造足够多的能够被11整除的数,作为测试数据对算法进行测试,算法的准确度会大大高于没有数论知识的同学。
至于这一算法为什么有效,有数论基础的同学不难看出原因:
10A+B+(A-B)=11A
11A肯定能够被11整除,所以10A+B和A-B具有被11整除同样的属性。
知道了这一点的同学完成的算法,只要注意边界条件的处理,基本上此题是稳拿满分的。
完整的C代码如下:

# include <stdio.h>

# include <ctype.h>

 

FILE * infp;

FILE * outfp;

 

int  t,             /* number of test cases */

     i,j,           /* indexes in array A  */

     A[50];         /* arrays to store the digits of a number */

char line[61];      /* a character array to store an input line */    

 

void subtract( int i )

/* subtract A[i] from the number represented by A[0..(i-1)]  */

{

  int j;

  if ( A[i]<=A[i-1] ) A[i-1] = A[i-1] - A[i]; 

  else {

    A[i-1] = A[i-1] - A[i] + 10;

    for ( j=i-2; A[j]==0; j-- )  A[j]=9;

    A[j]--;

  }                      

}

 

main()

{   

  infp = fopen( "div.in", "r");

  outfp = fopen( "div.out", "w");

 

  fscanf(infp, "%d\n", &t);

  while (t>0) {

 

    fgets(line, 60, infp);       /* get number */

    fprintf(outfp,"%s",line);    /* print number once     */

 

    /* convert from characters to digits */

    for (i=0; isdigit(line[i]); i++ ) A[i]=line[i]-'0';

 

    while ((A[0]!=0 && i>2) || (A[0]==0 && i>3)) {

      i--;

      subtract(i);

      if (A[0]!=0) fprintf(outfp,"%d",A[0]);   /* don't print leading zero */

      for (j=1; j<i; j++) fprintf(outfp,"%d",A[j]);

      fprintf(outfp,"\n");

    }

    

    line[strlen(line)-1]='\0';  /*  remove end-of-line */

    fprintf(outfp, "The number %s ", line);

    if ((A[0]!=0 && ((A[0]*10 + A[1])%11==0)) ||

        (A[0]==0 && ((A[1]*10 + A[2])%11==0)))

      fprintf(outfp,"is divisible by 11.\n");

    else fprintf( outfp, "is not divisible by 11.\n");

    

    t--; fprintf(outfp, "\n");

 }

}

substract()函数完成的是A-B的过程,其他都是控制台上读取输入指令和返回输出结果的操作。

通过此题我们看到,良好的数学功底对于CCC还是比较重要的。

 

三、第三名:入行敲门砖-Strings
(字符串处理)
 

鉴于商业软件系统使用字符串处理非常频繁,CCC也在其中大作文章,因为可以用来出题的商业应用场景比比皆是。

例如2009年初级组第4题,写好代码的同学基本上可以直接拿到真实环境中去用:

题目原文翻译如下:学生会需要在显示屏上用多行显示诸如"WELCOME TO CCC GOOD LUCK TODAY"字样,每一行最多可以容纳w个字符。你需要按照如下规则来显示这些文字:

1、每一行尽可能多的显示单词,且不能超过w个字符;

2、第一个词出现在行开头,如有多个词在该行,最后一个词显示在最后;

3、每行多余的空格需要显示在词与词中间并尽可能相同;

4、如果词与词中间的空格没有办法保持相同,最多的空格应该放在前面;

简单的翻译就是:如何对一段长文字美观地拆分到多行进行显示。

 

程序逻辑大概是这样:

接收一段文字;

通过检测字符串中的空格将其分割成一个一个的词,并用字符串数组存起来;

启动一个循环,到字符串数组中按照顺序找到前面的一些词,总长度刚刚小于w(每个词后面都追加一个空格);

在循环块中按照算法要求的4条规则将这些词排列好;

输出最终排列的结果;

 

限于篇幅,具体的代码略过,感兴趣的同学可以自己完成。

 

四、第六名:自恋循环-Recursions
(递归编程)
 

计算机相对人来说最大的优势是计算能力,用程序员的观点来看,就是计算机能够快速地通过循环来执行代码。

在计算机编程中,会写循环是最基本的技能。

在CCC竞赛中,为了检测参赛选手对于计算机语言的理解能力和逻辑思维能力,往往会采用比基础循环语句更高一级的自恋循环,之所以把它叫自恋循环,是因为它会无限次地调用自己,专业术语叫做递归编程。

递归编程容易理解,缺点是如果程序员一旦搞不清楚一个函数自恋自己到什么程度,边界条件稍微处理不当,就有可能造成无限循环,无休止自恋的结果就是堆栈溢出。

我们还是拿一道例题来说明吧,这是2015年初级组的最后一题:

题目原文翻译如下:一般3月14日叫做 π日,因为3.14正好是π的近似值。数学家用吃饼的方式来进行庆祝。假设你有n个饼,有k个数学家排着队来分饼吃,你需要写一个算法来把这n个饼分给这k个数学家,需要满足如下两个条件:

1.每个数学家至少有1个饼;

2.每个数学家分得的饼不能少于队列中前面的人分得的饼数。换句话说,饼数是一个递增序列;

此题看起来像是一道数学题,估计读友会觉得我有点特意往数学题方向上靠,其实不然,我们没有把这道题归为解数学题这一出题方向,尽管里面有数学家,也用到了数学逻辑的分类思维方法。

这是一道典型的递归算法编程题。

整个编程逻辑其实比较简单,借鉴了数学归纳法的一些递推思想:

1.定义一个递归函数getPiNo(int pieNo,int peopleNo,int firstPersonMinPieNo),有三个输入参数:

int pieNo:表示饼的总数;

int peopleNo:表示分饼的总人数;

int firstPersonMinPieNo:表示第一个人分得的饼数最小值;

2.如果要计算getPiNo(n,k,1),可以按照第一个人得到饼的数量进行分类;

第一类:第一个人分得1个饼,也就是后面k-1个人正好分得n-1个饼,并且k-1个人的第一个人最小可以分得1个饼。按照函数定义,正好有getPiNo(n-1,k-1,1)。程序走到这一分支直接返回getPiNo(n-1,k-1,1)即可;

第二类:第一个人分得2个饼,也就是后面k-1个人正好分得n-2个饼,并且k-1个人的第一个人最小需要分得2个饼。按照函数定义,正好有getPiNo(n-2,k-1,2)。程序走到这一分支直接返回getPiNo(n-2,k-1,2)即可;

......以此类推......

第n/k类:这是最后一个分类,因为如果第一个人超过n/k+1个饼,后面每个人都会超过n/k+1个饼,加起来就超过n个饼啦!第一个人分得n/k个饼,也就是后面k-1个人正好分得n-n/k个饼,并且k-1个人的第一个人最小需要分得n/k个饼。按照函数定义,正好有getPiNo(n-n/k,k-1,n/k)。程序走到这一分支直接返回getPiNo(n-n/k,k-1,n/k)即可;

在getPiNo(n,k,1)函数体内启动一个循环对前面所有类的得数求和后返回即可。因为在每个类里面都递归地调用了自己,只要控制好何时停止递归,算出答案不难。

 

只要把递归逻辑理解清楚,翻译成代码不难,需要注意哪些分类是叶子节点,在这些节点应该立即返回,终止递归。

同时为了提高程序运行的效率和性能,对于一些中间运行结果需要保留,以避免重复计算消耗CPU。

代码略过,感兴趣的同学可以根据上述逻辑完成编码。

五、总  结
 

"计算机要从娃娃抓起",三十多年前,邓小平高瞻远瞩地说出了这句名言。

三十多年后,看看我们的身边,3、4岁的娃娃们手机、电脑玩得溜溜的。

计算机上有太多好玩的东东,吸引着不少小朋友很早就进入这一领域,从小就开始学编程了,部分同学甚至觉得只要把编程学好了就可以独步武林天下,其他的学科例如数学可以不用花太多时间。

 

于是很多家长问我是不是可以只要把编程学好就行了。

 

我想上面的这份CCC数据分析报告其实已经给出了答案。

 

CCC让我们看到,没有扎实的数学功底,要想解决稍稍复杂一点的现实问题会比较困难,更不用说牵涉到复杂数学逻辑的算法了。

软件及互联网行业已经进入了开源软件盛行的时代,只要你能够想到的应用,一般都能够找到有人在做了,并且还是开源免费的,拿过来就能用。Rootofmath.com就很感恩这些开源软件的贡献者,他们大大地缩短了我们的研发周期。

开源软件让初级程序员进入的门槛大大减低,但如果没有扎实的数学功底,程序员向上发展的空间十分有限,其核心价值和竞争力会大打折扣。未来的程序员需要能够真正吃透开源软件才会比较吃香,否则碰到问题解决不了,也很难实现技术创新,在未来的时代可能会成为代码的搬运工。

滑铁卢计算机竞赛CCC让我们再次看到了数学教育的重要性。在参加数学竞赛学习的过程中,有些家长担心如果孩子在数学学习上花了时间却出不了成绩怎么办,CCC其实给我们指出了道路之一。数学好的孩子,可以东方不亮西方亮,即便没有在数学竞赛中拔尖,仍然可以在计算机、物理、经济、统计等领域拔得头筹。

至于选择什么编程语言参加CCC的问题,如果你已经学了某种语言很多年,有相当多的经验,尽管放心选择你熟悉的语言,因为每一种语言都有它适用的应用场景,自它诞生那天起,它就在为其所擅长的领域服务,今天很多人依然在用它,说明它具备了顽强的生命力。

 

如果你刚刚开始学习编程,如下经验供你参考:

 

如果你希望以后在一些科研院校做研究,建议你用Python。Python是一种脚本语言,门槛低,上手快,特别适合做科学研究和数值计算,缺点也恰恰来自于它的优点,因为过于简单,规范性不好,很少用来做大型商业应用系统;

如果你对自己的定位是以后进入大公司从事商业应用系统的研发,建议你用Java。虽然前期投入大一点,但是值得。尤其是Java 8引入的Stream API可以帮助你快速重用已有数据结构和组件完成排序和查找,瞬间实现大量代码,这一点在CCC中如果利用得当比较容易在编码时间上胜出;

如果你比较挑剔,控制欲望比较强烈,希望控制代码的方方面面,建议你用C/C++。C/C++的指针可以让你随心所欲地控制你的代码,出现诸如内存泄漏等性能问题也比较容易解决。缺点也同样来自于它的优点,因为控制得太细,你需要比别人花更多的时间来实现相同功能的代码。

 

计算机语言是相通的,熟悉一门语言再切换到另一门语言都不难,一通百通。

 

2020年滑铁卢CCC的初赛时间是2月12日。你,准备好了吗?

 

     

往期数据分析报告原创文章链接:

 

滑铁卢10年级Cayley数学竞赛数据分析报告

 

滑铁卢9年级Pascal数学竞赛数据分析报告

 

美国数学竞赛12年级(AMC12)数据分析报告

 

COMC加拿大国手选拔赛真题数据分析报告

 

滑铁卢欧几里得数学竞赛(12年级)历年真题数据分析报告

 

美国数学竞赛8年级(AMC8)历年真题数据分析报告

 

AMC美国数学竞赛10年级历年真题数据分析报告

 

滑铁卢高斯数学竞赛(7&8年级)历年真题数据分析报告

 

UBC Elmacon数学竞赛历年真题数据分析报告


 
 
 
 
 
 
 
 
 
 
 
 

竞赛资讯

Leave a Message. X

: *
: *
: *
:
Thanks for your message!