Ccc 2007!

[Naveg]

I did the CCC Senior today, as I'm sure many other people on this site did as well. How did you all find it?

[Clayton]

I found it pretty good. Finished S1 in ~10 minutes, S2 took a little more time purely because I was thinking about it in the wrong way. Then for the last 2 hours I worked solid on S5 and pwned it

[klopyrev]

That was a fun contest!!! I finished 1-4 in the first 1 hour. 4 was too easy. Took me 2 hours to finish 5. There is 1 problem though. My teacher started marking my work and it had a lot of input reading problems because of the test data. Many of the files for problem 1 have an extra space on the first line, which throws off parsing the int in java. Also, many of the other test files have a blank line between each line of data. I don't think that I should lose marks because of that. Hopefully they will change the test data in a few days.

KL

[Clayton]

If you ask me, all the data and such was poorly handled this year....

[PaulButler]

I completed S1-S5, but I had to use a brute-force approach for S5. I would love to see the correct way, if anyone has a copy of their code (I don't know what the rules are around sharing this).

I found it quite easy, half way through I got worried that I might have been writing the junior instead of the senior.

That's too bad about the test data, mine was written in Java as well and things like this would definitely screw it up.

[zwnage]

Can anyone tell me how this is marked? Would they check for commenting, format, etc, or are they just looking at your run window? Is there a time factor like who hands it in fastest? I did the junior today, but I definitely should have asked stuff like that before the test >.<

[eklypze]

I took Senior. Haven't programmed for such a long time so I found it pretty difficult, or at least time consuming. I really should've prepared more... >.>

[JakeP]

I got S1 in about 10 minutes, S2 fairly quickly, S3 I took longer on, and ended up goofing it up (hopefully I get part marks), S4 I'm pretty sure I aced, and S5 didn't bother with (only had a half hour left)

Hoping for 45 at least.

Does anyone have the official test data?

[klopyrev]

Your code is not marked. The markers only look at the output. There shouldn't be a time factor for the Junior. As for the Senior, problem 4 and 5 have a 1 minute time limit. For Senior 5, I think it is a dynamic programming problem. A state is the starting location and the number of balls left. The answer would be the answer for the state starting at 0 with K balls left. To calculate each state, you can either place that ball at the starting location or not. Thus dp[i][k] = max(dp[i+1][k],dp[i+W][k-1] + sum(i, i+W)). You should output dp[0][k] for the answer. Taking care of edge cases like k = 0 or i+W > N will make the solution work. I think that solution should work in time and get all the test cases correct. Too bad I didn't implement that exactly on the contest. I did a little less efficient way

KL

PS: If anyone has a better solution or if anyone thinks my solution is wrong, feel free to reply to this post.

[Naveg]

If you used Java, you should have used the Scanner class for input. It completely removes the hassle of parsing ints and such. Just use Scanner.nextInt() and it reads the next int in the file, regardless of how much whitespace is in between.

[JakeP]

Luckily I used C++ with the STL functions, they automatically strip spaces and newlines

[stde]

did u guys use linked list for s3?

[klopyrev]

If anyone wants a working solution for S5, feel free to contact me.

Konstantin Lopyrev

Edit: Included is a JAVA solution. Sorry, there is no explanation for the solution.

[bugzpodder]

this is all really great, but there are people writing as we speak. I know of at least one school who won't finish till 6:30pm. I urge people to stop showing off until end of the day.

[bugzpodder]

and putting a complete solution for download is just totally inconsiderate