Ccc 2012
Author 
Message 
Advecticity

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



smaxd

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

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

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


Did anyone write it in Turing? lol






D. McSmurfin

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

Posted: 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?
If this is true, then everyone who advances to stage two will be able to solve (almost) all of the problems!






VK_eipi

Posted: 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 breadthfirst 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

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

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

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


does anyone know what the cutoff marks will be around?






VK_eipi

Posted: 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 n1 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 n1 and n2, leading to the same order of magnitude as my original estimate for large n. The reason is that a number of neighbours below (n1) 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 counterexamples. 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

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

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

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






D. McSmurfin

Posted: 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?







