Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 CCC 05
Index -> Contests
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Drakain Zeil




PostPosted: 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
Sponsor
sponsor
person




PostPosted: 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 Very Happy
gigaman




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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. Sad anyway i will be going back next year.
lordofall




PostPosted: 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 Evil or Very Mad ah well we are going to the regionals Very Happy. 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 Razz spot 3 beat us by 12 points Very Happy 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 Smile



solutions.zip
 Description:
Three is a solution to p4 of ecoo with the sample data41.
one of the other ones is the commented code for J4 of the CCC and the exe is J4 but it draws the character as it journeys across the cross so you can see it

Download
 Filename:  solutions.zip
 Filesize:  168.12 KB
 Downloaded:  73 Time(s)

thegoose




PostPosted: 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. Sad anyway i will be going back next year.

lol..our school won ECOO with the Turing/Dell combo last year.....
Sponsor
Sponsor
Sponsor
sponsor
Bacchus




PostPosted: 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 Razz board is first which we passed and then comes regionals b4 provincials
person




PostPosted: 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




PostPosted: 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 Embarassed
person




PostPosted: 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




PostPosted: 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 Razz they prolly said dat it wouldn't take too many rows cause i never got caught =^D.
gvc




PostPosted: 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 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);
   }
}
thegoose




PostPosted: 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 Very Happy
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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 7 of 8  [ 114 Posts ]
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8  Next
Jump to:   


Style:  
Search: