Ccc 2015

[Butane]

What is your opinion on this year's CCC? I did the senior division and overall found it to be a good contest. My only issue was S3 being so sketchy. The N=100,000 really threw me off as I thought the naive O(N^2) would not work, but apparently it did(atleast in C++). S5 was really cool. I don't know who would think of sorting and have a 3D array! S4 was very similar to the past CCC stage 2 question Vampire Tunnels so that was an interesting choice by them. How did you guys do?

[awaykened]

By the way you are speaking, I think you are a scrub.

Also, yes - P3 was definitely on the sketch side of the problems.

Also also, why did this thread start 3 months after the contest ended?

Also also also, I think this year's CCC was on the slightly easy side (at least for senior). Taking a look at the junior problems, I definitely would've gotten 0/75 after giving up on the first question.

However, luckily I wrote the senior, and did semi-decent (66/75)

[jr5000pwp]

Problem 4 was actually harder than Problem 5 this year imo. I feel like it's harder to deal with zero weight cycles in a graph than it is to develop a simple Dynamic Programming solution. That being said, if you ignored zero weight cycles you could still get 9/15 points on the problem.

[awaykened]

I believe S4 could be done using 2D shortest path, which is what myself and many people I know who got 15/15 on this problem used. Perhaps it's just me, but I find implementing shortest path a lot easier than coming up with DP solutions. Can you elaborate on the zero weight cycles? I don't quite understand what you mean.

[jr5000pwp]

I find DP easy, I prefer to remember concepts, and not algorithms. I find it better to invent an algorithm when you need it than to just paste in some code. It really helps with understanding. You could probably use Bellman Ford or something. I chose to do it with Dynamic Programming as I prefer it, but I didn't realize there were zero weight cycles in the graph. This caused a typical dynamic programming solution to infinitely recurse. It can still be solvable using Dynamic Programming, you just need to be a bit smarter about it.

By zero weight cycle, I mean that there is a path you can take in 6 of the test cases in which you can traverse in a loop without losing any of your hull integrity.