CCC 05
Author 
Message 
Drakain Zeil

Posted: Sat Mar 05, 2005 8:24 am Post subject: (No subject) 


J4 gave me problems too, I'll post up where I was at if you want (on monday, files = @ school)






Sponsor Sponsor



person

Posted: Mon Mar 07, 2005 5:14 pm Post subject: (No 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






gigaman

Posted: Tue Mar 08, 2005 11:05 am Post subject: (No subject) 


Yah J4 gave me a lot of problems. I don't know why i got only 2 on J5 but i did.






Bacchus

Posted: Tue Mar 08, 2005 8:00 pm Post subject: (No 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)






Andy

Posted: Tue Mar 08, 2005 8:04 pm Post subject: (No subject) 


man.. my school doesnt have it.. i wish we did tho.. cuz i know we'd make it to provincials






gigaman

Posted: Tue Mar 08, 2005 10:46 pm Post subject: (No 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.






lordofall





thegoose

Posted: Wed Mar 09, 2005 6:31 am Post subject: (No 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.....






Sponsor Sponsor



Bacchus

Posted: Wed Mar 09, 2005 8:05 am Post subject: (No 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






person

Posted: Wed Mar 09, 2005 8:17 pm Post subject: (No subject) 


lordofall: i think theres an error with ur code
"Array subscription out of range."






lordofall

Posted: Wed Mar 09, 2005 8:43 pm Post subject: (No 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






person

Posted: Thu Mar 10, 2005 5:47 pm Post subject: (No subject) 


i cant remember wich one but i remember that i entered 2 and it wont work






lordofall

Posted: Thu Mar 10, 2005 9:17 pm Post subject: (No 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.






gvc

Posted: Fri Mar 18, 2005 10:34 pm Post subject: S5 


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 selfbalancing tree to get the worstcase 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 polynomialtime 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<<(31i))) { // 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);
}
}







thegoose

Posted: 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 ultraquicksort 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.







