Year out of the year you can see in the headlines of news vivid phrases like “Russian programmers won again”; Yes, and our president does not bypass this issue side. Words are nice, of course, but what does all this mean?

How is the championship

There are many programming contests in the world, but ACM ICPC stands out among all of them. It is the Association for Computing Machinery International Collegiate Programming Contest - the International Intercollegiate Programming Contest , which is held by the notorious ACM . The structure of the contest is simple - No more than twelve teams from the university for the quarter-final, no more than four for the semi-final, and only one for the final. During one round of the competition, which, with the exception of technical details, lasts five hours, each team must write the largest number of programs that solve the tasks from among those proposed; and they are usually from eight to sixteen. From a technical point of view, the programs are the simplest: neither you are a GUI, nor are you working with databases, or other similar whistles: a simple console application — read something, process it, and output the result of the calculations.
However, everything seems so simple only at first glance: not only does the solution of the problem require serious mathematical knowledge and ingenuity, but also the evaluation criteria are extremely strict:

• Correctness: the program should always display the correct answer;
• Reliability: the program should not "fall";
• Time effectiveness: the total time of the program on all tests should not exceed the established limit; most often from a split second to several seconds;
• Memory efficiency: the amount of memory that the program uses for its work is severely limited;

And now we add that the input data can contain millions and even billions of values, and also that if at least one of the many (sometimes their number goes over a thousand) tests the program will not satisfy at least one of the points listed above, an attempt to pass the task does not will be scored, and the team will be added penalty time. Needless to say that the test data participants are not known?

An example of the Olympiad problem

Consider a simple example: let’s write a program that takes an array of numbers as input, and then execute queries like getmax to get the highest number, or modify ab to replace a with b ? But what if the size of the array is a million, and you need to complete one hundred thousand queries? And what if the numbers can be deleted? And what if you want to display the k -e size of a number? What if numbers are replaced by strings? And at the same time - everything is only a second and some kind of pathetic couple of megabytes of memory. Everything does not seem so trivial, is not it? And this example is the simplest one; such a task takes only a few minutes for an olympiad.

What do I have to do with this?

It is logical to assume that the skills of Olympiad programming will be useful to any specialist, because then he will begin to seriously monitor the effectiveness of his creations. If readers are interested in it, I will be quite happy to continue publishing in this direction, namely: to begin with “how to become an olympiad”, “what habits should be discarded”, then I can replenish the blog “algorithms” and consider some particularly interesting and remarkable olympiad tasks .
')
PS I'm new here, so I don’t understand: where is it better to post such posts? Torn between Algorithms , Abnormal Programming and Learning Process . What do you think? - thanks khayrov
PPS Of course, I can’t move it to the appropriate blog due to the lack of karma. By the way, in the help I did not find anything about the restrictions for beginners to publish in collective blogs. Was I looking bad, or are they really not? - thanks Mithgol
PPPS Copyright photos: David Hill , taken from the ACM ICPC photo archive .

UPD: transferred sports programming to the blog. Thanks for the karma and clarifications.
UPD2: Post # 2 with us.