Thats what we said last year and stage 2 ends being around 62... remind you people in ib or ap can't go due to exams... like myself

Yeah 1, 2, 3 and 5 were so easy that I finished them within 1-1.5 hours.

But I just couldn't even think of an algorithm for problem 4, for I had trouble finding a good representation of each state.

Hello, I did the junior one, and the same problem appeared as J5.
Thankfully, after rocking my head trying to figure out how to do it, I was able to successfully analyze each case then use println.
Notice that for S4, n<8, while in J5, n<5, which made manual work possible (33 cases).

Can I get full marks with this approach? Where I just do the calculations by hand and just print the results out for each case?
If I do, then I have high chance of getting 75/75 which would be awesome considering this is my very first compsci competition.

How did you manage to play 33 towers of hanoi games in under 3 hours?

This year is really unfair for the good programmers. If S4 is not your type of question, which is a really bad exercise in recursion, then you're not making stage 2. There should be at least 2 really hard questions so the cutoff a near perfect score.

? That didn't make sense.

You have to get perfect to make stage 2 since 4 of the problems are trivial. What if it is an insane ad hoc problem (which is the case this year) that you just can't get? As a senior contest, where are the true computer science problems involving hard dynamic programming, recursion, graph theory or computational geometry that I like (actually I don't like graph theory)?

You have to get perfect to make stage 2 since 4 of the problems are trivial. What if it is an insane ad hoc problem (which is the case this year) that you just can't get? As a senior contest, where are the true computer science problems involving hard dynamic programming, recursion, graph theory or computational geometry that I like (actually I don't like graph theory)?

The last case for #4 was surprisingly easy; my extremely slow solution just passed with 49 seconds on my computer, so I tentatively have a perfect. (:

Hello, I did the junior one, and the same problem appeared as J5.
Thankfully, after rocking my head trying to figure out how to do it, I was able to successfully analyze each case then use println.
Notice that for S4, n<8, while in J5, n<5, which made manual work possible (33 cases).

Can I get full marks with this approach? Where I just do the calculations by hand and just print the results out for each case?
If I do, then I have high chance of getting 75/75 which would be awesome considering this is my very first compsci competition.

4.9/5 ... Just when i thought it was too easy. Its never perfect!!!!!!!! How do i know if i qualify for round 2

Same here.

Was it just factorial business? I didn't see a pattern

My script for 4 gets it after 48 sec for n=8 on cpython on my computer ... 16 sec on pypy. Given that my marker 's laptop is probably slower... maybe u should convince her to get pypy?

Oh yeah!!!! I got perfect 75~

Woah, congrats

This is my first computing contest....I got 60. Would that be enough to make it to honor roll or group 3?

also curious how people went about number 3 with the giant input. I had a frequency array of 1 - 1000 that would slowly increment values as it reads in the 2 million inputs then naively finds how many max values, second max values there are and then checked the 3 cases for the output (multiple max, 1 max, multiple second max, 1 max, 1 second max). My solution runs in about half a second in the worst case in c++.

What were other ways of going about that on (ideally more efficient)

For S3, after building the frequency table, you can iterate through the possible readings 1 to 1000 just once, keeping track of 6 variables: frequency, lower bound, and upper bound of the max-frequency and second-max-frequency readings. Then at the end, you check which case it is and work it out. E.g. If second max frequency is different from max (only one reading with max, so max_low=max_high), then take the bigger of (max_low - max2_low) and (max2_high - max_low), if one is negative the other's absolute value is bigger anyways.

Because you iterate in order, simplifications can be made such as only setting lower bound when a higher frequency is found and setting upper bound every single time the frequency matches. (You can even share one variable for the two upper bounds, since they are never simultaneously relevant, but it makes things confusing).


For S4, my friend came up with the idea to represent the state as an n-length array of n-bit binary numbers (integers), which might be the same as what user 102897108 means by "a number." Essentially, the coins are considered to be worth powers of two and each pile is represented by its total value, with moving a coin just equal to adding and subtracting the relevant entries. The smallest coin in a pile is equal to the smallest significant 1-bit, which can be calculated by the trick x&(-x).

Haha that's what i meant. But i guess what you wanted to say was that the coins are worth powers of N instead of powers of 2 )

Can anyone explain how the grade is calculated ?
Someone seems to have mentionned "full 75", but I only see 27 test files on the Robart website.

BTW my unoptimal S1, S2, S5 C solutions are here:
http://sites.google.com/site/bl0ckeduserssoftware/ccc-2012-partial-sols.zip
(I messed up S3, didn't know what to do for S4)

But why not just use BFS with the same state? BFS, I believe, would run much faster and be not much more difficult to code?

But I probably don't know best.

see this is why I love python. For S4 I just kept the state as a list and stored it in a dictionary, which has constant lookup time. In other words, I let python hash it for me

create a manual queue with an array and index of where you started. Ideally a flexible array/vector would be best to use for this purpose or at least something that you can quickly remove elements/indexes from. In C++ I normally use vectors for my queue in a bfs, but you can use makeshift ways of creating a queue.

To clarify, were you referring to a tuple instead of an actual Python list? Lists in Python are not hashable and cannot be used as dictionary keys.

ok, danc. Well, now after the last dwite and this, I have learned 2 new types in c++

Didn't know about pairs or queue. Both of those would make some problems much easier

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

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

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

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.

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

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

How do you know?

Results for the 2012 CCC will be posted on Monday, April 2, 2012.

Just get an e-mail from my teacher. I'm in!!! Couldn't be much more psyched right now. Our school got 4 people in the results booklet this year which I think is a school record (Beating the previous record of 1 that we set last year) between JCCC and CCC. Not bad for a small town school