How to explain competitive programming without making it sound boring?

Правка en1, от -Wave-, 2016-10-10 23:20:14

If you've ever been asked about your hobbies, you probably know this problem. How does one briefly explain what competitive programming is about to a person who has never even heard about it and, worse yet, is not a programmer nor mathematician?

I've struggled with this quite a bit and I still haven't found a satisfactory answer. With a bit of Googling, I found this entertaining response, which is accurate if you already know CP, but doesn't really tell you much if you don't. On the other side, there is an analogy I tend to use — that it's like a math contest but with a computer. However, I feel like when you mention the word math, people tend to roll their eyes and stop listening, and it's not entirely accurate either: having to code your solution is very different from writing it in a math contest. When my friends read a CP task I'm working on, they often don't even know what is being asked of them (that is, to write a program which solves the problem for any input).

My working explanation, which is far from perfect, goes something like this:

"It's a bit like the Mathematical Olympiad, but with programming. You are given some tasks which tell you that you have to write a program that performs a specific task. For example, imagine you have a backpack, which has some volume. Also, you have a list of items with various volumes. Your program, given the capacity and the list, has to tell you if you can put some of the items into the backpack so that it's completely full. So you read the task, then write a program which solves it, then you submit it to an automatic system which tests it, and if it really works, you get some points."

Obviously, this is the knapsack problem, which I selected because it's quite easy to state. The downside here is that it's hard to explain the solution to somebody who has never heard about recursion or DP. Also, it doesn't tell you about time complexities (basically, that your program has to be fast). This is why I sometimes use exponentiation as an example (given N, find 3^N), because it's fairly simple to explain both the O(N) and O(log N) solutions, but it's not that straightforward for people without a math background.

What I'm looking for here are other analogies and ways of explaining competitive programming, on either end of the accuracy/entertainment spectrum (but ideally, both accurate and entertaining). The shorter, the better. Also, do you know about some example tasks which are not trivial, but easy to explain and have solutions with different complexities?

Теги explain, competitive, programming, to, plebs


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский -Wave- 2016-10-10 23:20:14 2731 Initial revision (published)