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
bugzpodder




PostPosted: Wed Mar 02, 2005 9:08 pm   Post subject: (No 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...
Sponsor
Sponsor
Sponsor
sponsor
zylum




PostPosted: Wed Mar 02, 2005 9:13 pm   Post subject: (No 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?
Aidin Kashigar




PostPosted: Wed Mar 02, 2005 10:10 pm   Post subject: (No 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 Very Happy
bugzpodder




PostPosted: Thu Mar 03, 2005 12:09 am   Post subject: (No 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.
bugzpodder




PostPosted: Thu Mar 03, 2005 12:11 am   Post subject: (No 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 Very Happy


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
Aidin Kashigar




PostPosted: Thu Mar 03, 2005 12:13 am   Post subject: (No 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.
bugzpodder




PostPosted: Thu Mar 03, 2005 12:19 am   Post subject: (No 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.
thegoose




PostPosted: Thu Mar 03, 2005 6:36 am   Post subject: (No 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 Very Happy.
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.
Sponsor
Sponsor
Sponsor
sponsor
Drakain Zeil




PostPosted: Thu Mar 03, 2005 6:42 am   Post subject: (No 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.
thegoose




PostPosted: Thu Mar 03, 2005 6:44 am   Post subject: (No 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.
Aidin Kashigar




PostPosted: Thu Mar 03, 2005 7:56 am   Post subject: (No 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?
bugzpodder




PostPosted: Thu Mar 03, 2005 9:51 am   Post subject: (No 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)
zylum




PostPosted: Thu Mar 03, 2005 3:50 pm   Post subject: (No 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...
Aidin Kashigar




PostPosted: Thu Mar 03, 2005 4:37 pm   Post subject: (No 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 Laughing )
thegoose




PostPosted: Thu Mar 03, 2005 5:23 pm   Post subject: (No 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 Very Happy )
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.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

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


Style:  
Search: