Google Code Jam 2015 | Hacker News Reader

Google Code Jam 2015

code.google.com

176 pointsAaronn41 comments

Competitive programming is like a competitive sport. You need to practice a lot to excel at it. The best ones have been training consistently for years.

It's a humbling experience for anyone who thinks he or she is a good programmer. I remember when I tried topcoder for the first time. I thought it would be easy to move through the ranks and it turned out to be much harder than expected.

However, it's an extremely specific type of programming that in my opinion don't reflect real life programming aptitudes.

I think I learned two important lessons though. Be confident your solution is correct before starting coding it, and don't debug but write correct programs instead. It's easier said than done, but a little discipline can help a lot.

In my experience, practicing for competitions like GCJ, Topcoder help a LOT in two ways.

1. Raw coding skills - You'll reach a point where what's in your mind can be coded with very few stupid low level coding bugs like syntax errors, mis-assignments, initialization errors and such. Obviously this doesn't help with higher level issues like program design etc..

2. Algorithmic skills - You'll get VERY good at analyzing algorithmic complexity. You'll thoroughly understand common data structures like lists, vectors, trees, hash maps and other common algorithms.

Both these things are very much relevant to real life programming.

I completely agree.

I eliminated all basic issues in my coding skills a few years ago by doing a lot of online challenges.

Drawing an analogy to writers, online challenges (or preparing for them) is like getting really good at sentence formation, vocabulary, paragraph formation, etc. This allows you to then focus on larger things like writing a paper and even comprehending other people's papers with much ease.

Code is the language of software engineering and computer science. Online competitions help internalize that so that it becomes second nature.

Yay! Cmon y'all.. I can't be the only one excited about this!? Where are all the fellow HN'ers who actively practice programming challenges and such? Woot!

New this year is Distributed Code Jam:

> The competition will challenge your distributed coding, latency reduction abilities, and of course, your algorithmic coding skills

https://code.google.com/codejam/distributed_index.html

Wasn't clear from the description or FAQ how the solutions will run. Are solutions suppose to run on top of App Engine or something?

Yes, the website don't say clearly. But you must pass the Code Jam Round 3, then you can attend the distributed code jam.

What exactly is this? The site does not do a good job in telling me. Is it a competition? Is it a hackathon? I do not understand why I should care about this.

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.

How much harder is compared to ACM ICPC?

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

I recommend to anyone who wants to familiarize with the mechanics of competitive coding, the preparation to participate, or the kind of problems you are supposed to tackle, to get a copy of Steven and Felix Halim's "Competitive Programming" [1].

Even though I'm an outsider myself to these competitions, I found the book fascinating. Someone posted an article here at HN about someone reading Greek Classics a hundred or so times and what he got from that... this is the kind of book I feel like I'll have to read that many times in order to get the most of it!

"[...] the book contains a collection of relevant data structures, algorithms, and programming tips written for University students who want to be more competitive in [...] competitions, those who love problem solving using computer programs, and those who go for interviews in big IT-companies [...] The possible long term effect is future Computer Science researchers who are well versed in problem solving skills."

P.S.: nobody asked me but, what the hell. The other algorithms book I'm really itching to recommend is Sedgewick and Wayne's [2] :-). I like it more than other commonly recommended books, like Skienna's "Algorithms Design Manual" and Cormen's "Introduction to Algorithms".

1: https://sites.google.com/site/stevenhalim/

2: http://algs4.cs.princeton.edu/home/

I'm always surprised at why people (especially those who end up winning these things) tend to use C for these challenges.

Is it just because they can still solve a challenge even if the solution is suboptimal in some cases? It can't possibly be that it's easier for them to think about problems that way...

Another interesting thing is that Python is only really popular in US.

Source: http://www.go-hero.net/jam/14

Nobody uses C. Most use C++. There are a few Java people. I made it to on-site semifinals in Clojure once. Reid Barton, who is at least 1000x smarter than me, made it to world finals in Haskell.

Modern C++ is about as easy to use as Python or Ruby for algorithmic problems and has many fewer gotchas and hidden time sucks. Python tends to spend a lot of time on implicit data type conversion that C++ saves and the data structures in Python are deeply suboptimal so that many algorithms won't run in their theoretical asymptotic time. Ruby is even worse. Python and Ruby's numerical efficiency and consistency is not suitable for fast, precise, predictable computation.

Take a look at some of the solutions on go-hero and you can see the style of C++ that is used; there aren't any ugly class hierarchies and deep template metaprogramming there. Modern C++ is very simple and efficient with C++ versions of all the nice tools and gadgets that make Python and Ruby fun.

"Another interesting thing is that Python is only really popular in US"

I think Python is popular only in the USA in real life, too. Living overseas you learn that the rest of the world is very, very far behind in programming tools compared to Boston and SF.

This year I plan to use Scala for the GCJ, but for numerical problems I won't hesitate to go back to Python: Numpy is just too convenient for that. In previous editions I've used Numpy (and once even a Scipy solver) and it made my life easier (and efficient, consistent, fast, precise and predictable, while we're at it).

As someone who did a bit a C++ at University and switched to Python, your comment makes me want to learn modern C++. Do you have any suggestion on where to start?

> ... makes me want to learn modern C++. Do you have any suggestion on where to start?

i have always found bjarne-stroustrup's books to be quite useful. his latest one (Programming: Principles and Practice Using C++) seems to cover c++11/c++14 as well. might be worth checking out ? another author i really like is andrew-koenig, you can probably look at, Accelerated C++, from him. it is a bit dated, but still pretty good overall.

I think another reason is that for the competition-kind code there is very little difference between languages, so the drawbacks of C++ just don't matter. For example, the lack of garbage collection is not a problem, as the program works in the "allocate-compute-free" workflow. And with C++ you have far more room before you would have to think about performance than with more high-level languages. That is, maybe counterintuitively for someone, programming on C++ may be easier when performance matters.

Do you have any links to Reid Barton's 2010 Google code jam code? I briefly looked and couldn't find it. I'm guessing someone more familiar with code jam would know right where it was or if it existed.

http://www.go-hero.net/jam/08/name/Reid

People use C++. The STL is very convenient as you get most datatypes from it with less syntactical overhead than in Java (esp. in C++ 11). In particular thanks to operator redefinitions and "auto" type inference.

Python is more concise but it can be too slow for certain tasks, and the lack of static typing can be counterproductive.

I will be there like every year, at least for the challenges happening during the weekend. Too bad you can't do it on your own terms. Like why can't you start the coding session when you want? I always forfeit not because I can't solve it but because it's at random times on weekdays.

There should be a round in Code Jam which asks people to write the slowest possible (and correct) solution for a problem. Would be interesting to see people coming up with algos that have ridiculously large complexity classes like O(n!), O(n!!) etc.,

How do you eliminate stuff that is slow just for the sake of being slow? For example, a find_in_list function that iterates through the list N! times to 'protect against cosmic rays' or something along those lines.

By requiring to terminate and return a result?

Of course. Just test to see if the program terminates or not.

While halting problem can't be solved, you can solve the problem by saying all programs must terminate within 20min and program must scale with input length.

And/Or you can forbid sleep and similar nop functions.

And/Or you can sit down and analyze the code.

Truth be told, it makes for a very boring competition, but a very useful exercise.

How will a code-checking engine get past infinite loops?

while(earth_has_not_blown_up) {}

"Hey, I need the earth to blow up to solve this problem!"

you'll never get the answer. when earth blows up, you lose electricity

Just before the electricity goes, an electromagnetic disturbance or a shockwave causes the CPU to skip a few instructions, printing out the answer.

  while True:
        continue

  return solve(x)

It reminds of an interview question. What is the slowest program (that still terminates) it is possible to write, and how would you do it?

    sleep(10000)
    return fizzbuzz(10)

This reminds me of the busy beaver problem.

Funny that it forces me to pick a Google office where I would like to work, to complete the registration. They need to get it that not everyone are interested in working for them.

Nonsense. The question before asks if you are interested in having Google contact you. If not, leave it blank.

I think Google Code Jam is a recruiting tool for Google...

It is. They contacted me last year.

Is this a school or commercial address?

Yes / No

Google master troll

if it is a school or a commercial address, the answer is Yes, otherwise No.

Residential == No.

Reply on news.ycombinator.com