3 ms·
It's a programming competition similar to TopCoder or ACM ICPC. You're given 4 problems, each with a small (small n) and large (big/huge n) input set, and a tim
by pmlamotte 12y ago
It's a programming competition similar to TopCoder or ACM ICPC. You're given 4 problems, each with a small (small n) and large (big/huge n) input set, and a time limit to write programs to solve as many as possible. You're ranked by the combined score of the ones you've solved, and ranked within that score by how fast you solved each one.
For difficult problems you can often write a brute force solution with terrible complexity (think 2^n) for the small input set. For the large though, you'll need to really understand the problem and write an efficient solution via memoization, dynamic programming, pruning, or good (sometimes obscure) algorithm choices. For small solutions you get instant checking of your solution on submit (but not what you failed on, only that you did), for large ones you submit and hope for the best.
As for why you should care, for me at least it's fun to come up with fast solutions to problems regardless of whether they're efficient or if my code is well designed. You learn about new types of algorithms and ways of solving problems. For example, dynamic programming was foreign to me until I started doing tons of TopCoder. Google also uses it for recruiting, I'm still getting contacted by them even though I skipped last year.
My favorite moments come from solving problems poorly while knowing there's a proper solution out there. Ex: There was a problem in some competition where it was some special way you had to return the y-intercept of a line with a given slope that bisected a particular polygon. There was an actual way to do it properly, but I'm not so great at math/geometry so I ended up doing a binary search and did enough iterations to get the right amount of floating point precision they wanted.
- nanoGeek 12y agoHow much harder is compared to ACM ICPC?
- pmlamotte 12y agoNot too much, the difficulty comes more from fewer problem choices. ICPC at the regional level has many questions to select from and usually has at least 2 problems that can be solved in under 5-10 minutes (we had a badass on our team with under 1 minute submissions). I rarely anticipate solving the most difficult GCJ problem, even the small input case. In the beginning rounds the first 2-3 GCJ problems are usually on par with easy-medium difficulty ICPC problems. As you get higher up in the rounds they get more challenging. Edit: Should also point out that since you're not in a controlled environment, you have full internet and library access unlike ICPC where you have to rely on memorization and standard libraries.