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?
Cannot agree more. I was often asked "what is your hobby?". I said Competitive Programming and then they looked like "What the hell is that?". I started explaining for a while and they looked at me like monkey in the zoo, like I was talking in a different language. I am also looking for an good explanation which is good enough to use in an interview where they will definitely ask me about my hobby.
I think Google search engine is a good example. Sometimes I say: "Heve you ever wondered how is it possible that Google finds answers really fast among billions of sites? It is done using advanced algorithms, which I'm also interested in and I learn them by solving special tasks." Something like that :)
This analogy has never occurred to me, but it's quite clever. Also, it explains "time complexities" in a very understandable way. Nice!
If a person is neither a programmer nor someone in a related field, why exactly do you need to talk to them about competitive programming in such detail as to explain solutions with different complexity?
I once tried to teach programming is to a friend of mine who was into arts; I think we got stuck at "You can tell the computer what to do and it will do it? Wow!" Granted, I was around 12 then, but I'm not sure whether I would do a better job of it today :-)
When non-programmer people ask me specifically "What is this TopCoder thing written on your T-shirt?" (usually happens at an airport or other public places where you want to keep smalltalk really small), I stick to "programming competitions, you know, when people solve small problems fast".
I guess you're right — this question mostly stems from me obsessing about explaining it as precisely as possible. I usually only go into such detail with people with a math/CS background to explain that CP is mostly thinking, not coding. But I suppose it doesn't tell much to people who haven't experienced it. Thanks!
Your explanation from when you were 12 reminds me of this :)
Wooo, random people at street ask you about your CP t-shirts? Has never happened to me :(
Dude she is a girl, what else can you expect?
No random people in the streets for me either :-) More like security officers at an airport, clerks at various offices etc — places in USA where people purposefully try to have a conversation with customers while their computers process something.
The only time I've seen a reasonably random person (i.e. somebody who didn't have to stop by and talk but chose to) ask somebody about their CP T-shirt, the T-shirt in question was from onsite finals ;-)
Instead of knapsack, try Binary search.
Click
Don't forget to read comments ;)
The O(1) pen-finding algorithm cracked me up :D
IOI 2013 — Art Class
At least they understand what are we doing, I always use this as example :(
I would rather use it if someone asks me "what is machine learning?" not "what is competitive programming?" ;P
I think one of best examples is "shortest path from city A to city B". Classical algorithmic problem that is as real life as it gets. I sometimes refer to CP as logic puzzles or just intelectual challenges and I am ensuring nobody thinks I do some clickable webapps during contests :p.
I usually don't go into explaining complexities, but if you would like to I would go with some very simple problem like "you have a set of 10^8 numbers and find a pair with largest difference". Explain n^2 bruteforce, but don't say it performs n^2 operations, but sth rather "naive solution needs 10^16 operations, which will take years to compute!, but if we will use one simple trick (explain it) then we can create solution which uses 10^8 operations which runs in less than a second!"
I like comparing CP to art, and it quite often results good. "Programming is like art. You have some tools, which, like pencils or crayons, are nothing by themselves. We can use our creativity and computing skills to create outstanding artworks from scratch" Quite pathetic, but helps "normal" people to understand. They don't need to know what complexities are — this won't enlighten them probably.
To non-programer, I would say it is an intelligence computer game.
If you want to talk about programming to non CS guys , you won't have them long so say whatever you want.
To CS guys you can tell them I like to play with algorithms(We always have such statements in Problems so no problem).
Google CEO Eric Schmidt already made similar attempt by asking president Obama:
What is the most efficient way to sort a million 32-bit integers?
I think Schmidt made thoughtful decision to choose this question for Obama as short and clear.
More precisely, this question was not addressed to Obama but rather to general audience in order to promote computer science.
I think this question could give some impression (although is not 100% accurate) about what competitive programming is.
So here is how I would explain competitive programming to the general public:
Competitive programming is basically algorithm competitions/olympiads where participants should solve specific puzzles in efficient way using some programming language. To some extent problems could be similar to this:
What is the most efficient way to sort a million positive integers not larger than 4 billion?
Competitive programming is a mind sport like Chess. Also these skills are useful for such companies as Google. Just think about how Google search return results among billions of web pages within one second.
That's why Google hosts and sponsors algorithm competitions.