CCC 2011 - Are you ready?

[z_cross_fire]

Hm, so the CCC is on Tuesday, March 1, 2011. How many of you feel prepared for it?

DWITE is on February 23, 2011 if you still need practice.

I still feel un-prepared.
So, tell me how are you guys preparing for it, and what programming language do you guys plan to use?

Discuss...

[Tony]

AJ will be trying to turn up the difficulty of DWITE to match it closer to CCC. It would be strongly encouraged to participate in the next DWITE round (if the timing doesn't work, all the questions and test data become public after the contest).

I would also remind you guys that about a collection of tips we have posted at http://compsci.ca/blog/getting-ready-for-the-canadian-computing-competition/

[RandomLetters]

Great blog post!

I'm still in the habit of churning out code that is "about right" and then debugging it. Although the code makes sense it is slow X(

The CCC keeps mentioning efficiency and speed but I can not find any grading information on it. How is the time graded? Is there a limit (ie, 15 seconds) that has a penalty if you go over or do you get more points the faster it is? Is this even important as long as it does not time out?

[Tony]

It's pass/fail for test cases, as long as it doesn't time out, for some definition of "time out".

You can approximate that large data sets with quadratic solutions is bad news, but if you can't come up with more efficient algorithms, then naive solutions could still often get partial marks, depending on the test cases.

[bbi5291]

Tony @ Mon Feb 07, 2011 10:35 pm wrote:

It's pass/fail for test cases, as long as it doesn't time out, for some definition of "time out".

You can approximate that large data sets with quadratic solutions is bad news, but if you can't come up with more efficient algorithms, then naive solutions could still often get partial marks, depending on the test cases.

I cannot emphasize the importance of this enough. Partial marks can make the difference between making the honour roll and not making the honour roll. Partial marks can make the difference between making the honour roll and making stage 2. Partial marks can make the difference between making the IOI and not making the IOI. And partial marks can, and do, make the differences between IOI medals. If you cannot find a nice solution to a problem, code up an ugly, inefficient, hackish solution --- after all, if you can solve the problem at all, that's already commendable, and nobody expects you to have good coding style when your time is so constrained (and plus your coding style is not marked anyway, although some people think it should be). Who knows, you might get 5 points out of 15 on problem 3, and beat all the kids who didn't bother to submit anything for problem 3, and hence get on the honour roll.

[A.J]

Having said that though, keep in mind that these questions are intended to be solved in the given time limit for the given constraints. One very useful tip when considering how efficient your code should be is to consider the bounds of the input data (this might also tell you what the required complexity is).

Unlike real world problems, where a solution doesn't necessarily exist, use the fact that all the problems are written solely for one purpose: to test your ability in solving them.

[z_cross_fire]

Tony @ Mon Feb 07, 2011 7:15 pm wrote:

AJ will be trying to turn up the difficulty of DWITE to match it closer to CCC. It would be strongly encouraged to participate in the next DWITE round (if the timing doesn't work, all the questions and test data become public after the contest).

I would also remind you guys that about a collection of tips we have posted at http://compsci.ca/blog/getting-ready-for-the-canadian-computing-competition/

Thanks Tony, the blog entry provides some nice tips
I also registered on the USACO training website, but then found out that it did not support C# submissions (though I can still try the problems). It's because I'm planning on using C# for the CCC (even though I'm new to it).

Also, I'm definitely looking forward to the next DWITE contest

I have another question as well: What are some methods for solving questions that involve lots of visual stuff? For example, Problem S4 - Animal Farm, which can be found here:
http://www.cemc.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

Any tips on solving this particular question? I saw a few solutions for it, but I would appreciate it if some of you here can tell me your methods.


Thanks,
z_cross_fire

[Tony]

1) You recognize that as a graph problem. That comes from experience. Once you map the problem description to a graph, there are many standard ways of solving many types of questions.

2) Use paper -- http://compsci.ca/blog/super-paper-programming/

[hamid14]

I'm ready as I'll ever be. Using Java FTW.

[A.J]

@z_cross_fire - Refrain from using this thread to ask specific questions regarding past contests. Create a new thread for any questions you may have. Having said that, since you have already posed your question regarding S4 2010, I feel obligated to answer:
This problem was one of the harder graph theory questions on the CCC. Like Tony mentioned, recognizing its a graph theory problem leads to the usage of Minimum Span Tree algorithms, like Prim's algorithm. The trick is to run the MST algorithm on the dual of the given graph (http://en.wikipedia.org/wiki/Dual_graph).

[z_cross_fire]

A.J @ Thu Feb 10, 2011 11:14 am wrote:

@z_cross_fire - Refrain from using this thread to ask specific questions regarding past contests. Create a new thread for any questions you may have. Having said that, since you have already posed your question regarding S4 2010, I feel obligated to answer:
This problem was one of the harder graph theory questions on the CCC. Like Tony mentioned, recognizing its a graph theory problem leads to the usage of Minimum Span Tree algorithms, like Prim's algorithm. The trick is to run the MST algorithm on the dual of the given graph (http://en.wikipedia.org/wiki/Dual_graph).

I'm sorry about that.
The idea about dual graphs seems a little complicated. I will definitely look into it.
Anyways, thanks for replying.

[ultimatebuster]

Not that prepared considered I'm writing it at 8:30 in the morning tomorrow.

First time writing this contest. I don't have any teachers who knows how to mark these contests and have experiences. How do you get marks from these contests? Is someone willing give me a quick run down on this? Thanks!

[techietim]

ultimatebuster @ Mon 28 Feb, 2011 7:37 pm wrote:

Not that prepared considered I'm writing it at 8:30 in the morning tomorrow.

First time writing this contest. I don't have any teachers who knows how to mark these contests and have experiences. How do you get marks from these contests? Is someone willing give me a quick run down on this? Thanks!

The grader for you will take your program, run it, then test is against data. Your school received, along with the question booklets, an additional grader booklet that contains input to feed into the programs and the expected output for each question. This is done after the contest is completed.

Since each question is worth 15 points, there are usually around 5 test cases; 3 points each. So if your code is not bullet proof, it is possible to get partial points for a question.

I believe (and anyone correct me if I'm wrong) that if your teacher grades your work and you receive over ~50%, they are required to submit your code to Waterloo, to ensure it was marked correctly.

[ultimatebuster]

techietim @ Mon Feb 28, 2011 7:39 pm wrote:

ultimatebuster @ Mon 28 Feb, 2011 7:37 pm wrote:

Not that prepared considered I'm writing it at 8:30 in the morning tomorrow.

First time writing this contest. I don't have any teachers who knows how to mark these contests and have experiences. How do you get marks from these contests? Is someone willing give me a quick run down on this? Thanks!

The grader for you will take your program, run it, then test is against data. Your school received, along with the question booklets, an additional grader booklet that contains input to feed into the programs and the expected output for each question. This is done after the contest is completed.

Since each question is worth 15 points, there are usually around 5 test cases; 3 points each. So if your code is not bullet proof, it is possible to get partial points for a question.

I believe (and anyone correct me if I'm wrong) that if your teacher grades your work and you receive over ~50%, they are required to submit your code to Waterloo, to ensure it was marked correctly.

Thanks for that. I believe I can get over 50%, since I should be able to solve 3 questions no problem. I just need some good luck with thinking of all the possibilities. Any tips? I'm doing junior contest.

[mirhagk]

So does it have to be a specific language so that waterloo can mark it?