Computer Science Canada

CCC 05

Author:	Drakain Zeil [ Sun Feb 13, 2005 11:33 am ]
Post subject:	CCC 05
It's coming around the 22nd, who's going to write it? (I didn't see any other topics on this, if there is close this)

Author:	zylum [ Sun Feb 13, 2005 1:14 pm ]
Post subject:
i thought its march 1st... hopefully this time i make stage 2...

Author:	Martin [ Sun Feb 13, 2005 2:18 pm ]
Post subject:
Not me. I don't qualify.

Author:	Drakain Zeil [ Sun Feb 13, 2005 3:05 pm ]
Post subject:
zylum wrote: i thought its march 1st... hopefully this time i make stage 2... I have the papers from the past few years, back to '01, they all seem to be the last Tuesday of every Febuary.

Author:	zylum [ Sun Feb 13, 2005 3:20 pm ]
Post subject:
http://contest-cemc.uwaterloo.ca/ccc/ tuesday march 1st 2005

Author:	Drakain Zeil [ Sun Feb 13, 2005 6:08 pm ]
Post subject:
I blame the leap year

Author:	thegoose [ Sun Feb 13, 2005 6:47 pm ]
Post subject:
It's definitely March the 1st. We also have a case of foreign invasion this year. See: http://cemc.uwaterloo.ca/ccc/2005_2/HongKong.shtml GO CANADA! (anybody want to place bets?)

Author:	bugzpodder [ Sun Feb 13, 2005 10:45 pm ]
Post subject:
i know one of the HK guys who is REALLY REALLY GOOD and if he participates, i think he will beat everyone in Canada. I will try to ask him to participate, thanks Richard for the link.

Author:	Tony [ Mon Feb 14, 2005 10:26 am ]
Post subject:
martin wrote: Not me. I don't qualify. A lot of us don't. Could somebody make sure to keep a copy of the questions and post them up here after the contest?

Author:	thegoose [ Mon Feb 14, 2005 11:59 am ]
Post subject:
bugzpodder wrote: i know one of the HK guys who is REALLY REALLY GOOD and if he participates, i think he will beat everyone in Canada. Bring it on. For the record, we owned them at the IOI. (420,360,300,290):(405,305,NM,NM), NM=no medal tony wrote: Could somebody make sure to keep a copy of the questions and post them up here after the contest? Sure...I'll take care of that. Do you also want solutions?

Author:	Tony [ Mon Feb 14, 2005 12:11 pm ]
Post subject:
thegoose wrote: tony wrote: Could somebody make sure to keep a copy of the questions and post them up here after the contest? Sure...I'll take care of that. Do you also want solutions? Thx. Could somebody else keep this in mind for the redundancy though? And yeah - solutions too, but separate. I want users to be able to try the problems out on their own, and submit/discuss different approaches to the problems.

Author:	bugzpodder [ Mon Feb 14, 2005 2:54 pm ]
Post subject:
thegoose wrote: bugzpodder wrote: i know one of the HK guys who is REALLY REALLY GOOD and if he participates, i think he will beat everyone in Canada. Bring it on. For the record, we owned them at the IOI. (420,360,300,290):(405,305,NM,NM), NM=no medal wow! who got 420?? must be a genious!!

Author:	Aidin Kashigar [ Tue Feb 15, 2005 1:55 pm ]
Post subject:
bugzpodder wrote: wow! who got 420?? must be a genious!! lol. as if you haven't seen the IOI scores before. so, any predictions on the last <senior> problem this year?

Author:	Tony [ Tue Feb 15, 2005 3:14 pm ]
Post subject:
well if the contest is anything like last year's, you'd have to ask your teacher and the guy next to you in an attempt to understand the question and my guess is: recursive algorithm

Author:	thegoose [ Tue Feb 15, 2005 3:26 pm ]
Post subject:
tony wrote: and my guess is: recursive algorithm Doubt they'll put pruning, since the solution will either a). takes too much skill. b). be too straight foward. c). solvable using a random algorithm. Betting on 4 being graphic theory (not graphics) and 5 being DP again. They might put 2-SAT/flow but I don't think Gord will be that evil (at least not on stage 1).

Author:	Tony [ Tue Feb 15, 2005 3:29 pm ]
Post subject:
ether way you can count on not learning that in school (unless you're in Massey ofcourse)

Author:	zylum [ Tue Feb 15, 2005 3:50 pm ]
Post subject:
generally how many people sovle the senior 4 and 5? what score does it usually take to get to stage 2?

Author:	Tony [ Tue Feb 15, 2005 4:12 pm ]
Post subject:
last year's results might be of interest Generally top 20~25 senior scores advance to stage 2. The required score fluctuates by year. In 2004 it had to be over 45 (out of 75) and unless my math is off.. out of 623 participants 52 people have scored more than 0 on problem 4 38 people have scored more than 0 on problem 5

Author:	thegoose [ Wed Feb 16, 2005 6:26 pm ]
Post subject:
tony wrote: Generally top 20~25 senior scores advance to stage 2. The required score fluctuates by year. In 2004 it had to be over 45 (out of 75) Generally, if you can hit 60, you're almost guarantteed to go to stage 2. The cutoff is usually in the mid-50s, last year was an exception because space turtle threw many of the serious practicing people off (I never saw something like that on other Olympiads before). I hope Donny don't make any problems this year. It's quite funny that for the past few years, 4 was a harder problem compared to 5. (DP vs. ugly 3D-geo for 04, modifiedMST/dijkastra vs. suffix tree for 03)

Author:	bugzpodder [ Wed Feb 16, 2005 7:19 pm ]
Post subject:
Aidin Kashigar wrote: bugzpodder wrote: wow! who got 420?? must be a genious!! lol. as if you haven't seen the IOI scores before. so, any predictions on the last <senior> problem this year? spoiling the fun I am just trying to make richard feel better about himself by boosting his ego (he hasnt got over a sore USACO score two months ago...). i pity him for what he is. =.=; dont take this the wrong way richard... but i think you really need to lighten up a bit

Author:	Aidin Kashigar [ Wed Feb 16, 2005 8:18 pm ]
Post subject:
bugzpodder wrote: spoiling the fun I am just trying to make richard feel better about himself by boosting his ego (he hasnt got over a sore USACO score two months ago...). i pity him for what he is. =.=; dont take this the wrong way richard... but i think you really need to lighten up a bit Another interesting post. Might as well be removed by one of the moderators to avoid a flame war.

Author:	thegoose [ Wed Feb 16, 2005 8:52 pm ]
Post subject:
Aidin Kashigar wrote: Another interesting post. Might as well be removed by one of the moderators to avoid a flame war. lol....Aidin, HE IS THE MODERATOR...I think... you got the solution for USACO Feb no.1 (Jersey politics, the crazy DP one) yet?

Author:	Aidin Kashigar [ Wed Feb 16, 2005 9:14 pm ]
Post subject:
no. I haven't. but I got the Aggressive Cows without a timeout. What about secret? Do you have the code for a flow alg that would run in time?

Author:	thegoose [ Thu Feb 17, 2005 6:53 am ]
Post subject:
I have O(TE+ElogE), but with a pretty big constant. I'm still trying to reduce the constant. It turned out that the algorithm I used was right, I just forgot to sort the edges by increase value in the edge graph. :(

Author:	zylum [ Mon Feb 28, 2005 3:45 pm ]
Post subject:
CCC tomorrow... goodluck everyone! there's a high probablity there will be a snow day for me tomorrow. will they postpone it if there is?

Author:	Paul [ Mon Feb 28, 2005 6:22 pm ]
Post subject:
Oy, can someone please please explain to me the purpose of the first for loop in the main procedure of the quicksort algorithm? Is it something that does nothing for the first iteration?

Author:	Bacchus [ Mon Feb 28, 2005 7:43 pm ]
Post subject:
hhmm... me think i dont stand a chance in hell in this contest ne who good luck to all (dont beat me to bad )

Author:	we64 [ Mon Feb 28, 2005 7:50 pm ]
Post subject:
don't know if you guys heard of dynamic programming.. it has been used intensively in the contest for the last 2 questions... recursive can do it but just take too long and not efficient..

Author:	zylum [ Mon Feb 28, 2005 8:53 pm ]
Post subject:
20-30cm of snow overnight in my area school buses will definetly be cancled... i guess ill have to take transit which normally takes me an hour to get to school, tomorrow will probably take 2 hours all this just for the CCC

Author:	Bacchus [ Mon Feb 28, 2005 9:23 pm ]
Post subject:
ya we're getting a bunch of snow here to, hopefully it wont be that much in the morning

Author:	Hikaru79 [ Tue Mar 01, 2005 8:01 am ]
Post subject:
Today's the big day! Contest will be written in about 5 hours for me... GOOD LUCK EVERYONE!

Author:	Drakain Zeil [ Tue Mar 01, 2005 5:55 pm ]
Post subject:
Just wrote the Junor one today... saddly, I didn't do anywhere as well as I should have, or thought I would have. Of the 5 questions, I only got the first three... However, I did them about 15 minutes each, and got them all. So there I was, opend to number four... and spent about 2 hours on the thing. I have no idea why it took so long... well, yes I do. I coded it poorly, made two checking systems at once without knowing it, and couldn't seperate them easily without more errors cropping up. Oh well.

Author:	azndragon [ Tue Mar 01, 2005 6:29 pm ]
Post subject:
Just wrote the senior one. Is it just me, or is it insanely easy this year? Question 1 was simple if statements and string manipulation, 2 was simple if statements (I made a simple game using the same concepts), question 3 was the only one I couldn't do. Not too sure if my method for question 4 is correct, but it worked for a few test cases I made up, and question 5 was pretty easy as well. Hope I do well, but can't get my hopes too high

Author:	nate [ Tue Mar 01, 2005 6:34 pm ]
Post subject:
I wrote senoir 2day as well. I got all 5 questions for the test cases they showed so who knows how well i did. But i agree the questions were easy the top 20 people will probably all have 75 points.

Author:	bugzpodder [ Tue Mar 01, 2005 6:38 pm ]
Post subject:
deleted

Author:	Hikaru79 [ Tue Mar 01, 2005 7:15 pm ]
Post subject:
May we start posting solutions? Or is there a minimum waiting time before we can start discussing the contest in detail, like there is for a lot of math contests? I'm interested in seeing a lot of the solutions for some of these..

Author:	Tony [ Tue Mar 01, 2005 7:18 pm ]
Post subject:
Please wait until the end of the week. Some schools have not yet written the contest due to snow conditions.

Author:	Bacchus [ Tue Mar 01, 2005 7:33 pm ]
Post subject:
all i can saw is: i probably failed soooo bad. i ont work that well under pressure with time limit lol spacially for programming

Author:	bugzpodder [ Tue Mar 01, 2005 8:09 pm ]
Post subject:
tony wrote: Please wait until the end of the week. Some schools have not yet written the contest due to snow conditions. good point

Author:	AsianSensation [ Tue Mar 01, 2005 9:40 pm ]
Post subject:
trust me, question 5 is not as easy as you think. I helped marked the whole contest afterward with Mr.Mckenzie, and trust me. Question 5 is probably the hardest question on that contest to get full marks on. 4 was pretty hard, but if you know the algorithm, you are all set. 3 was actually pretty easy if you didn't get jumbled up. 2 was easy. 1 was easy.

Author:	Hikaru79 [ Tue Mar 01, 2005 9:55 pm ]
Post subject:
AsianSensation wrote: 3 was actually pretty easy if you didn't get jumbled up. When Friday rolls along, I really wanna see question 3... I didn't even understand what it was asking. ******** were an entirely new concept to me, and trying to learn it from scratch from their vague instructions was too much for me I think I did well on every question besides that one though, so it's still OK... but I am still curious about #3.

Author:	AsianSensation [ Tue Mar 01, 2005 10:00 pm ]
Post subject:
yeah, just to let you guys know, the highest from our school is 46. It wasn't as easy as some people thought it were.

Author:	Andy [ Tue Mar 01, 2005 10:00 pm ]
Post subject:
well as in below 30?... we all generally did prety bad... my number three was supposed to work perfectly.. but it messed up... wtf.....

Author:	Andy [ Tue Mar 01, 2005 10:05 pm ]
Post subject:
what do you guys think the cut off for stage two will be this year?? high 40s again?

Author:	Hikaru79 [ Tue Mar 01, 2005 10:10 pm ]
Post subject:
AsianSensation wrote: yeah, just to let you guys know, the highest from our school is 46. It wasn't as easy as some people thought it were. We finished marking all of them?

Author:	zylum [ Tue Mar 01, 2005 11:19 pm ]
Post subject:
wtf? #5 was easy as hell... obviously you dont just loop to find the rank... well im not going to give the answer but i believe you just do something that starts with binary and rhymes with earch... first 2 were easy... seeing as i couldnt install java on the computers (i tried but not enough drive space) i had to use turing so 3 was tricky... i ended up using 2d arrays of size 1024x1024... im not sure whether its correct but it passed the two sample cases.

Author:	Drakain Zeil [ Wed Mar 02, 2005 7:08 am ]
Post subject:
I'll post up my answers to 1, 2 and 3 for the jr contest on Friday.

Author:	VC [ Wed Mar 02, 2005 11:06 am ]
Post subject:
Hey... about S5. A couple of us stayed after school to mark it the other day; what's interesting is that there are three test cases (of the 10) that threw everyone's algorithms off (one of which, I believe, resulted in a negative answer for our output!!!). So, what's interesting then... the markers expect the S5 program to give output within one minute of running time - I was sitting there marking mine, and the output came up at 59 seconds of run time (heh). Oh wait, but that answer was wrong... To anyone who has already gotten theirs marked, do your teachers allow you to hard-code/brute-force a program to yield specific output? I mean like, do your teachers not deduct the marks you could get for anticipating the exact input file in the example being used in the test case, and then just having a program output exactly what it wants...? Jes wondering...

Author:	bugzpodder [ Wed Mar 02, 2005 1:57 pm ]
Post subject:
obviously there was no way to get your hands on the data unless you cheat. besides your program gets sent in to waterloo if you make stage 2, and you'll get disqualified when they look at your program.

Author:	person [ Wed Mar 02, 2005 3:48 pm ]
Post subject:
ill post the answers for j5 on friday j4 was f***ing hard i spent 50 minutes on it and still didnt know where to start

Author:	Drakain Zeil [ Wed Mar 02, 2005 4:09 pm ]
Post subject:
j5 is the one I should have done instead. For j4 I made a 2-d array of 0s and 1s, then a "movement" to ones for as many steps to the most clockwise position (by doing a if, elsif, end if selection) and if no movement can be made, or you are out of steps, then exit and give your position on the grid of 0s and 1s. Saddly, I ran into a few errors, and could either get a wrong number (bad logic, fixed it), move nowhere (I was running my checks backwards), or only moved a maximum of 2 spaces... then I ran out of time.

Author:	Andy [ Wed Mar 02, 2005 4:46 pm ]
Post subject:
for some reason c++ wont allow you to have two d arrays with sizes over 512 by 512.... and my number three messed up... dunno why but it did.. damn... and holy crap.. who the hell said it was easy to do s5... did you look at the datas??? they're frigging huge... no way you can calculate it in 1 min unless you used some sort of binary search

Author:	thegoose [ Wed Mar 02, 2005 5:34 pm ]
Post subject:
No.5 was actually a well-known problem (if you have looked at foreigh Olympiads). The solution that I think the creaters of the problem had in mind was NlogN. I will put up my solution which ran for <1 second on all cases sometimes next week. It would really be unfair for the people who actually coded a NlogN or a Nsqrt(N) if a N^2 solution was allowed to run in time and get full points. I'm pretty sure that even with Turing, my code would run in about 5 seconds.

Author:	Andy [ Wed Mar 02, 2005 6:09 pm ]
Post subject:
hmm well at least my program was sent off.. to remark.. but i just thought that they should've told us the time limit... anyways, what do you guys think the cut off wll be this year? i really want to go to stage 2 but i dun think my score was high enough

Author:	bugzpodder [ Wed Mar 02, 2005 6:40 pm ]
Post subject:
massey has 8 apperances in stage 2 in the last 6 years. i dont think this is gonna extend.

Author:	bugzpodder [ Wed Mar 02, 2005 6:42 pm ]
Post subject:
thegoose wrote: No.5 was actually a well-known problem (if you have looked at foreigh Olympiads). The solution that I think the creaters of the problem had in mind was NlogN. I will put up my solution which ran for <1 second on all cases sometimes next week. It would really be unfair for the people who actually coded a NlogN or a Nsqrt(N) if a N^2 solution was allowed to run in time and get full points. I'm pretty sure that even with Turing, my code would run in about 5 seconds. my 15 line N^2 solution ran in <1 second for largest test case. i dont see the need to write a 100 line N log N solution.

Author:	Andy [ Wed Mar 02, 2005 6:43 pm ]
Post subject:
lol yea... not until nxt yr when andy kong makes it... hes really good.. if it werent for stupid mistakes.. he would've got 65

Author:	thegoose [ Wed Mar 02, 2005 7:38 pm ]
Post subject:
bugzpodder wrote: my 15 line N^2 solution ran in <1 second for largest test case. i dont see the need to write a 100 line N log N solution. I somehow doubt that a N^2 would run in less than 1 second for S5, after all, the input data has N=100,000. Can you please send me the code of your program via. E-mail?

Author:	bugzpodder [ Wed Mar 02, 2005 8:59 pm ]
Post subject:
bugzpodder wrote: massey has 8 apperances in stage 2 in the last 6 years. i dont think this is gonna extend. 10 appearences. I cant count. Jessie Lei x3 Me x3 John Doe, Rui Me, Wissam Bishara, and Gary Lambing one each. a couple of others were close to making it too

Author:	zylum [ Wed Mar 02, 2005 9:04 pm ]
Post subject:
thegoose wrote: bugzpodder wrote: my 15 line N^2 solution ran in <1 second for largest test case. i dont see the need to write a 100 line N log N solution. I somehow doubt that a N^2 would run in less than 1 second for S5, after all, the input data has N=100,000. Can you please send me the code of your program via. E-mail? yeah i was gonna say that too... turng takes about 3 seconds to loop through an empty loop up to ten million on my 800mhz. i doubt it will run in under a minute

Author:	bugzpodder [ Wed Mar 02, 2005 9:08 pm ]
Post subject:
well I lied. I found a bug in my code. I had size 10000 instead of 100000. so when getting an input of 100000, it just crashed... (still outputting stuff, !!) yeah, i didnt think it would work...

Author:	zylum [ Wed Mar 02, 2005 9:13 pm ]
Post subject:
what would the runtime be if i were using a binary search to find the rank and then inserting the new rank into the list? would it pass a worst case?

Author:	Aidin Kashigar [ Wed Mar 02, 2005 10:10 pm ]
Post subject:
thegoose wrote: It would really be unfair for the people who actually coded a NlogN or a Nsqrt(N) if a N^2 solution was allowed to run in time and get full points. I'm pretty sure that even with Turing, my code would run in about 5 seconds. I strongly disagree, for obvious reasons

Author:	bugzpodder [ Thu Mar 03, 2005 12:09 am ]
Post subject:
zylum wrote: what would the runtime be if i were using a binary search to find the rank and then inserting the new rank into the list? would it pass a worst case? insertion takes O(n). doing it for every element makes O(n^2). which means it wont work without some fancy optimization, (for example, estimiate if the value you are inserting would be closer to beginning or end of the array) and even then it would still take close to 60 seconds if not more.

Author:	bugzpodder [ Thu Mar 03, 2005 12:11 am ]
Post subject:
Aidin Kashigar wrote: thegoose wrote: It would really be unfair for the people who actually coded a NlogN or a Nsqrt(N) if a N^2 solution was allowed to run in time and get full points. I'm pretty sure that even with Turing, my code would run in about 5 seconds. I strongly disagree, for obvious reasons unless you write your code in assembly or that you optimized your code, it is highly unlikely that an O(n^2) algo would run in time. But I might be wrong, since you always seem have some tricks up your sleeves, Aidin

Author:	Aidin Kashigar [ Thu Mar 03, 2005 12:13 am ]
Post subject:
My code solved all of the given test cases in under 30 seconds. It's n^2. Compared to Richard's claim of <1 sec, it's slow but it stills gets the mark.

Author:	bugzpodder [ Thu Mar 03, 2005 12:19 am ]
Post subject:
well, I dont have the inputs but I assumed they are randomized... does your algorithm have a worst case (strictly increasing/decreasing list or always have the element in the middle maybe?) i'll be impressed if it runs under 30 seconds for every input.

Author:	thegoose [ Thu Mar 03, 2005 6:36 am ]
Post subject:
Nice....you're the mad pruner from now on, Aidin (remember USACO Dec?) To prune it so it runs under 30 seconds is still quite cool....you'll probably get away with that on the CCC. But try not to do that if we get pass CCC . I'm probably the only one who actually coded a worst-case nlogn (sorry if this is not the case). From what I heard, Simon Parent did a Nsqrt(N) and it ran pretty fast too. I basically discretized (donnu if this is the English term) the data by qsort, then cycled through the numbers and inserted them into a segment tree (more like a segment heap). My code is actually O(N) since the range is already specified, but if the range is not, it would be O(nlogn) with O(n) memory.

Author:	Drakain Zeil [ Thu Mar 03, 2005 6:42 am ]
Post subject:
Thats one thing I don't like about the time limits: processing times of different computers. I mean, if you wanted your school to do well, you'd get the most powerful computers to run the programs on.

Author:	thegoose [ Thu Mar 03, 2005 6:44 am ]
Post subject:
Drakain Zeil wrote: Thats one thing I don't like about the time limits: processing times of different computers. I mean, if you wanted your school to do well, you'd get the most powerful computers to run the programs on. Trying to run S5 in a second using a N^2 is gonna to take quite a powerful computer.

Author:	Aidin Kashigar [ Thu Mar 03, 2005 7:56 am ]
Post subject:
I'm not sure if my algo is N^2 after all. Here's what I do: create a table of pairs with <point, position> sort the table based on points and then position (nlogn) create an array of size 100000, initialized to all zeros (call this A) start from the largest element of the table, I take the position and the # of points of each element. I add A[points] to the total sum (which I later on divide by the # of elements) and then, increment all elements of A with indices higher than my position. And how do you get sqrt(n) in your runtime?

Author:	bugzpodder [ Thu Mar 03, 2005 9:51 am ]
Post subject:
thegoose wrote: Drakain Zeil wrote: Thats one thing I don't like about the time limits: processing times of different computers. I mean, if you wanted your school to do well, you'd get the most powerful computers to run the programs on. Trying to run S5 in a second using a N^2 is gonna to take quite a powerful computer. or an so-so one to get N^2 under 1 minute! i benchmarked 2 min for a worst case on a PIII 600Mhz... I assume a P4 would have a <1 min run time. wonder what happens if I turn compiler optimzation on 8)

Author:	zylum [ Thu Mar 03, 2005 3:50 pm ]
Post subject:
im not sure on this but i think my teacher said #4 has to run in under 30 seconds and #5 in under 60 seconds on a 350Mhz computer...

Author:	Aidin Kashigar [ Thu Mar 03, 2005 4:37 pm ]
Post subject:
the time limit is correct but there were no specified CPU power for the testing machine. It is likely that the 5th problem will be re-run on a computer with around 900Mhz CPU as they usually retest the top submissions at Waterloo. It would however be unfair to penalize the n^2 programs due to the fact that the choice of writing an n^2 algo might have been based on the 1 minute constraint. And I forgot to mention, NO PRUNING was used in my solution for S5. and i tested it for both decreasing and increasing sequences and it ran in under 1 minute in debug mode in VC (which is the opposite of compiler optimization )

Author:	thegoose [ Thu Mar 03, 2005 5:23 pm ]
Post subject:
Aidin Kashigar wrote: It would however be unfair to penalize the n^2 programs due to the fact that the choice of writing an n^2 algo might have been based on the 1 minute constraint. No offence, but I think that both of us (and Simon too) were had a pretty good idea of what the time limit should be. Also, the input size should ring a bell about the solving algorithm. However, I'm not saying that your program should not get the points. After all, it was much faster than the other N^2 solution:D. Now I'm not even sure what the creater of the problem had in mind of our solutions. From what I heard from Simon, we all came down to the same basic idea, which is to find the number of elements in a certain range. Instead of having a tree that branches into 2 subtrees, his structure divides into sqrt(N) subtrees. This brings the depth from logn to 2, which makes it a lot easier to code but slightly slower. (I yelled cheap at him for 10 minutes on MSN after he told me his solution ) So, can people start posting the scores in their schools here? This way, we can have a good guess on the cutoff for stage 2.

Author:	zylum [ Thu Mar 03, 2005 5:49 pm ]
Post subject:
bugzpodder wrote: zylum wrote: what would the runtime be if i were using a binary search to find the rank and then inserting the new rank into the list? would it pass a worst case? insertion takes O(n). doing it for every element makes O(n^2). which means it wont work without some fancy optimization, (for example, estimiate if the value you are inserting would be closer to beginning or end of the array) and even then it would still take close to 60 seconds if not more. well im using binary search to find the rank so i already know where to insert...

Author:	thegoose [ Thu Mar 03, 2005 6:23 pm ]
Post subject:
zylum wrote: well im using binary search to find the rank so i already know where to insert... But how do you insert? Binary search depends on the maintenance of an array and inserting an element in an array is worst-case O(n), when you always insert into the 1st element.

Author:	Andy [ Thu Mar 03, 2005 7:41 pm ]
Post subject:
the high scores from massey are 46 43 and 41.. sad but meh

Author:	Aidin Kashigar [ Thu Mar 03, 2005 8:53 pm ]
Post subject:
Banting (now where the heck is that? ) has top scores of 75 and 61. The 61 might be increased due to a dispute over problem S5 and the timelimit.

Author:	Andy [ Thu Mar 03, 2005 8:56 pm ]
Post subject:
damn... im guessing u got the 75?

Author:	thegoose [ Fri Mar 04, 2005 6:25 am ]
Post subject:
Here are the high scores that I'm aware of so far: Woburn: 74, 65, 65 KCI: 75, 65 Don Mills: 70, 60 (estimate) Other random Toronto schools: 75 (Vaughan Road), 75 (estimate, AY Jackson), 64 (estimate, Leaside), 60 (estimate, Sir John A Mac), 60 (estimate, Leaside) According to Ms. Plachata (the CS teacher at Woburn), the cutoff should be somewhere in the mid-60s. This is very likely the case since the timelimit made S5 quite a easy problem and 1-4 were also quite easy.

Author:	Drakain Zeil [ Fri Mar 04, 2005 7:03 am ]
Post subject:
I'll post up some of my answers to J1, 2 and 3 when I get to school.

Author:	zylum [ Fri Mar 04, 2005 8:28 am ]
Post subject:
thegoose wrote: Here are the high scores that I'm aware of so far: Woburn: 74, 65, 65 KCI: 75, 65 Don Mills: 70, 60 (estimate) Other random Toronto schools: 75 (Vaughan Road), 75 (estimate, AY Jackson), 64 (estimate, Leaside), 60 (estimate, Sir John A Mac), 60 (estimate, Leaside) According to Ms. Plachata (the CS teacher at Woburn), the cutoff should be somewhere in the mid-60s. This is very likely the case since the timelimit made S5 quite a easy problem and 1-4 were also quite easy. how would one get 74/75???

Author:	bugzpodder [ Fri Mar 04, 2005 9:05 am ]
Post subject:
thegoose wrote: Here are the high scores that I'm aware of so far: Woburn: 74, 65, 65 KCI: 75, 65 Don Mills: 70, 60 (estimate) Other random Toronto schools: 75 (Vaughan Road), 75 (estimate, AY Jackson), 64 (estimate, Leaside), 60 (estimate, Sir John A Mac), 60 (estimate, Leaside) According to Ms. Plachata (the CS teacher at Woburn), the cutoff should be somewhere in the mid-60s. This is very likely the case since the timelimit made S5 quite a easy problem and 1-4 were also quite easy. lol, if i were in this, i probably wont make it either

Author:	thegoose [ Fri Mar 04, 2005 4:05 pm ]
Post subject:
zylum wrote: how would one get 74/75??? No clue, I'll try to ask him at stage 2. Just wondering, did anybody here do no.3 the smart way (aka. not multiplying the matrices out, but use the min/max values of each matrice instead)?

Author:	Tony [ Fri Mar 04, 2005 4:12 pm ]
Post subject:
Alright, it's Friday afternoon. Time to see those questions Could somebody who has a copy post up Junior/Senior questions. Make new topics in this [Contests] forum in the following format. [CCC 2005] Level Number -- Name for example [CCC 2005] Senior 3 -- FooBar Post the question and sample case provided in the contest. If you want to share your solution as well, make a reply to your own topic.

Author:	gigaman [ Fri Mar 04, 2005 4:41 pm ]
Post subject:
YAY! i got a 47 on the Junior contest and that is the best in my school (Westmount) I beat Rhysticlight who got a 45 and came in 2nd

Author:	zylum [ Fri Mar 04, 2005 5:32 pm ]
Post subject:
meh, posted S1,2 and 5... someone else can do the rest

Author:	person [ Fri Mar 04, 2005 10:00 pm ]
Post subject:
can someone please...please...please...please...please post j4 on the forum btw: did i remember to say please

Author:	zylum [ Fri Mar 04, 2005 10:49 pm ]
Post subject:
if you post the problem statement, i may be able to provide a solution...

Author:	Drakain Zeil [ Sat Mar 05, 2005 8:24 am ]
Post subject:
J4 gave me problems too, I'll post up where I was at if you want (on monday, files = @ school)

Author:	person [ Mon Mar 07, 2005 5:14 pm ]
Post subject:
for some reason i only got 2 on j5. anyways i got 47/75 id like to see how my score compares with others

Author:	gigaman [ Tue Mar 08, 2005 11:05 am ]
Post subject:
Yah J4 gave me a lot of problems. I don't know why i got only 2 on J5 but i did.

Author:	Bacchus [ Tue Mar 08, 2005 8:00 pm ]
Post subject:
i need to find out my scores, o well did ne one do that ECOO (i think thats wat called) competition? groups of 4 starting with ur school board then regionals and then provincial and stuff? whos going to regionals? i kno i am (lol my team got 3rd in the school board)

Author:	Andy [ Tue Mar 08, 2005 8:04 pm ]
Post subject:
man.. my school doesnt have it.. i wish we did tho.. cuz i know we'd make it to provincials

Author:	gigaman [ Tue Mar 08, 2005 10:46 pm ]
Post subject:
i did the ECOO or ECCO or watever it is. my scool came in 6th. the only reason we didn't do better was because our school uses terrible dells and it took them forever to make the executabe from Turing. anyway i will be going back next year.

Author:	lordofall [ Wed Mar 09, 2005 12:10 am ]
Post subject:	ECOO and solutions
We came fourth in the ECOO cause our group made stupid mistakes and they killed 60 marks cause turing scrolls down when printing answers and the judges couldn't read it ah well we are going to the regionals . Number 4 was the easiest the wording was just confusing i can't believe virtual nobody solved it especially since it takes about 10 minutes to get the right answer(tho the sample output was wrong) And congrats Bacchus on getting to the provincials spot 3 beat us by 12 points the universitys gonna be really competitive but atleast our team can try again next year =^Ãž. heres the solution to p4 along with "some" test data that i just copied from the sheet. Some of the code is useless and i just put there to make fun of my partner since he was bothering me but it gets the job done and is fast enough. Message me if you need an explaination of the code. btw for the cross heres an example * = character F- spots u can enter(easier to read then T) @@@*FFFF@@@ line 1- 11 @@@FFFFF@@@ line 2 - 8 FFFFFFFFFFFFFFF line 3 - 3 FFFFFFFFFFFFFFF line 4 - 2 FFFFFFFFFFFFFFF line 5 -> whatever amount of steps u want it to take @@@FFFFF@@@ @@@FFFFF@@@ i only got 60/75 on the CCC but i came late so i'm still happy with it, plus they were testing us on some "forward" command that i never learned so i think we should all be proud although were not the best were still pretty good

Author:	thegoose [ Wed Mar 09, 2005 6:31 am ]
Post subject:
gigaman wrote: the only reason we didn't do better was because our school uses terrible dells and it took them forever to make the executabe from Turing. anyway i will be going back next year. lol..our school won ECOO with the Turing/Dell combo last year.....

Author:	Bacchus [ Wed Mar 09, 2005 8:05 am ]
Post subject:
ya we used dells this year, they suked and a few computers didnt even work but we still managed. and im not going to provincials... yet board is first which we passed and then comes regionals b4 provincials

Author:	person [ Wed Mar 09, 2005 8:17 pm ]
Post subject:
lordofall: i think theres an error with ur code "Array subscription out of range."

Author:	lordofall [ Wed Mar 09, 2005 8:43 pm ]
Post subject:
person wrote: lordofall: i think theres an error with ur code "Array subscription out of range." which program is it? none of them are bob proof, for the cross that probably means that the data you entered was a bit to large(for example the blocks to take out of the cross were bigger then the cross) either that or i made a mistake when the top row was filled (suppose to start on the second row but i never checked for that

Author:	person [ Thu Mar 10, 2005 5:47 pm ]
Post subject:
i cant remember wich one but i remember that i entered 2 and it wont work

Author:	lordofall [ Thu Mar 10, 2005 9:17 pm ]
Post subject:
person wrote: i cant remember wich one but i remember that i entered 2 and it wont work hmm ya dats prolly cross, as the other one is suppose to be all letters, and prolly for the reasons i told u they prolly said dat it wouldn't take too many rows cause i never got caught =^D.

Author:

gvc [ Fri Mar 18, 2005 10:34 pm ]

Post subject:

Here's a solution to S5. Well, not quite S5. It prints all the ranks and doesn't print the summary information that the question asks for.

It uses a trie, which takes advantage of the fact that the numbers all fit in 32 bits. So it is actually O(n) time; more precisely O(n log m) where n is the number of scores and m is the magnitude of the maximum possible score.

There are a number of O(n log n) algorithms that don't explicitly depend on m. But if you want to be really precise, most of them will be O(n log n log m) .

If you used binary tree insertion, you'd get the random cases and probably one of the ordered cases, but you wouldn't get them all because binary tree insertion will probably create a reasonably balanced tree, but in worst case will not. So you need to use some kind of self-balancing tree to get the worst-case behaviour right.

Aidin's solution, if I understand it right, basically halves the problem size. This can be very useful especially for problems for which a polynomial-time solution is not known. That is, you can do 2^30 operations while you wait, but 2^60 will take your lifetime and more.

As for the time limit, I'm not exactly sure how it was implemented at particular schools but it was my understanding that a calibration program was made available in some of the advance materials. It is really hard for us to guarantee even treatment across all schools, but it is safe to assume that you were not intended to be able to execute of the order of 5 billion comparisons in the time available. The solution below uses about 3 million.

I will very soon be assuming my role as ISC member for the IOI, so I won't be directly involved in the second stage. And I have no information beyond what I've seen here as to the mark cutoff. Good luck to the qualifiers.

code:

struct ss {
struct ss *left, *right;
int leftcnt;
} avails[3200000];

int i,j,k,n,s,t,cnt,c,toleft;
struct ss *avail = avails, *head, **p;

main(){
scanf("%d",&t);
for (cnt=0;cnt<t;cnt++) {
scanf("%d",&s);
p = &head;
c = cnt;
toleft = 0;
for (i=0;i<32;i++) {
if (!*p) *p = avail++;
if (s & (1<<(31-i))) { // left
c = (*p)->leftcnt;
(*p)->leftcnt++;
p = &(*p)->left;
} else {
c -= (*p)->leftcnt;
toleft += (*p)->leftcnt;
p = &(*p)->right;
}
}
printf("%d of %d\n",toleft+1,cnt+1);
}
}

Author:	thegoose [ Sat Mar 19, 2005 12:16 pm ]
Post subject:	Re: S5
gvc wrote: There are a number of O(n log n) algorithms that don't explicitly depend on m. But if you want to be really precise, most of them will be O(n log n log m) . Depends on whether you consider addition/substraction/comparison to be logm time I think Simon did the halving the size thing, I heard he did the same things for the Waterloo ACM contest (the ultra-quicksort question). What Aidin did (at least what I think he did) was basically a segment array with O(n) implementation but a smaller constant, my code was a logn implementation of the segment array (more like a segment heap). Since the data size was 100,000, what I heard that some schools did was they just ran the program on the server. In one case, the teacher even ran the program (which was the N^2 code) on a 5GHZ comp and it ran in 50 seconds. http://access.mmhs.ca/ccc/2005/CCC2005s5PinballRanking.txt has some more info about the time limit vs. machine.

Author:	gvc [ Sat Mar 19, 2005 12:41 pm ]
Post subject:	Re: S5
thegoose wrote: gvc wrote: There are a number of O(n log n) algorithms that don't explicitly depend on m. But if you want to be really precise, most of them will be O(n log n log m) . Depends on whether you consider addition/substraction/comparison to be logm time I Precisely. Many people ignore the fact that it is reasonable to assume that arithmetic operations are constant time only if the size of the operands is bounded by some constant. O() notation considers the run-time (or space or whatever is being measured) as the parameter's values tend to infinity. And it ignores constant factors. If there really were no bound on m (or a bound larger than, say 2^64) you would definitely have to consider the fact that arithmetic operations are not constant time. Addition and subtraction are linear time in the size of the integer (i.e. log of the magnitude) while naive multiplication and divison algorithms are quadratic. Better multiplication and division algorithms exist, but they're hard to implement. Naive comparison is linear time, but if the values are unequal and you know something about them, you might do better than linear time. The trie implementation that I gave doesn't actually do integer comparisions on its way to finding the right value to increment. But it does do additions to compute the cumulative ranks, so I guess I should've said that my implementation was O(n log^2 m) - looking up the value only takes O(n log m) single-bit comparisions, but computing the ranks requires full log-m-bit arithmetic.

Author:	thegoose [ Sat Mar 19, 2005 3:57 pm ]
Post subject:	Re: S5
gvc wrote: Many people ignore the fact that it is reasonable to assume that arithmetic operations are constant time only if the size of the operands is bounded by some constant. O() notation considers the run-time (or space or whatever is being measured) as the parameter's values tend to infinity. And it ignores constant factors. Addition and subtraction are linear time in the size of the integer (i.e. log of the magnitude) while naive multiplication and divison algorithms are quadratic. Better multiplication and division algorithms exist, but they're hard to implement. Naive comparison is linear time, but if the values are unequal and you know something about them, you might do better than linear time. Mine would have been O(NlogNlogM) then. I think I brought this up a while ago (sometime during camp last year), but I never got the conclusive answer for it. In terms of a CPU, what are the relative costs of adding/multiplication/comparison/memory access of say, int (32-bit) of C. Aka. how many of them can you do in a second on something like a P4 processor?

Author:	gvc [ Sat Mar 19, 2005 4:10 pm ]
Post subject:
The short answer is that the relative costs ususally don't matter - by and large the running time of your program is dominated by RAM access and the number of instructions executed. But in a very tight loop, you'll find that addition and subtraction are essentially free. Multiplication is relatively slow - maybe the equivalent of 10 additions. Division is 2-5 times slower still. Floating point is yet another factor of 2-10 slower again. So it is entirely possible that floating-point algorithms are dominated by the number of floating point operations. -- One last counterpoint about O() notation. O() notation is just a tool. In competition what matters is how much you can get done in the time available. If your algorithm uses a hundred million operations, it'll probably run in time. If more, you have to consider the possibility that it won't. In this situation, you should be estimating actual running time, not asymptotic complexity. So the "log m" discussion is of academic interest - it really has little relevance in deciding whether or not a solution to S5 is fast enough.

Author:	thegoose [ Sat Mar 19, 2005 8:31 pm ]
Post subject:
gvc wrote: by and large the running time of your program is dominated by RAM access Can you please go into some detail of why this is the case? (aka. why does RAM access take so much time)

Author:	gvc [ Sat Mar 19, 2005 10:21 pm ]
Post subject:
thegoose wrote: gvc wrote: by and large the running time of your program is dominated by RAM access Can you please go into some detail of why this is the case? (aka. why does RAM access take so much time) A typical CPU will have an internal clock speed of perhaps 2 GHz. That's 0.5 nanoseconds per cycle. The CPU will be able to do at least one - probably several - simple integer arithmetic operations in one cycle. RAM might be 200 MHz - that's 5 nanoseconds. So when you access RAM you have to waste about 10 cycles waiting for it. The CPU tries really hard to find something else to do while waiting for the RAM but it isn't all that easy. Also, the RAM is typically wider than 32 bits or whatever the word size is on your computer. So the CPU can actually read in a few words at a time, provided they are adjacent. It saves them in cache which won't slow the CPU down. So if you access RAM sequentially, you get a big saving for this and other reasons. But if you wander all over RAM, as you might while traversing a tree or using a hash table, you'll pay full price for each access. But perhaps I haven't really answered your question. RAM has vast storage capacity compared to what's in the CPU/cache. To keep it small and cheap and not too power hungry, different technology is used and that is slower. Also, there's a reasonably complex protocol that the CPU uses to talk to the RAM. It sends the address over the bus, waits for the RAM to pick up the address, then waits for the data to be transmitted to or from the RAM. It simply isn't possible to do this as quickly as a CPU cycle. More generally, there are time-distance tradeoffs. In 0.5 nanoseconds you can't send a signal very far and also you get all sorts of weird high-frequency electromagnetic effects. Not only the data, but the program itself, is stored in RAM. So if you have a large amount of code, especially if it branches all over the place, the time to read the instructions from RAM will be a big factor in the execution time of your program. But if you have a small loop with only a few instructions, it will likely all be read into cache, so will run pretty quickly. You can try a few experiments. Write a loop that runs a billion times. Then put a simple addition instruction into it and see if it slows it down. Then try unrolling the loop - repeat the body 1000 times and have the loop run only a milliion times. I'll leave it to your imagination to try different combinations. Trying to measure the time consumed by any particular instruction is really tough to do on a modern computer.

Author:	bugzpodder [ Tue Mar 22, 2005 5:26 pm ]
Post subject:
woah, we were just doing this in my CS class today... exact same info.... while we are on the subject of CCC, I am not sure if this information is announced publically or not, but stage 2 this year will be held on the last week of april i believe... and I'll decide if i want to volunteer for this and "babysit" some of you today or tomorrow =.=; after i make sure theres no conflict with my exams that is It is always amusing to listen to Troy/JP lecture.

Author:	thegoose [ Wed Mar 23, 2005 11:54 am ]
Post subject:
bugzpodder wrote: I'll decide if i want to volunteer for this and "babysit" some of you today or tomorrow =.=; after i make sure theres no conflict with my exams that is Are you gonna to do a talk?

Author:	Aidin Kashigar [ Wed Mar 23, 2005 9:59 pm ]
Post subject:
And also, should we expect a question from you at the 2nd stage?

Author:	bugzpodder [ Thu Mar 24, 2005 4:21 pm ]
Post subject:
i thought about it last night, and turned the option of meeting u guys down due to some personal reasons. I submitted a question to Troy but I have no idea if he'll use it or not... Prof Cormack (gvc?) will usually announce who made the problems so you'll know it if its mine or not. and I always use 'Jack' in the problem statement, so if they keep the original problem statement then it will possibly be my question. I made the problem just for you two (and Simon) so let me know if it gets used or not... Anyways, best of luck to you two for stage 2

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

Terms of Use | Privacy Policy