Canadian Computing Competition

Canadian Computing Competition
(Last modified Saturday February 04, 2012)

This provides ALL past Stage 1 CCC

problems,
solutions, using Python beginning in 2011 and prior to that Holt Software Associates' Turing and Ready: Java.
(All solutions were written by Chris Robart of Milliken Mills High School., except where indicated below:)
and data files (both input and output).

All of these are of course UNOFFICIAL. The Official website is CCC.

The following people have contributed solutions (thank you!):
(AJ) Amlesh Jayakumar of Waterloo Collegiate Institute (2008 S5: 2009 S4, S5)
(AL) Anton Likhtarov of Burnaby North S.S. (2005 S5)
(AV) Aaron Voelker of Bell High School. (2007 S3: 2000 S4: 1999 P5)
(BB) Brian Bi of Woburn Collegiate Institute (2009 S5)
(DC) Daniel Cressman of Westdale Secondary School (2011 J5)
(DG) Daniel Galperin of Waterloo Collegiate Institute (2009 S5)
(GV) Goutam Venkatramanan of Harry Ainlay High School (2009 S1)
(HT) Hubert Tong of Queens University (2008 S4: 2001 S5)
(JJ) Jason Jackson of Aurora High School (2006 S3, S5: 2005 J5)
(KL) Konstantin Lopyrev of the University of Waterloo. (2008 S3, S4, S5: 2007 J5, S5)
(ML) Matthew Lai of Steveston-London Secondary School. (2008 S5: 2007 S4)
(PS) Peter Sun of St. Francis Xavier S.S. (2010 J5)
(RC) Robin Cheng of Pinetree Secondary (2005: S5)
(RH) Rich Hong of St. George's School, Vancouver (2006 S5)
(RP) Richard Peng of Vaughan Road Academy (2004 S4: 2001 S4: 2000 S5)
(SH) Sean Henderson of the University of Toronto (2005 S5)
(SF) Sumudu Fernando of the University of Alberta (2011 J5, 2011 S5)
(VL) Victor Liu of Dr. Norman Bethune C.I. (2010 S5)
(VS) Vassili Skarine of Northview Heights S.S. (2003 S4, S5: 2002 S4)
(VSi) Vincent Siao of St George's School (S010 S3)
(WC) Wonjohn Choi of St. Francis Xavier S.S. (2010 J5)
(WHL) Wen-Hao Lue of Bayview Glen Private School.(2007 J5: 2009 S4)
Please email me if you find any errors, or have easier-to-understand solutions. Thanks.

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

Rating key (this is for just for fun, but does give some sense a problem's difficulty.)

* an average grade 11 student should get this

** an average grade 12 student should get this

*** a good grade 12 student MIGHT get this

**** the best grade 12 student MIGHT get this if given enough time

***** the teacher will get this after many days, or maybe never :-)

Links and Resources
Books (pdf)

Problems on Algorithms 2nd Edition, July 2002 by Ian Parberry and William Gasarch

Foundations of Computer Science    Lawrence Paulson

"Algorithms" Course Materials by Jeff Erickson

CMSC 420: Data Structures (Spring 2001)    Dave Mount

CMSC 451: Design and Analysis of Computer Algorithms     David M. Mount

The Java Language Specification    James Gosling, Bill Joy and Guy Steele

Sorting and Searching Algorithms: A Cookbook    Thomas Niemann

Art of Programming Contest   Ahmed Shamsul Arefin

How to Think Like a Computer Scientist     Allen B. Downey

Algorithms S. Dasgupta, C.H. Papadimitrou and U.V. Vazirani

Websites

The Wiki of the Senior Computer Team at TJHSST

The Lectures of TJHSST's Senior Computer Team

The Algorithmist

Data Structures and Algorithms with Object-Oriented Design Patterns in Java by Bruno R. Preiss

Please email me if you have other favorites.

2011 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1: Which Alien?	ifs	*	1 2 3 4 5	1 2 3 4 5
J2: Who Has Seen the Wind	loop and if	*	1 2 3 4 5	1 2 3 4 5
J3: Sumac Sequences	a loop	*	1 2 3 4 5	1 2 3 4 5
J4: Boring Business	moving in a 2d array	**	1 2 3 4	1 2 3 4
J5: Unfriend a strange counting method a recursive approach (SF) a more general approach (DC)	tricky counting and 1D array handling or recursion (SF relies on j<i as given in the problem, DC is more general allowing j>=i)	***	1 2 3 4 5	1 2 3 4 5
Senior Problems
S1: English or French?	simple character counting	*	1 2 3 4 5	1 2 3 4 5
S2: Multiple Choice	simple array processing	*	1 2 3 4 5	1 2 3 4 5
S3: Alice through the Looking Glass	recursion (I won't say simple)	***	1 2 3 4 5	1 2 3 4 5
S4: Blood Distribution	array processing (straight forward: no tricks.)	**	1 2 3 4 5	1 2 3 4 5
S5: Switch my brute force method (solves the test cases but doesn't work in ALL cases) a dynamic programming approach (SF)	relatively simple String handling or Dynamic programming	or **	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10

2010 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1: What is n, Daddy?	if's or a calculation	*	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10
J2: Up and Down	loops and ifs	**	1 2 3 4 5	1 2 3 4 5
J3: Punchy	loop with ifs	*	1 2 3 4 5	1 2 3 4 5
J4: Global Warming	arrays and matching	***	1 2 3 4 5	1 2 3 4 5
J5: Knight Hop Simple Recursion (by PS and WC) Bread First Search	2D array - simple recursion - queue and BFS	***	1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8
Senior Problems
S1: Computer Purchase	calculations and ifs	**	1 2 3 4 5 6 7 8 9	1 2 3 4 5 6 7 8 9
S2: Huffman Encoding	arrays and string handling	**	1 2 3 4 5 6	1 2 3 4 5 6
S3: Firehose linked list of gaps (by VSi) Binary seaching and arrays	arrays and Linked lists or Binary Searching	*****	1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8
S4: Animal Farm	2D arrays, graph and Prim's algorithm	*****	1 2 3 4 5	1 2 3 4 5
S5: Nutrient Tree (by VL)	Binary Tree, Recursion and Arrays	*****	1 2 3 4 5 6 7 8	1 2 3 4 5 6 7 8

2009 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1: ISBN	simple arithmetic	*	1 2 3	1 2 3
J2: Old Fishin' Hole	nested for loops	*	1 2 3 4 5	1 2 3 4 5
J3: Good Times	calculations and if's	**	1 2 3 4 5	1 2 3 4 5
J4: Signage	string handling, arrays	**	1 2 3 4 5 6	1 2 3 4 5 6
J5: Degrees of Separation	graph theory: 2D arrays	****	1 2 3 4	1 2 3 4
Senior Problems
S1: Cool numbers Cubes and powers approach Power of 6 method (by MANY people) Power 6 with Insight (by GV)	tricky loops and calculation	***	1 2 3 4 5	1 2 3 4 5
S2: The Lights Going On and Off	array processing	***	1 2 3 4 5	1 2 3 4 5
S3: Degrees of Separation	graph theory: 2D arrays	****	1 2 3 4	1 2 3 4
S4: Ship and Shop Recursion (in a loop?) Dijkstra's Algorithm (By AJ and WHL)	graph theory	****	1 2 3 4 5	1 2 3 4 5
S5: Wireless Straight forward Difference Array (by BB, AJ and DG)	2D array processing	*****	1 2 3 4 5 6	1 2 3 4 5 6

2008 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1 Body mass Index	simple calculation	*	1 2 3	1 2 3
J2 Do the Shuffle	simple string handling	*	1 2 3 4 5	1 2 3 4 5
J3 GPS Text Entry	ifs and calculations	**	1 2 3 4 5	1 2 3 4 5
J4 From Prefix to Postfix	recursion	***	1	1
J5 Nukit	indirect recursion (see S5 for a DP approach)	***	1 2 3 4	1 2 3 4
Senior Problems
S1 It's Cold Here	simple "find smallest" algorithm	*	1 2 3	1 2 3
S2 Pennies in the Ring	simple geometry problem	**	1 2 3 4 5	1 2 3 4 5
S3 Maze Recursive DFS approach A better BFS approach (by KL)	It's a 2D problem for sure - recursion (Depth First Search) - Breadth First Search	***	1 2 3 4 5	1 2 3 4 5
S4 Twenty-four Brute force Recursion, stacks and RPN (By KL anf HT)	nested loops and 2d arrays	****	1 2 3 4 5	1 2 3 4 5
S5 Nukit Recursive approach DP approach (by KL, ML and AJ)	indirect recursion, or DP	****	1 2 3 4	1 2 3 4

2007 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1 Who is in the middle?	simple decisions	*	1 2 3 4 5	1 2 3 4 5
J2 I Speak TXTMSG	simple decisions with a loop	*	1	1
J3 Deal or No Deal Calculator	simple 1D array processing	*	1 2 3 4 5	1 2 3 4 5
J4 Anagram Checker	string processing	**	1 2 3 4 5 6 7	1 2 3 4 5 6 7
J5 Keep on Truckin' Dynamic Programming approach Dynamic Programming V2 (by KL) Recursive approach (by WHL)	dynamic programming or easier DP or recursion (easiest)	***	1 2 3 4 5	1 2 3 4 5
Senior Problems
S1 Federal Voting Age	simple decision	*	1 2 3	1 2 3
S2 Boxes	arrays, records and sorting	***	1 2 3 4 5	1 2 3 4 5
S3 Friends (by AV)	arrays and more arrays :-)	***	1 2 3 4	1 2 3 4
S4 Water park Linked List Approach Recursive Approach (by ML)	linked lists and dynamic programming or easier recursion	****	1 2 3 4 5	1 2 3 4 5
S5 Bowling for Numbers (by KL)	2D Dynamic Programming	*****	1 2 3 4 5	1 2 3 4 5

2006 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1 Canadian Calorie Counting	simple decisions	*	1 2 3 4 5	1 2 3 4 5
J2 Roll the Dice	loops and counting	*	1 2 3 4 5 6	1 2 3 4 5 6
J3 Cell-Phone Messaging	strings and decisions	*	1	1
J4 Tough Being a Teen	array handling	**	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10
J5 CCC Othello	2D array handling	**	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10
Senior Problems
S1 Maternity	basic string handling	*	1 2 3	1 2 3
S2 Cipher Texts S2 Cipher Texts v2	string handling (V2 - inferring the 27th from 26 given requires a more complex approach)	**	1 2 3 4 5	1 2 3 4 5
S3 Tin Can Telephone S3 Tin Can Telephone (Vec) (by JJ)	geometry calculations (Vector approach)	***	1 2 3 4	1 2 3 4
S4 Groups	2D array (matrix) manipulation	***	1 2 3	1 2 3
S5 Origin of Life (by CR, JJ, RH) S5 Origin Of Life (V2) (by JJ)	2D arrays, queues and complex algorithm (find all Edens approach)	****	1 2 3 4 5	1 2 3 4 5

2005 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1 Cell Sell	arithmetic, decision structures	*	1 2 3	1 2 3
J2 RSA Numbers	arithmetic with nested structures	*	1 2 3	1 2 3
J3 Returning Home	simple array and string processing	*	1 2 3	1 2 3
J4 Cross Spiral	moving around a 2D array	***	1 2 3 4 5	1 2 3 4 5
J5 Bananas J5 Bananas (non-recursive) (by JJ)	indirect recursion or simple iteration (no recursion needed)	***	1 2 3 4	1 2 3 4
Senior Problems
S1 Snow Calls	basic string handling	*	1	1
S2 Mouse Move	basic structures	*	1 2 3 4 5	1 2 3 4 5
S3 Quantum Operations	2D array (matrix) manipulation	**	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10
S4 Pyramid Message Scheme	tree height / 1D array manipulation	***	1	1
S5 Pinball Ranking Very simple but slow - Counting (by RC) Slow- Insertion sort Fast - Binary Tree (by AL) Fast -Merge Sort (by SH)	sorting exercise (using insertion sort, a binary search tree or merge sort)	***	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10

2004 Problems	Topics Involved	Rating	Input Files	Output files
Junior Problems
J1 Squares	reals and integers	*	1 2 3 4 5	1 2 3 4 5
J2 Terms of Office	simple arithmetic (loops and mod)	*	1 2 3 4 5	1 2 3 4 5
J3 Smile with Similes	nesting loops	*	1 2 3 4 5	1 2 3 4 5
J4 Simple Encryption	strings and character manipulation	**	1 2 3 4 5	1 2 3 4 5
J5 Fractals	geometry, array processing	***	1 2 3 4 5	1 2 3 4 5
Senior Problems
S1 Fix	decisions and built-in string functions	**	1 2 3 4 5	1 2 3 4 5
S2 Top Yodeller	simple 1D array processing	**	1 2 3 4 5	1 2 3 4 5
S3 Spreadsheet	simple 2D arrays and String processing	***	1 2 3 4 5	1 2 3 4 5
S4 Space Turtle (by RP)	ugly geometry problem	****	1 2 3 4 5	1 2 3 4 5
S5 Super Plumber	2D arrays & dynamic programming	****	1 2 3 4 5	1 2 3 4 5

2003 Problems	Topics Involved	Rating	Input Files	Output files
J1 Trident	character graphics	*
J2 Perfect Picture	simple arithmetic (div and mod)	*
J3/S1 Snakes and Ladders	simple counting, decisions	*
J4/S2 Poetry	simple strings, decisions	**	1 2 3 4	1 2 3 4
J5/S3 Floor Plan	2D array, recursion, largest of 1D array	***	1 2 3 4 5	1 2 3 4 5
S4 Substrings (by VS)	strings	***	1 2 3 4 5	1 2 3 4 5
S5 Trucking (by VS)	graph theory, Prim's algorithm	****	1 2 3 4 5	1 2 3 4 5

2002 Problems	Topics Involved	Rating	Input Files	Output files
J1 0123456789	character graphics	*
J2 AmeriCanadian	simple strings	*
J3/S1 Student Council's Breakfast	nested loops	*
J4/S2 Fraction Action	GCD algorithm	*
J5/S3 Blindfold	1D and 2D array	**	1 2 3 4	1 2 3 4
S4 Bridge Crossing (by VS)	dynamic programming	*****	1 2 3 4 5	1 2 3 4 5
S5 Bouncing Ball	geometry calculations	****	1 2 3 4 5	1 2 3 4 5

2001 Problems	Topics Involved	Rating	Input Files	Output files
J1 Dressing Up	character graphics	*
J2 Mod Inverse	simple arithmetic (div and mod)	*
J3/S1 Keeping Score	simple strings, decisions	*
J4/S2 Spirals	loops, decisions	**
J5/S3 Strategic Bombing	graph theory, Warshall's algorithm	****	1 2 3 4 5	1 2 3 4 5
S4 Cookies (by RP)	geometry calculations	****	1 2 3 4 5	1 2 3 4 5
S5 Post's Correspondence Method 1 Method 2 (by HT)	strings, complex recursion	****	1 2 3 4	1 2 3 4

2000 Problems	Topics Involved	Rating	Input Files	Output files
J1 Calendar	loops, decisions	*
J2 9966	simple arithmetic (div and mod), decisions	*
J3/S1 Slot machines	loops, decisions	*
J4/S2 Babbling Brooks	1D array (insertion/deletion shifting)	**	1 2 3 4 5	1 2 3 4 5
J5/S3 Surfing	strings, graph theory, Warshall's algorithm	****	1 2	1 2
S4 Golf Dynamic programming approach Breadth First Approach (by AV)	dynamic programming or breadth first Tree Search	****	1 2 3 4 5	1 2 3 4 5
S5 Sheep and Coyotes Brute force approach or using Perpendicular Bisectors (by RP)	geometry calculations, 1D arrays	****	1 2 3 4 5	1 2 3 4 5

1999 Problems	Topics Involved	Rating	Input Files	Output files
P1 Card Game	1D array, decisions	*	1	1
P2 Year 2000	Ugly string processing	***	1	1
P3 Divided Fractals	character graphics, recursion	***	1	1
P4 A Knightly Pursuit	2D array, dynamic programming	*****	1	1
P5 Letter Arithmetic My Brute force Approach An Improved Method (by AV)	exhaustive search (combinations/ permutations), string, 1D array, complex algorithm	*****	1	1

1998 Problems	Topics Involved	Rating	Input Files	Output files
P1 Censor	strings, loops, decisions	*	1	1
P2 Cross Number	simple arithmetic (div and mod)	*		1 2
P3 Mars rover	decisions	**	1	1
P4 Lottery	string, complex algorithm	***	1	1
P5 Mountain Passage	2D arrays, dynamic programming	*****	1	1

1997 Problems	Topics Involved	Rating	Input Files	Output files
P1 Sentences	nested loops	*	1	1
P2 Nasty Numbers	complex arithmetic (div and mod)	**	1	1
P3 Double Knockout Competition	simple arithmetic (div and mod)	**	1	1
P4 Dynamic Dictionary Coding	string, 1D array	**	1	1
P5 Long Division	string, 1D array, complex algorithm	****	1	1

1996 Problems	Topics Involved	Rating	Input Files	Output files
P1 Perfect Numbers	simple arithmetic (div and mod)	*	1	1
P2 Divisibility by 11	string, 1D array, complex algorithm	***	1	1
P3 Pattern Generator	complex string algorithm	***	1	1
P4 Roman Numerals	decisions	**	1	1
P5 Max Distance	1D array	***	1	1