Teen Mathletes Do Battle at Algorithm Olympics

http://www.wired.com/magazine/2010/11/mf_algorithmolympics/

by kingsidharth • 16 years ago

55 32 16 years ago

Single page: http://www.wired.com/magazine/2010/11/mf_algorithmolympics/a...

How to become matheletes like them ? Any guides ? Books? Where to get started ? You suggest to learn python by it clearly says C,C++ and Pascal. Should I learn C++ as first language ? Help ?

RiderOfGiraffes3• 16 years ago

Ask for opinions of 10 HNers and get 10! answers ...

Personal opinion only ...

Learn Python first. Work on problems from Project Euler. Learn to program Python in OO mode. Learn C. Learn C++. Learn to program Python in functional mode. Read about the algorithms mentioned in the article. Understand P vs NP. Understand why this is funny: http://xkcd.com/287/

rednum2• 16 years ago

I have to disagree. I participated in few algorithm competition (however much easier than IOI) and I think that: - OOP - C - functional python are redundant. Creating more advanced objects than graph vertex/edge is usually unnecessary in algorithm tasks. Functional programming - well, that would be useful sometimes, but as IOI and most similiar type competirions support C/C++/Pascal, you won't be able to use it anyway. Problems from project euler seems to be a good start, however. Learning mentioned in article algorithms too.

lini• 16 years ago

Like any sport, you should have a good coach - informatics is no different. I used to participate in such competitions in high school and I can tell you that reading books is not enough. There has to be someone to teach you the basics so you can build on that. I started very early with Logo, moved to Pascal and finally graduated to C++. In the end, most of the problems can be solved with a standard algorithm - e.g. graph theory (DFS, flow, etc), dynamic programming (Knapsack), geometry (finding intersections or area of polygons). Some problems require heuristic solutions, but that is very rare. You need a lot of experience and that is gained by solving problems. You can find a lot of online judges that have problem sets from very easy to difficult - e.g. http://acm.zju.edu.cn/onlinejudge/showProblemsets.do or http://uva.onlinejudge.org/index.php?option=com_onlinejudge&...

xentronium• 16 years ago

Language isn't important. You start by solving some problems in whatever language you know.

http://acm.timus.ru/Default.aspx?locale=en -- not a bad place to start

Good books include monographies about algorithms. In Russia, the most popular books on the subject are:

    * Introduction to Algorithms (Cormen)
    * Algorithms and Data Structures (Wirth)
    * Algorithms [in C++] (Sedgewick)

Don Knuth also has remarkable works but they're somewhat more into proofs and math.

eru• 16 years ago

I went to a school that was very supportive and often send multiple people to those and similar competitions. (I was quite active in the mathematics olympiades, and helped out with organizing them after I finished school.)

That approach is probably not suitable for you. Like lini said, having a mentor or coach or just a mate is a good idea. You can ask on HN or on irc, I guess you will find people to help you.

rednum2• 16 years ago

Well, python is nice, but must algorithm competition (for reasons i dont really know) allow only C/C++/Pascal. Learning C++ seems to be the best choice here (though I don't like it), as usually you are allowed to use standard template library which comes with a few useful structs/algorithms.

I have taken part in similar competition (but not world class, though), and my advice is:

- learn c++ so you can express basic algorithms - creating an algorithm which solves task and not having enough time/skills to code it is extremely frustrating. However don't spend too much time learning the language - you probably won't need to write your own templates or do some advanced OOP stuff. learning python is ok too (personally I like python much more than C++) - it is really easy and cool, but you won't be allowed to use it anyway

- learn some maths, you will need it. You wont need arithetics or calculus - rather combinatorics or some number theory. Try to choose 'tricky' tasks rather than that requiring much computation - in IOI you are the one who thinks about tricks, and computer does the computation ;)

- read about algorithms mentioned in texts. learn about: dynamic programming (knapsack problem), greedy algorithms, trees and graphs (dfs, bfs, dijskstra, maximum flow, minimal spanning tree (kruskal-prim)), data structures (start with lists and binary search trees, then move to queues more advanced like interval trees - there are lots of interesting, both trivial and complicated structures), text algorithms (KMP, Manacher algorithm), computational geometry (sweep line algorithm, convex hull). - also, learning some tools - like good editor and debugger (vim and gdb) and some basic linux command line knowledge (e.g. when you test your programs it's better to redirect input from file than to write it each time manually) is really handy - it will make coding/debuggins much easier

It seems that there is quite a lot to learn - if you are a newbie to algorihtms, at the beginning I recommend learning what is algorihtm complexity - sorting algorithms are good place to start here. Then spend a while with basic data structs (writing your own linked list is an obligatory exercise here), then move to something different. Dont try to learn everything at once, rather focus on single subject at given momment. Personally I learned algorithms from 'Introduction to algorithms' by Cormen/Rivest/Leierson/Stein - I did only a few chapters on graphs/geometry/data structs but it was hard, I didn't understand most of the math - however many people I knew who were good at algorithms gained some kind of intuition whether something works or not or what complexity it has(obviously, you dont have time to write a proof of your algorithm during competition - also, it isn't necessary) and didn't use it too much - anyway it's good to grasp basics (so you can e.g. estimate complexity bounds to your solution). Also don't start algorithms by trying to copypaste them from your book to editor - try to understand them first (pen and paper are your friends here). However it is good to code at least once each of well known algorihtms as an exercise.

I mentioned cormen earlier - however this book is tough. Some of the algorithm tutorials on topcoder site (http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&...) may be useful for you - topcoder seems also as a good place to start coding (however, imho many tasks in div2 are rather brute-force, requiring much time coding than a good idea). Participating in your national OI may is a good idea too - usually you can find some useful resources on its site.

Locke1689• 16 years ago

Note that this is more accurately a computer science competition, not a mathematics competition. The use of "mathletes" in the Wired title was inappropriate.

sandaru1• 16 years ago

You should try doing USACO - http://ace.delos.com/usacogate

They have guides, problems and online judging system.

kmak2• 16 years ago

http://train.usaco.org/usacogate

It walks you through the algorithms, though you need one of the languages.

There's some terse list at

http://www.algorithmist.com/

that might help. (Disclosure: I started Algorithmist)

ianbishop4• 16 years ago

I would just like to say thanks! Without the Algorithmist, I would have pulled my hair out more than once.

xyzzyz• 16 years ago

Solve problems. After that, solve more problems. Having done that, read some algorithms book and solve even more problems.

The thing is that most problems on such contests are designed so that classical algorithms are of no use in solving them -- the jury want you to figure out the answer, not to know it beforehand. Of course, there are some algorithms that are helpful anyway, but not many -- here is an almost complete list: merge sort, quicksort, radix sort, Dijkstra, DFS/BFS, Find-Union, KMP, sometimes Manacher and various maximum flow algorithms. Regarding data structures, the following ones are useful: self-balancing binary search trees, interval trees, (mergeable) priority queues.

Learning more algorithms will not help you nearly as much as solving more problems.

CrLf• 16 years ago

Actually, there is at least one book: http://www.amazon.co.uk/Programming-Challenges-Contest-Train...

ianbishop4• 16 years ago

North American competitions usually allow C/C++/Java and sometimes Pascal.

Good books on these are:

* Programming Challenges by Skiena and Revilla

* Algorithm Design Manual by Skiena

* Introduction to Algorithms by Cormen

The biggest trouble of these competitions is being able to recognize what you're trying to solve. If you can say 'THIS IS DYNAMIC PROGRAMMING', you'll be a lot closer than someone who writes a backtracking solution and times out. From there, knowing what kind of problem (or combination of them) within the domain will help you design the proper algorithm.

Number theory, graph theory, geometry and combinatorics based problems appear often. There is sometimes some necessary knowledge required to be able to solve problems altogether. For example, if the problem makes reference to Catalan numbers and you don't know what they are - you won't be getting very far.

The UVa website (http://uva.onlinejudge.org/) offers a pretty horrible experience but an unforgiving judge which will help you practice a lot. It also has a judge for every book in the above text, Programming Challenges. There are also judges for live contests which you can participate in.

The Algorithmist (www.algorithmist.com) gives you some good test data and hints along the way if you get stuck on any of the UVa problems.

Project Euler is fun but it is slightly more algebraic and you do not (often) run into these kind of problems in these sort of competitions. It's still a good idea to try them out though.

redraga• 16 years ago

I highly recommend solving problems on spoj.pl (http://www.spoj.pl/). It has a HUGE collection of problems from various competitions, supports a plethora of languages for coding and the forums are an excellent resource.

albemuth• 16 years ago

Not sure how challenging this is compared to those other, but http://projecteuler.net/ has 300+ problems with varying difficulty.

apl2• 16 years ago

It'd be interesting to observe their workflow, from editor choice to debugging methodology. Sure, choosing and developing a sensible algorithm is the "meaty" part. I, for one, am fairly impressed by the stuff these kids do.

But I'd be surprised if they didn't have some serious Vim-Fu going on as well.

chunkbot• 16 years ago

There's very little usage of either Emacs or vim at these competitions (they seem to prefer a simple text editor). Also, they code fast, literally at the limit of how fast they can type! Maybe it's a consequence of the language choice (typically C++)...

apl2• 16 years ago

Maybe it's a consequence of the language choice (typically C++)...

Because it allows them to type as fast as they can, or because it forces them to do so?

ianbishop4• 16 years ago

Your text editor options are usually vim, emacs and pine (or nano) depending on where you are competing. No one uses IDEs, even if they are prohibited.

Benjo• 16 years ago

If you can find it, Beautiful Young Minds is a great documentary about the British team for the International Math Olympiad.

http://en.wikipedia.org/wiki/Beautiful_Young_Minds

ovi256• 16 years ago

One neat thing: at Harvard, Neal takes Math 55, a course so famous it has its own Wikipedia page.

http://en.wikipedia.org/wiki/Math_55

" ... covers four years of math in two semesters."

Otherwise, that "will he die a virgin ?" quip was really uncalled for.

protomyth• 16 years ago

That quip is pretty much why I don't subscribe to wired anymore. Showing contempt for the audience is not a good thing.

lookACamel• 16 years ago

That quip was about Korotkevich not Neal. And besides, it was Kolstad who said it.

zach• 16 years ago

Rob is quite a character, but there's no question he has a huge heart for this kind of stuff.

He was an organizer of Spaceset at JPL when I went there in the 90's. It was basically a space-colonization-themed mock Startup Weekend for high schoolers. And that's when he was plenty busy as the president of BSDI:

http://en.wikipedia.org/wiki/Berkeley_Software_Design

I'm pretty impressed to see him coaching this. The guy is indefatigable.

ianbishop4• 16 years ago

"For kicks, he took the tryout test for Harvard’s team. He came in first place."

I knew I recognized him from somewhere! ACM Regionals in New York took place a couple weeks ago. MIT managed to solve 7/8 problems, Harvard solved 3.

No one on our team has been doing competitive programming for nearly as long as some of these guys have. It took me only about a year of (very casual) practice to get to this point. So it doesn't necessarily mean you need to spend every waking moment on TopCoder.

borii• 16 years ago

In case anyone's interested, there's a syllabus: http://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf

Teen Mathletes Do Battle at Algorithm Olympics

Related Stories