3 ms·
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 (th
by rednum 16y 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&module=Static 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.