Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Ccc 2012
Author Message

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

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

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

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 cut-off 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 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

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?
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 7 of 9  [ 122 Posts ]
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: