Computer Science Canada

Mock CCC
Author:  A.J [ Sun Feb 14, 2010 1:53 pm ]
Post subject:  Mock CCC
Yea, it's that time of year again.

This year, Brian Bi (bbi5291 on compsci.ca) and I put together a mock CCC (senior...sorry that I couldn't make a junior this year) as practice for stage 1.

So, if you wanted some extra practice for the CCC, feel free to download this and try it at home. I would advise you to try recreating the 'CCC' environment as much as possible (i.e. give yourself 3 hours, do it with friends at school, follow the rules Laughing, etc...). Yes, I didn't make all the questions (like last year), as the person who had helped me come up with the questions last year graduated, and I also have Math Club to worry about...

Also, I would appreciate it if you don't discuss these problems here (as there are people in my school, and other schools, writing this).

Finally, if you feel confident enough about your programs, feel free to send them to me to amleshjayakumar at yahoo.ca .

Hope this helps.
Author:  chopperdudes [ Wed Feb 17, 2010 8:47 pm ]
Post subject:  RE:Mock CCC
is it possible for you to post some test cases? and CCC is next week, i think it would be more helpful if we can discuss solutions to these problems (or else it would be like... oh i can't do them, great, and i wouldn't know how to do them before CCC comes around).
Author:  A.J [ Wed Feb 17, 2010 11:01 pm ]
Post subject:  RE:Mock CCC
I'll post the test-cases later on this week (most likely Friday).

As for the discussion, I am going to say no for now, as there are some school's that are yet to write the contest (I need the green light from Brian too). So, this Friday you'll be able to discuss the solutions on here. However, I will be posting official solutions and programs for these problems on Saturday (or maybe Friday itself).

Depending on how many people are actually interested, I might move this date back a few days.

Also, any feedback is much appreciated.
Author:  chopperdudes [ Wed Feb 17, 2010 11:06 pm ]
Post subject:  RE:Mock CCC
oh was this made to be a real contest? i.e. not just wolburn/compsci? then yeah that would make sense, but please do discuss the solutions before the actual CCC.

do you think these questions mimic the difficulty of actual CCC senior questions? i don't know cuz from my impression senior might be harder, but it could be cuz the last time i saw a CCC question was... quite a long time ago.

i was able to tell the approach to 3 and 4 immediate after reading the question, granted, they probably aren't the optimal solutions, but with the low test case limits, they'll work. don't know bout the actual CCC though. 5 will take some thinking (which i didn't rly have time to do yet...) but i guess i'll be really happy if i can get 4 questions for the actual CCC and part marks for the 5th.
Author:  A.J [ Thu Feb 18, 2010 5:07 pm ]
Post subject:  RE:Mock CCC
I will definitely be releasing the solutions before the actual CCC. However, the WCC is made to be slightly harder than the actual CCC Stage 1 (however, some people might think otherwise). I believe that solving the first 4 questions perfectly on the WCC is quite a good mark. Also, you can email me your solutions if you believe to have solved a question, and I'll mark it for you.

Last year's CCC was probably a bit 'harder' than usual (though it was still pretty standard). The CCC from two years ago, however, was extremely easy for a stage 1 (and consequently, the cutoff for stage 2 was a 66/75, which is unusually high).

Though, I shouldn't be the one speaking, as I am not too experienced/good at CS. Brian should be the one measuring difficulties here Razz.
Author:  bbi5291 [ Thu Feb 18, 2010 6:24 pm ]
Post subject:  Re: RE:Mock CCC
A.J @ Wed Feb 17, 2010 11:01 pm wrote:
I'll post the test-cases later on this week (most likely Friday).

As for the discussion, I am going to say no for now, as there are some school's that are yet to write the contest (I need the green light from Brian too). So, this Friday you'll be able to discuss the solutions on here. However, I will be posting official solutions and programs for these problems on Saturday (or maybe Friday itself).

Depending on how many people are actually interested, I might move this date back a few days.

Also, any feedback is much appreciated.
Woburn holds its practice CCC on Friday from 15:00 to 18:00 (GMT -5:00). As long as posting of testcases/solutions/discussion doesn't start before then, I won't mind.

As for the difficulty of the Mock CCC, I will say that the first four problems are probably harder than their counterparts in the actual CCC 2009. As for S5, I think more than two competitors in Canada would be able to solve it completely (that's how many solved S5 on CCC 2009, "Wireless"); it's a more well-known problem. Overall, this is pretty tough, and if this were the actual contest, I'd estimate the stage 2 cutoff between 45 and 50. (It could be higher if more competitors would put more effort into writing partial solutions, an indispensable skill at IOI.)
Author:  DtY [ Thu Feb 18, 2010 7:46 pm ]
Post subject:  RE:Mock CCC
So the first four questions are overall harder than the actual questions have been in the past, but the fifth was easier?

And where can I find the guidelines for the competition?
Author:  A.J [ Thu Feb 18, 2010 8:24 pm ]
Post subject:  RE:Mock CCC
You mean for the CCC? Well, in that case, all the details can be found here: http://cemc.uwaterloo.ca/contests/computing.html
Author:  bbi5291 [ Thu Feb 18, 2010 8:31 pm ]
Post subject:  Re: Mock CCC
Not sure if the fifth problem is easier. It's more code, but the problem itself is well-known, so that very smart people would probably have some idea of how to solve it already. You can get partial marks by making some clever observations.

If we give you a contest easier than the real CCC, you'll get complacent Razz

I'm surprised that the rules for stage 1 are not online, but the basics are:
* The contest must be taken in three consecutive hours.
* You must work alone (i.e., you may not communicate with anyone but your proctor during the three hours)
* You can use any languages you want, except for symbolic computation languages (like Maple). You can use different languages for different problems if you wish.
* You can use any written/printed materials you wish, but may not access any electronic materials (except for a language reference, or possibly to email your solutions to your proctor, or something like that)
* Your output should match the format shown in the samples exactly, except that you are not required to print prompts.
Author:  chopperdudes [ Thu Feb 18, 2010 10:44 pm ]
Post subject:  RE:Mock CCC
okay in an attempt to do the questions, for number 3, are there gaps in the people numbered? i.e. will there be something like.. 1 -> 7, 1 -> 9, instead of 1 -> 2, 1 -> 3?

if it's the latter it'll make the code abit less of a hassle.
Author:  Zren [ Thu Feb 18, 2010 11:29 pm ]
Post subject:  RE:Mock CCC
For Q5, what way are we to end the test cases?

From the input description:
Quote:
The input is terminated by two zeros in place of the board size.


and from the test data it assumes we get the numTestCases first:
Quote:

5
5 5
7
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX
5 5
.XX.X
.....
Author:  saltpro15 [ Fri Feb 19, 2010 10:59 am ]
Post subject:  Re: Mock CCC
bbi5291 @ Thu Feb 18, 2010 wrote:
* You can use any languages you want, except for symbolic computation languages (like Maple). You can use different languages for different problems if you wish.


I'd like to add that if you qualify for stage 2 the only acceptable languages are Java/C++/Pascal.
Author:  A.J [ Fri Feb 19, 2010 1:42 pm ]
Post subject:  RE:Mock CCC
@Zren - Sorry about that...but follow what's written in the IO specs (i.e. end of input is indiciated by two '0 0').
Author:  bbi5291 [ Fri Feb 19, 2010 7:34 pm ]
Post subject:  Re: Mock CCC
saltpro15 @ Fri Feb 19, 2010 10:59 am wrote:
bbi5291 @ Thu Feb 18, 2010 wrote:
* You can use any languages you want, except for symbolic computation languages (like Maple). You can use different languages for different problems if you wish.


I'd like to add that if you qualify for stage 2 the only acceptable languages are Java/C++/Pascal.
No, Java's not allowed (although it's allowed at USACO). CCC stage 2 follows the IOI convention strictly: C/C++/Pascal only.
Author:  DtY [ Fri Feb 19, 2010 11:07 pm ]
Post subject:  RE:Mock CCC
The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf
Author:  mseo [ Sat Feb 20, 2010 2:08 am ]
Post subject:  Re: Mock CCC
hmm... since the friday has passed, is it okay if people discuss their solutions?

I think my answers to questions 1-4 are correct, but I have no idea how to approach question #5

CCC is in 4 days Sad
Author:  TerranceN [ Sat Feb 20, 2010 2:36 am ]
Post subject:  Re: RE:Mock CCC
DtY @ Fri Feb 19, 2010 11:07 pm wrote:
The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf


I believe you are misreading the input, I think you mixed up x and y. Look at the edits I made to the diagram, does that help?
Author:  DtY [ Sat Feb 20, 2010 8:26 am ]
Post subject:  Re: RE:Mock CCC
TerranceN @ Sat Feb 20, 2010 2:36 am wrote:
DtY @ Fri Feb 19, 2010 11:07 pm wrote:
The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf


I believe you are misreading the input, I think you mixed up x and y. Look at the edits I made to the diagram, does that help?
Ohh, I get what I was doing, (1,3), and (3,1) were both there, so when I went to make sure I was reading it right, I looked for (1,3), found (3,1) and saw it was there.

Thanks for the diagram

[edit] Woo, got it, except for being slow with the actual test data.
Is there a time limit on how long your program runs?
Author:  TerranceN [ Sat Feb 20, 2010 11:10 am ]
Post subject:  RE:Mock CCC
I don't think so, but I don't see how this would take a long time to run. How did you program this?

I would just go through each grid point and check if each point is in or on the circle, and have a total bitrate for each point and just increase that. I have no idea if that is how it is supposed to/the best way be done though (This year will be my first CCC).

The one that really has me stumped out of thoses is the degrees of seperation one. I have no idea where I would even begin. Any help would be appreciated.
Author:  DtY [ Sat Feb 20, 2010 11:28 am ]
Post subject:  RE:Mock CCC
That's how I did it, it worked fine on the sample input (really fast), but when I ran it on the actual test data (which you wouldn't get when you're doing the contest), it was too slow.

I'm sure it would have been fast enough if I was using C.

--
Actually, mine was a little different than that, I started with a grid filled with zeroes, then for each coffee shop with wifi, loop over every point within a square around that point, and if it's within a circle of the wifi, increment that point by the bitrate.
Author:  TerranceN [ Sat Feb 20, 2010 11:48 am ]
Post subject:  RE:Mock CCC
Ok, after looking at the test data I understand why it took so long. It's a grid of 1000 x-values by 30000 y-values, and there are about 1000 circles, some of which have radii of over 9000!!! But seriously, no matter what language you use that would take a long time. Here is an example of one of the circles

730 14872 17630 4

So you would have to check (2 * 17630) * (2 * 17630) (it would not let me put the squared symbol) points to see if they are in the circle (actually less cause they would not be on the grid, but still)... Now times that by about 500 (as the other 500 have small radii).
Author:  A.J [ Sun Feb 21, 2010 5:27 pm ]
Post subject:  Re: Mock CCC
Sorry about the delay guys. I have included solutions (in C++) to the problems with descriptions to #1 -> #4 in the programs. As for #5 (and a copy of #4), I have also included a word document with these.

Sorry about the delay once again.

Feel free to ask me any other questions,
AJ

(P.S: Continue to send me solutions if you want me to mark them)
Author:  A.J [ Sun Feb 21, 2010 6:15 pm ]
Post subject:  Re: Mock CCC
Ok, here's an updated solution of #5 (and by updated, I mean better).

This solution is due to Brian Bi, Woburn Collegiate Institute (similar to my solution but more precise):
"First we make two critical observations:

1. The order in which tiles are tapped is irrelevant.
2. Tapping a tile twice is the same as not tapping it at all.

Combining these two observations yields the result that all we have to do is pick some subset of the tiles, then tap each tile in that subset exactly once. Each tile on the billboard is either tapped or not tapped, so on a 16 ? 16 billboard, there are 2256 different subsets to try. Attempting to try them all will clearly time out, but can earn 5 of the 15 points.

A smarter strategy is needed to get 15/15. Here's what we do. Notice that since we may tap tiles in any order, it is acceptable to tap them row by row: that is, we start by tapping any tiles we wish to tap on the first row, then we move on to the second one, and so on, never revisiting a row. Now notice that once we have tapped our tiles on the first row, some tiles may still be black on the first row. The only way to make these white now is to tap the tiles directly underneath them in the second row. Furthermore, we cannot tap any additional tiles on the second row, because this would flip some additional tiles on the first row, turning them black. That is, once we have tapped the first row, we immediately know which tiles to tap on the second. But then this immediately tells us which tiles to tap on the third row, for the same reason: we tap exactly those tiles on the third row that are now below black tiles on the second row. And so on, down to the last row. If we are lucky, after tapping tiles on the last row there will not remain any black tiles. We brute-force all possible subsets of tiles on the first row to tap, in each case chasing the tiles down to the last row and counting our taps as we do so. We then report the lowest count associated with a completely white billboard. If none of the combinations we try gives a completely white billboard at the end, we know it is impossible, and report that the billboard is damaged."
Author:  DtY [ Sun Feb 21, 2010 8:58 pm ]
Post subject:  Re: RE:Mock CCC
TerranceN @ Sat Feb 20, 2010 11:48 am wrote:
Ok, after looking at the test data I understand why it took so long. It's a grid of 1000 x-values by 30000 y-values, and there are about 1000 circles, some of which have radii of over 9000!!! But seriously, no matter what language you use that would take a long time. Here is an example of one of the circles

730 14872 17630 4

So you would have to check (2 * 17630) * (2 * 17630) (it would not let me put the squared symbol) points to see if they are in the circle (actually less cause they would not be on the grid, but still)... Now times that by about 500 (as the other 500 have small radii).
Actually, the way you worded that made me realize that you could instead loop over a quarter of that, the top right corner, and set four points, the remaining three quadrants each time. Since in a high level language like python, most of the overhead is in all the iteration, it would probably drastically increase the speed.

You could also get a good speed increase by using C arrays (via numpy) instead of python lists (since C arrays can be modified in constant time, whereas python lists have slower lookups in deeper elements). You probably wouldn't be able to use numpy though, since it's not part of the std python install, and I'm not sure what reason schools would have to install it.
Author:  A.J [ Sun Feb 21, 2010 9:06 pm ]
Post subject:  RE:Mock CCC
Guys, this thread is strictly for the Mock CCC. Any discussion of other CCC problems should be taken to a separate thread.

Thanks
Author:  jimjim168 [ Sun Feb 21, 2010 9:47 pm ]
Post subject:  Re: RE:Mock CCC
DtY @ 2010-02-20, 12:07 pm wrote:
The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf


Hey man, you see, the point in left-bottom is (1,1). And the east-west road passing (1,1) pointing at the east is the X-axis.
The north-south road passing (1,1) pointing at the north is the Y-axis. So needless to say, the sample input is right... Cuz the description says the input is X,Y, which are X-coordinate and Y-coordinate...
BTW, Do you think that University of Waterloo can make such a mistake? Laughing

P.S: I ain't a Canadian so there might be some grammar mistakes in my expression...
Author:  A.J [ Sun Feb 21, 2010 10:40 pm ]
Post subject:  RE:Mock CCC
Guys....seriously, another thread!
Author:  DtY [ Sun Feb 21, 2010 11:14 pm ]
Post subject:  RE:Mock CCC
Sorry for the off topic discussion, it just threw me off that it gave height then width, but x then y (the two pieces of information they gave you were backwards from each other).

Btw, thanks for these questions, donno if I said that already
Author:  A.J [ Sun Feb 21, 2010 11:57 pm ]
Post subject:  RE:Mock CCC
Oh, no problem. Thanks should also go to Brian, who helped me arrange the problem set and converted it to Latex

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy