Teen Mathletes Do Battle at Algorithm Olympics(wired.com)
wired.com
Teen Mathletes Do Battle at Algorithm Olympics
http://www.wired.com/magazine/2010/11/mf_algorithmolympics/
34 comments
That quip was about Korotkevich not Neal. And besides, it was Kolstad who said it.
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.
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.
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
http://en.wikipedia.org/wiki/Beautiful_Young_Minds
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.
But I'd be surprised if they didn't have some serious Vim-Fu going on as well.
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++)...
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?
Because it allows them to type as fast as they can, or because it forces them to do so?
Too much to type in C++ as compared to language like Python
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.
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 ?
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.
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.
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:
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)
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&...
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.
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.
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/
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/
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.
If I want to play Rachmaninov's second piano concerto, I don't start by trying to play it straight away. I start with simple pieces, with scales and arpeggios, and with speed exercises. I build my basics, initially leaving out things that I'm not ready for.
I think learning Python first, and then the concepts behind both OOP and FP, better prepare someone for solving problems in languages like C++ than trying to start with C++ first.
As I said, personal opinion.
ADDED IN EDIT:
Fascinating. Rather than refuting the point I'm trying to make, someone has simply down-voted it without comment. That's a shame, as it doesn't provide me the opportunity to learn. Perhaps I simply haven't been clear, or perhaps they simply disagree without caring to articulate their point.
To try to be more specific, I think that learning Python, then learning Python in an OO style, then learning C++, makes a better programmer faster than trying to learn C++ directly. I have no evidence, only anecdotes, and they're not worth much. I think it's like trying to make a 6 inch reflector telescope. It's faster to make a 4 inch, then a 6 inch, than it is to try to make a 6 inch first. Again, there have been no controlled, double-blind experiments, but it is the conventional wisdom.
So there it is. If you think that expressing such a thought is detracting from the value of HN then feel free to downvote this comment further. If you disagree, but think it's an interesting point that deserves to be refuted, I'd love to hear your reasons.
I think learning Python first, and then the concepts behind both OOP and FP, better prepare someone for solving problems in languages like C++ than trying to start with C++ first.
As I said, personal opinion.
ADDED IN EDIT:
Fascinating. Rather than refuting the point I'm trying to make, someone has simply down-voted it without comment. That's a shame, as it doesn't provide me the opportunity to learn. Perhaps I simply haven't been clear, or perhaps they simply disagree without caring to articulate their point.
To try to be more specific, I think that learning Python, then learning Python in an OO style, then learning C++, makes a better programmer faster than trying to learn C++ directly. I have no evidence, only anecdotes, and they're not worth much. I think it's like trying to make a 6 inch reflector telescope. It's faster to make a 4 inch, then a 6 inch, than it is to try to make a 6 inch first. Again, there have been no controlled, double-blind experiments, but it is the conventional wisdom.
So there it is. If you think that expressing such a thought is detracting from the value of HN then feel free to downvote this comment further. If you disagree, but think it's an interesting point that deserves to be refuted, I'd love to hear your reasons.
Algorithm competitions aren't like playing Rachmaninov's second piano concerto.
It's more like playing a simpler piece that everyone knows, like Canon in D. Except you learn to play it faster than anybody else.
You're giving advice on how to be a better programmer, which is significantly different from being a programmer who implements algorithms. In a programming competition, I don't go back and optimize my code. I test to see if it works, and go on to the next question.
It's more like playing a simpler piece that everyone knows, like Canon in D. Except you learn to play it faster than anybody else.
You're giving advice on how to be a better programmer, which is significantly different from being a programmer who implements algorithms. In a programming competition, I don't go back and optimize my code. I test to see if it works, and go on to the next question.
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.
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.
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.
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)
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)
I would just like to say thanks! Without the Algorithmist, I would have pulled my hair out more than once.
Thank the contributors, I only maintain the site! ;) Of course you can thank the site by paying it forward!
That said, UVa's problems are better defined nowadays. Tough problems are actually tough, instead of trying to trick people!
That said, UVa's problems are better defined nowadays. Tough problems are actually tough, instead of trying to trick people!
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.
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.
Actually, there is at least one book: http://www.amazon.co.uk/Programming-Challenges-Contest-Train...
You should try doing USACO - http://ace.delos.com/usacogate
They have guides, problems and online judging system.
They have guides, problems and online judging system.
Note that this is more accurately a computer science competition, not a mathematics competition. The use of "mathletes" in the Wired title was inappropriate.
Not sure how challenging this is compared to those other, but http://projecteuler.net/ has 300+ problems with varying difficulty.
In case anyone's interested, there's a syllabus: http://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf
"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.
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.
[deleted]
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.