The path of the Olympiad
As promised in a previous post , I will post the next one in which I will tell you how to join the great variety of Olympiads, and give initial tips.
UPD: The next post in the series.
Where to go
ACM ICPCGenerally speaking, if a university is already behind you, or you are studying in something big ( like St.
Petersburg StateUniversity ITMO, St. Petersburg State University, Saratov State University, Kiev State University, Ural State University, and so on- it’s not true, I can’t judge other universities, knowing about your - thanks MikeMirzayanov), but have never been interested in olympiads before, then you almost certainly have no way to ACM ICPC. Why? The answer is obvious: if you are no longer a student, then obviously you can’t participate in the interuniversity competition. But if you are studying at a university that showed itself well before, then you will be kicked out without the slightest twinge of conscience. And if they don’t do it, then as a beginner you still have no chance against the pros. But if you do not fall under any of these points, then the path is open; you just need to go to the appropriate department of your university and request an application for participation in ACM ICPC. Detailed and detailed information about each of the stages of the Olympiad is on the official NEERC website .
TopcoderAnd here anyone can participate: one can say, no restrictions! In addition to the "free entry" TopCoder is versatile: competitions are held in many areas, and quite often you can get good cash prizes without even taking first place. A complete list of destinations is available on the information page .
Other artsIn addition to the above, there are many other contests like Google Code Jam and UVa . By the way, no one bothers to participate in everything at once. Or not everything, depending on what you like.
How to learnIt is foolish to hope that you suddenly, as if by UFO, will take first places. The key to success lies in constant training ; they should devote about twenty to thirty hours a week, or even more. First of all, you need to take care of the relevant literature: Cormen should be your almanac , and with him Knut . From online resources I can advertise Algolist , e-maxx and Computer Algorithm Tutor . The last resource is especially noteworthy in that it contains many visualizers for algorithms. But please, be careful with the habraeffect: the site is spinning on a rather old Pentium-IV.
Of course, that the theory of cramming the case will help just a littleTherefore, you also need to practice. In this matter, a wonderful creation will be a wonderful creation of the Ural State University - Timus . There you can select a task from a very large database (about seven hundred pieces) and solve it. Assessment is carried out according to the rules of ACM ICPC. Timus is very popular, and not only among domestic programmers: in total, more than forty thousand people from various countries participate in the ranking. There is also a practice mode on TopCoder, which was mentioned earlier.
What to write onThe choice of languages in the olympiads is standard: C / C ++, Java, Pascal. In some olympiads, it is extended by Delphi, C #, and even some functional languages like Haskell or OCaml. It would seem: since the choice is wide, why can't I always write in my favorite language? And here's why: in the contest, one of the most important parameters is how quickly you write the solution. Now think: if you need to indirectly implement a tree, then which is better: bare Pascal or Java, which has a wonderful TreeSet? And here is another case: the memory limit is extremely small (by the way, here is an example of such a task, I plan to parse it pretty soon). Of course, it's easier to choose C / C ++ or Pascal.
So, it turns out that you need to write on everything. Even more than that, you need to know the standard libraries of all those languages with which you are going to work. Very often, when solving a problem, it is indirectly required to use various data structures or to sort. In order not to waste time in vain, it is much more logical to use ready-made options; all the more so since you’re unlikely to write more efficiently. However, this is not always true: say, in no case can be used
a.indexOf(b)in Java, where
bare strings. Why? Yes, because it works for an excessively long time, beyond O (n⋅m) . So, the second conclusion: you need to know very well how efficiently this or that little thing is implemented in a particular language.
Afterword and promisesHere it is, the first parting word to the world of Olympiads. In the next post, I plan to talk in more detail about the advantages and disadvantages of various languages, accompanying this with an analysis of several classic problems. By the way, some workers are asked to talk about how ACM-schiki lives. If the rest of the workers approve, then I can do this.
PS It would seem that the topic of how Olympiad programming is applicable or not applicable to conventional programming is about nine thousand years ago.