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

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




PostPosted: Sat Mar 03, 2012 8:37 pm   Post subject: RE:Ccc 2012

What's the O() running time for the solution of S4?
Sponsor
Sponsor
Sponsor
sponsor
smaxd




PostPosted: Sun Mar 04, 2012 12:36 pm   Post subject: Re: Ccc 2012

I did the Junior competition during the CCC. Got all but J5 perfect. Yesterday did a mock run through of the senior competition.
Got all but S4 perfect. fml
bbi5291




PostPosted: Sun Mar 04, 2012 1:31 pm   Post subject: Re: Ccc 2012

I've put the CCC 2012 problem descriptions and test data up on the PEG Judge, so you can try solving problems you didn't get during the contest, or whatever. You're limited to 60 seconds of execution time and 1 GiB of memory.
Snario




PostPosted: Sun Mar 04, 2012 2:01 pm   Post subject: RE:Ccc 2012

Did anyone write it in Turing? lol
D. McSmurfin




PostPosted: Mon Mar 05, 2012 9:16 pm   Post subject: RE:Ccc 2012

I hear CCC Stage 2 is going to be easier than Stage 1 this year.
ihsh




PostPosted: Mon Mar 05, 2012 10:37 pm   Post subject: Re: RE:Ccc 2012

D. McSmurfin @ Mon Mar 05, 2012 9:16 pm wrote:
I hear CCC Stage 2 is going to be easier than Stage 1 this year.

Where did you hear this from? Shocked
If this is true, then everyone who advances to stage two will be able to solve (almost) all of the problems!
VK_eipi




PostPosted: Wed Mar 07, 2012 1:11 am   Post subject: Re: RE:Ccc 2012

Advecticity @ Sat Mar 03, 2012 5:37 pm wrote:
What's the O() running time for the solution of S4?


For naive breadth-first search with a set storing visited states, checking expanded neighbours for membership in the visited set totals to O(E log V) and adding new vertices to the set is O(V log V) so running time is O((E+V) log V).

From my own data for n=3 to 7, it looks like, in the worst cases, V approaches n^n and E approaches n^(n+1). So that is O((n^(n+1)+n^n) log(n^n)) = O(n^(n+1) n log n) = O(n^(n+2) log n)

There is probably a much more efficient way of doing it, though. Does anyone have one to share?
d310




PostPosted: Wed Mar 07, 2012 8:06 pm   Post subject: Re: Ccc 2012

I would like to correct you.
BFS has a runtime of O(V+E), you've mixed it up with Dijkstra's runtime of O((E+V) log V) (for a binary heap).
I agree with the n^n vertices statement, but for the number of edges... not so much.
Firstly n^(n+1) assumed that each vertex is connected to n other neighbours, but evidently that is sometimes impossible (e.g. all coins are in one stack). Additionally the graph is definitely not completely connected (as seen with the IMPOSSIBLE test cases), and you forgot to account for the same edge being used twice in your estimate.
So an overestimate for the number of edges is n^(n+1)/2.

I also disagree with the O(V log V) runtime for state checking. This can be reduced to O(Vn) (see ihsh's comment on 3110, meaning coin 0 is in stack 3, coin 1 is in stack 1, and so on), with the use of computer number systems.
Thus:
O(V+E+Vn)
=O(n^n+n^(n+1)/2+n^(n+1))
Simplified to
O(n^(n+1))

The runtime based on the unsimplified expression is about 9.5 million operations in the worst case of n=7.
This translates to roughly 1 second on a modern computer, for each game.
A.J




PostPosted: Wed Mar 07, 2012 8:10 pm   Post subject: Re: RE:Ccc 2012

D. McSmurfin @ Mon Mar 05, 2012 9:16 pm wrote:
I hear CCC Stage 2 is going to be easier than Stage 1 this year.


I can assure you that this won't be the case. Don't take Stage 2 too lightly. A good way to prepare for it is to take a look at some of the past Stage 2 problems, and maybe some other national olympiads.
mirhagk




PostPosted: Wed Mar 07, 2012 8:26 pm   Post subject: RE:Ccc 2012

does anyone know what the cut-off marks will be around?
VK_eipi




PostPosted: Thu Mar 08, 2012 2:37 am   Post subject: Re: Ccc 2012

d310 @ Wed Mar 07, 2012 5:06 pm wrote:
I would like to correct you.
BFS has a runtime of O(V+E), you've mixed it up with Dijkstra's runtime of O((E+V) log V) (for a binary heap).
I agree with the n^n vertices statement, but for the number of edges... not so much.
Firstly n^(n+1) assumed that each vertex is connected to n other neighbours, but evidently that is sometimes impossible (e.g. all coins are in one stack). Additionally the graph is definitely not completely connected (as seen with the IMPOSSIBLE test cases), and you forgot to account for the same edge being used twice in your estimate.
So an overestimate for the number of edges is n^(n+1)/2.

I also disagree with the O(V log V) runtime for state checking. This can be reduced to O(Vn) (see ihsh's comment on 3110, meaning coin 0 is in stack 3, coin 1 is in stack 1, and so on), with the use of computer number systems.
Thus:
O(V+E+Vn)
=O(n^n+n^(n+1)/2+n^(n+1))
Simplified to
O(n^(n+1))

The runtime based on the unsimplified expression is about 9.5 million operations in the worst case of n=7.
This translates to roughly 1 second on a modern computer, for each game.


My mistake. The operations I thought would use logarithmic time are constant time on average (with hash table or similar data structure), so like you said, log V does not play a part and it's just O(V+E)=O(n^(n+1)). Thank you for the corrections (I didn't even account for state checking against the solution).

For the number of edges, I agree that n neighbours per vertex is an overestimate; in fact, the maximum for any vertex is n-1 neighbours (for each pair of adjacent piles). However, it turns out that this maximum occurs surprisingly often, such that the average neighbours per vertex is usually between n-1 and n-2, leading to the same order of magnitude as my original estimate for large n. The reason is that a number of neighbours below (n-1) occurs only when there are 2 or more adjacent empty locations, which is rarely required for larger n where the coins are generally spread out. I also doubt the significance of the IMPOSSIBLE cases, since I only found one ("2 1") but I'm open to counter-examples. As for dividing by two for each edge, I did not keep track of parent states in my algorithm so I had to think about both directions. Perhaps that was a mistake, but I didn't want to store to essentially double the size of my states.
crossley7




PostPosted: Tue Mar 20, 2012 9:51 pm   Post subject: RE:Ccc 2012

We are now 3 weeks removed from doing the contest. Anyone have an idea of when round 2 competitors come out? I don't remember from last year and it isn't up on the website yet. Still 2 months until round 2, but it would be nice to know if I qualified
d310




PostPosted: Tue Mar 20, 2012 10:12 pm   Post subject: Re: Ccc 2012

Well, a date listed on last year's results was March 29, 2011 (on Comments, page 2). So expect results to come out around the end of March.
crossley7




PostPosted: Tue Mar 27, 2012 6:03 pm   Post subject: RE:Ccc 2012

Quote:
Result for the 2012 CCC will be posted by Friday morning.


Results are finally almost here. Not sure why, but that is about the only thing that has been in my mind when I'm not completely zoned in on work this past week. I'll be glad to finally know how I did so I can stop worrying about it Very Happy
D. McSmurfin




PostPosted: Thu Mar 29, 2012 9:22 pm   Post subject: Re: RE:Ccc 2012

Quote:
Result for the 2012 CCC will be posted by Friday morning.


How do you know? Confused
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 9  [ 122 Posts ]
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Jump to:   


Style:  
Search: