I'm going to be writing the waterloo contest this upcoming Tuesday...

[Reality Check]

and I'd like to get some pointers. I'm in for the Junior one but I honestly feel I can do the senior one. I'm in grade 11 and because I have programming this semester, I'm suppose to be doing the junior. Anyways, the grade 12's tell me its impossible to do all 5 in the senior one and I'm starting to get worried. I probably won't use Java though since I'm not too familiar with it yet. I'll do Java for next years program. Anyways, what are some things I can do to prepare myself?

[PaulButler]

I am going in this competition for the first time as well. I have been practicing by looking over and doing the questions from past years which can be found here:

http://www.cemc.uwaterloo.ca/ccc/past/previous_contests.shtml

Notice the link at the top of the page to an external site with unofficial solutions, I thought this page was helpful too.

Other than that, I have just been doing any programming question I could get my hands on... I signed up for TopCoder and Project Euler and did a few of their problems as well. Of course, I haven't done the competition before so maybe someone who has will have better tips.

I do have a question to add, though: when is the choice between junior and senior made? I didn't see the choice when my teacher was making the order, and I hope I don't get stuck with junior. To make things worse, my teacher is away until Monday so I can't check with him. My impression (from previous contest guidelines) was that you are given both sets of questions and choose at the time of the test.

[bugzpodder]

yes, its pretty much impossible to get everything on the senior. but you dont need to get everything to get to stage 2. only about 3 - 4 questions (first 2 is usally pretty easy)

[PaulButler]

bugzpodder @ Wed Feb 21, 2007 8:11 pm wrote:

yes, its pretty much impossible to get everything on the senior. but you dont need to get everything to get to stage 2. only about 3 - 4 questions (first 2 is usally pretty easy)

Really? That's encouraging. Do you know how many people usually enter?

RealityCheck (or anyone else), if you're interested, we could pick a past competition and do as many of the questions as we can individually, and share our solutions with eachother. I figure at the very least it would be good practice, and ideally we might learn something from the other's code.

[bugzpodder]

they pick 20-25 people. as i said you need to get essentially first three pretty solid to have any chance of getting in.

and i'll pass on that. I'm past CCC

[Tony]

Yes, you are given both sets of questions at the start of the competitions. If I recall correctly there's quite a bit of overlap as well (3rd Junior question is 1st Senior?)

So you can start writing Junior, finish all 5 questions and if there's enough leftover time start doing the other 2 Senior questions. I've actually done that during my first CS high school year, and got to choose between two different scores to submit

[klopyrev]

I am also writing the contest next tuesday and have been preparing for several months already. I've done it twice already before, so I think I am ready. The choice of which contest to write is made after you get to look at both contests. You get to read over both and then make a choice. The junior contest is fairly simple. You don't need to be familiar with any algorithms for the first 4 questions on the junior. The 5th question is a bit harder. You should know how to do recursion, some other basic algorithms. As for the senior. The first two problems are ad-hoc problems. You don't need to know anything to answer them. The 3rd and 4th question are a bit harder. They require knowledge of basic algorithms. There was a computation geometry one last year. As for the 5th question: it varies from year to year from difficult ad-hoc problems to problems with an algorithmic nature in them. You have to know quite a bit about computer science to be able to answer the 5th question. The difficulty of the 5th questions is slightly easier than a standard IOI question. Also note that there is no overlap in the Junior and Senior contests, therefore, you should make your choice initially before writing any code if you want to finish several questions in time. For the Junior to be in the top group of people, you should be able to answer all 5 questions. As for the senior: it varies greatly from year to year. You generally need to be within the top 20 to get to stage 2, but the actual score needed for that varies. In 2005, a 57 or above would have gotten you in. That means 4 questions solved correctly except for 1 test case in some question or even the 5th problem solved for some test cases. In 2006, the contest was quite a bit harder. A score of 48 got you in. If you solved 3 questions and some test cases on a 4th last year, you would have surely been invited to stage 2. To all writing, I wish you the best of luck. Hopefully, I will see some of you at stage 2 - that is if I don't screw up another question again.

Konstantin Lopyrev

[Martin]

As far as practicing goes, there's USACO and TopCoder. You might find TopCoder kind of hard, it's aimed at the university and higher crowd, but they're both worth looking at. Downside is you'd have to use Java or C or C++, but those are languages that you'll want to learn eventually anyways.

[PaulButler]

Martin @ Thu Feb 22, 2007 5:32 am wrote:

As far as practicing goes, there's USACO and TopCoder. You might find TopCoder kind of hard, it's aimed at the university and higher crowd, but they're both worth looking at. Downside is you'd have to use Java or C or C++, but those are languages that you'll want to learn eventually anyways.

TopCoder has a high-school section as well, with more reasonable questions.

[Reality Check]

I'd like to partner up and do some questions. I will be doing the junior and I'll do the senior next year.

[cool dude]

I am doing the senior one this tuesday. I hope i get one right

Edit: Whoever is doing junior one if you have any programming knowledge at all you'll be able to do the first 3 within the first hour easily. the last 2 are really tough. i remember from last year the last question was to make a game (forgot what its called anyone remember?)

[PaulButler]

cool dude @ Thu Feb 22, 2007 9:38 pm wrote:

I am doing the senior one this tuesday. I hope i get one right

Edit: Whoever is doing junior one if you have any programming knowledge at all you'll be able to do the first 3 within the first hour easily. the last 2 are really tough. i remember from last year the last question was to make a game (forgot what its called anyone remember?)

The Game of Life

[Clayton]

That question is ridiculously hard. I'm practising on it right now, although I don't expect to get it, especially as I didn't get it last year during the competition.

[klopyrev]

Game of Life is not that hard a question. I actually finished it today in class because my friend wanted to see the solution, so its an interesting coincidence that I see it here. For that question, you have to be familiar with such things as binary numbers, bit operations, etc. You also should be able to take a binary number which represents a state and convert it to its next generation. Basically, if you know how to do all those things, the question becomes as simple as generating the next generation from each original state, storing all that information in a linked list for each next generation and then doing a Breadth First Search backwards. Basically, you know that a state is a garden of eden if there is no state that it is a next generation of. If a state has a previous state or perhaps several, you just add them to your search at a level 1 higher than that of the state. Here is a quick example (I refer to possible boards as numbers). Here are several example linked lists:

1 -> [3,5,7]
3 -> [5]
5 -> [3]
7 -> null

If you initial state is 1, you would add the states 3, 5 and 7 to the queue at a depth of 1. Then, you would consider the state 3 at level 1. It has state 5 as its parent, but state 5 has already been added to the queue, so you don't add it again. The same for state 5, level 1. You don't add the 3, because it has already been in the queue. When you reach state 7, level 1, you see how it has a null list of previous generations, so we know its a garden of eden. Thus, the minimum possible solution is then just 1. If you have any questions about this, feel free to ask. You could also go to access.mmhs.ca/ccc for several solutions. I could send you mine if you want it, but it is not much different from the solution on the site (It is much shorter )

KL