As promised in the previous
post , I place the next one in which I will tell you how you can join a great many olympiads, and give initial tips.
UPD: The next
post in the series.
Where to go
ACM ICPC
Generally speaking, if the university is already in the background, or you study at something big ( like SPSU ITMO, SPSU, Saratov State University, Kiev State University, Ural State University, and so on - not true, I cannot judge other universities, knowing thanks to MikeMirzayanov ), but I have never been interested in olympiads before, then you almost certainly have no way for ACM ICPC. Why? The answer is obvious: if you are no longer a student, you obviously cannot participate in the inter-university competition. And if you study in a higher educational institution that showed itself well earlier, then you will get out of the slightest twinge of conscience. And if they don't kick it off, 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 only need to go to the appropriate department of your university and request an application for participation in the ACM ICPC. Detailed and detailed information about each of the stages of the Olympiad is available on the official website of the NEERC.Topcoder
And here anyone can participate: you can say no limits! In addition to the “free entry”, TopCoder is distinguished by its versatility: competitions are held in many areas, and quite often you can get good cash prizes without even taking the first place. A full list of directions is available on the information page .Other Arts
In 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 at all, depending on what you like.
How to learn
It is foolish to hope that you suddenly, as if by the wave of a UFO, will occupy the first places.
The key to success lies in constant training ; they should be devoted about twenty to thirty hours a week, or even more. First of all, you need to attend to the relevant literature:
Kormen should become your almanac, and with it the
Whip . From online resources I can advertise
Algolist ,
e-maxx and
Computer Algorithm Tutor . The latter resource is particularly noteworthy in that it contains many visualizers for algorithms. But, please, be
careful with habraeffektom : the site turns on quite old Pentium-IV.
Of course, the
knowledge of theory theory will help a little bit , so you also need to practice. In this case, the remarkable creation of the Ural State University -
Thymus will prove to be a good helper. There you can choose a task from a very large base (about seven hundred pieces) and solve it. Evaluation is made according to ACM ICPC rules. Timus It is very popular, and not only among domestic programmers: in total, over forty thousand people from various countries participate in the rating. Also, there is a practice mode on TopCoder, which was mentioned earlier.
What to write
The choice of languages ​​in Olympiads is standard: C / C ++, Java, Pascal. In some competitions, 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? But why: in the contest one of the most important parameters is how quickly you write the solution. And now think: if you need to indirectly implement a tree, then what is better: bare Pascal or Java, which has a wonderful TreeSet? But another case: the memory limit is extremely small (by the way, here is
an example of such a task, I plan to sort it out pretty soon). Of course, it is easier to choose C / C ++ or Pascal.
')
So, it turns out that
you need to write on everything . Even more, you need to be well aware of 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 perform sorting. In order not to waste time, it is much more logical to use ready-made options; especially since you are unlikely to write more efficiently. However, this is not always the case: for example, in no case can you use
a.indexOf(b)
in Java, where
a
and
b
are strings. Why? Yes, because it works too long, for
O (nâ‹…m) . So, the second conclusion:
you need to know very well how effectively this or that little thing is implemented in this or that language.
Epilogue and promises
Here it is, the first farewell to the world of Olympiads. In the next post I plan to tell in more detail about the advantages and disadvantages of various languages, accompanying this with the analysis of several classical problems. By the way, some workers ask to tell about how ACM lives. If the rest of the workers approve, then I can do that.
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.