Canadian Computing Competition

From PEGWiki
Revision as of 04:51, 18 May 2013 by Brian (Talk | contribs)

Jump to: navigation, search

The Canadian Computing Competition (CCC) is an annual programming competition for Canadian secondary school students, administered by the Centre for Education in Mathematics and Computing (CEMC) at the University of Waterloo. It was first held in 1996. It occurs in two stages, known simply as Stage 1 and Stage 2. The primary difference is that Stage 1 is open whereas one must qualify to Stage 2 by achieving a high score on Stage 1. Understandably, Stage 2 problems tend to be considerably more difficult than Stage 1 problems. The CCC may be regarded as Canada's national informatics olympiad (OI). Like other OIs, it consists exclusively of problems that are fundamentally algorithmic in nature; and again like other OIs, it is used to select students to represent the country at the International Olympiad in Informatics (IOI).

Stage 1

Stage 1 is offered at various high schools across Canada; any Canadian high school may participate provided that a staff member is willing to act as proctor. It is also offered in Hong Kong (since 2005) and Beijing (since 2007), and participation is not restricted by citizenship. There is a registration fee of 8.00 CAD per contestant, though this is not necessarily the amount a school will charge contestants for participating.

The competition itself, held in or around February, is three hours long and comprises five problems of varying difficulty (each worth 15 points, for a total of 75). It can be written in any programming language, except for symbolic computation languages such as Mathematica. Contestants may bring arbitrary printed reference material to the competition (that is, not electronic), such as pre-written code, or algorithmic texts such as Introduction to Algorithms by Cormen et al. Reference materials may also be supplied by the proctor. Competitors are additionally permitted to use the Internet to access an online reference for their programming language (example).

Since 2000, Stage 1 has been offered in two difficulty levels, Junior and Senior. Every eligible high student may write either the Junior or Senior competition in a given year, but not both. Students are permitted to see both the junior and senior contests and may submit solutions to a mixture of junior and senior problems if they wish. Students who have at least two years of experience in computer science are strongly encouraged to write Senior.)

Cash prizes are awarded for high scorers in both divisions. The CEMC also publishes results showing the names of high-scoring students (although it does not show their precise scores). The top twenty or so finishers in Stage 1 Senior are invited to Stage 2. High scorers in the Senior division of Stage 1 may also be considered for scholarships by the University of Waterloo.

Pre-2012, the responsibility of marking students' code submitted at Stage 1 fell to the proctors, although high-scoring students' code was re-marked by the CEMC to ensure consistency and fairness. In 2012, the CEMC introduced an online judge, although this does not obviate the need for manual scoring since an online judge is limited with respect to which programming languages (and programming language implementations) it can grade. As of 2013, the supported programming languages are C, C++, Pascal, Java, Perl, Python, and PHP.

Stage 2

Stage 2 is invitational; only the top twenty or so scorers from Stage 1 Senior are invited to write it. Generally, the criterion has been that the largest score s is selected such that at least twenty contestants scored s or higher on Stage 1 Senior; these students are invited to write Stage 2. However, if this would result in too many students being invited, then s might instead be the smallest score such that at most twenty contestants scored s or higher. The number s is referred to as the Stage 2 cutoff. Like Stage 1, Stage 2 does not limit participation by citizenship.

The competition is held in a week long camp (Monday to Friday) at the University of Waterloo, comprising two competition days (as in the IOI) on Wednesday and Thursday, and various other activities, including practice sessions, computer science related lectures, and plenty of free time for socializing and exploring the university. Unlike Stage 1, Stage 2 is completely free for contestants; the CEMC raises funds to cover the contestants' transportation, lodging, and meals. Students live in the university's residence and take their meals at the residence cafeteria. The competition itself is held in a computer lab in the Math and Computing (MC) building of the university. The camp is scheduled in or around May, and has traditionally been scheduled to avoid coinciding with another computer science competition, ACSL. (However, it often coincides with the exams of the International Baccalaureate (IB) program, which has led to some eligible contestants being unable to participate.)

Three problems are given per competition day, all equally weighted, matching the pre-2009 format of the International Olympiad in Informatics. In 2009, the format of the IOI itself changed, adding one "easy" problem per day. However, CCC Stage 2 still consists of only three problems per day. The amount of time given per day has varied from year to year. Stage 2 also does not use a consistent scoring scheme, but is weighted twice as heavily as Stage 1 in determining an "IOI index"; the four contestants with the highest IOI indices are selected to represent Canada at the IOI, excluding ineligible contestants (generally the contestants from outside Canada). In 2008, for example, each problem was marked out of 25, for a total of 150, which was added to the stage 1 score (up to 75) to obtain a total of 225. In 2009, on the other hand, each problem was marked out of 100 for a total of 600, which was then added to four times the stage 1 score.

Stage 2 does not permit arbitrary programming languages like Stage 1 does; only C, C++, and Pascal (the same three programming languages allowed at the IOI). Submissions are made through an electronic system. Unlike Stage 1, Stage 2 does not permit printed reference materials, but contestants are provided with offline electronic documentation of the allowed programming languages.

The four competitors selected to represent Canada at the IOI are awarded gold medals and $500 each; any ineligible contestant who scored at least as high as the lowest-scoring of the four is likewise awarded a gold medal and $500. Some of the remaining contestants are awarded silver medals and $250 each, and the rest are awarded bronze medals. The official results show which medal each contestant received, but do not reveal the actual rankings, except by indicating the absolute winner(s). The contestants themselves can learn their own scores, but generally do not have access to the scores of other contestants.

Historical cutoff values

These values are obtained by counting the number of students who qualified to Stage 2 in each year (listed on the CEMC's official results) and comparing this to the values in the table given at the end of the results which maps score to rank. Prior to 2001, the latter is not given, so the cutoff cannot be determined. In 2002 and 2007 the cutoff is uncertain because no value would have given the exact number of stage 2 invitees listed, assuming the table is correct.

CCC stage 2 cutoff data in graph form
  • 2001: 59
  • 2002: 57 (?)
  • 2003: 57
  • 2004: 47
  • 2005: 57
  • 2006: 48
  • 2007: 58 (?)
  • 2008: 66
  • 2009: 49
  • 2010: 41
  • 2011: 63
  • 2012: 64

These data show no clear trend over time. However, they give a good idea of the difficulty of each year's CCC Stage 1 Senior; harder years tend to have lower cutoffs, since the cutoff is determined by the score of the twentieth or so best contestant. (Of course, some years have stronger contestants than others, so one should exercise discretion with this interpretation.)

The (at the time) all-time high value of 66 in 2008 was presumably due to the fact that the hard problem, Nukit, was a relatively easy exercise in dynamic programming; several students in fact achieved perfect scores.

In 2009, the last problem, Wireless, was ad hoc and presumably intended to be solved with difference arrays, a technique that few contestants knew; in addition, the fourth problem, Ship and Shop, had huge input data and could have been challenging to optimize. Predictably, the cutoff took a nose dive; one cannot help but wonder whether the organizers were trying to make up for the abnormally high cutoff the previous year.

For reason or reasons unknown, the contest was made even more difficult the following year, with problems S3, S4, and S5 all quite difficult; there was no perfect score in that year. The resulting cutoff of 41 was the lowest in "recorded" CCC history.

The cutoff returned to a more "normal" value in 2011 and 2012. Then, 2013's cutoff was the highest in CCC history. This may be attributed to the fact that all of the problems were fairly straightforward, except S5 which required some optimization in order to crack the larger test cases.

Troy Vasiga, director of the CCC, had the following to say about the recent high cutoffs:

I think we have stopped clubbing students on Stage 1 like baby seals, especially in the last couple of years. I think something in the low 60s is probably about the "right" score for the cutoff: ace the first 3 problems, make sure you don't mess up S4 and get something intelligent on S5.[1]

Problems

Past CCC problems from both Stage 1 and Stage 2 may be found on the PEG Judge.

References

  1. Troy Vasiga. Personal communication. March 10, 2013. Included with permission.