Teen Mathletes Do Battle at Algorithm Olympics
wired.com
wired.com
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.
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.
But I'd be surprised if they didn't have some serious Vim-Fu going on as well.
Because it allows them to type as fast as they can, or because it forces them to do so?
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 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.
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.
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)
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.
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.
They have guides, problems and online judging system.
It walks you through the algorithms, though you need one of the languages.
There's some terse list at
that might help. (Disclosure: I started Algorithmist)
That said, UVa's problems are better defined nowadays. Tough problems are actually tough, instead of trying to trick people!
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.
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.
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.