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

How is the championship

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

• Correctness: the program should always output the correct answer;
• Reliability: the program should not “crash”;
• Time efficiency: 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 very limited;

And now we add that the input data can contain millions or 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 point from the above, an attempt to pass the task does not will be counted, and the penalty time will be added to the team. Needless to say, the test data is not known to the participants?

An example of an olympiad problem

Consider a simple example: suppose you need to write a program that takes an array of numbers as an input and then executes queries like getmaxto get the largest number, or modify a bto replace a with b ? But what if the size of the array is a million, and you need to complete one hundred thousand queries? But what if numbers can be deleted? But what if you want to output the kth largest number? But what if the numbers are replaced by strings? And at the same time - there is only a second for everything and some kind of pathetic couple of megabytes of memory. Everything doesn’t seem so trivial anymore, does it? And this example is the simplest one, the Olympiad will take such a task in just a few minutes.

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 this interests readers, I will be quite glad to continue publishing in this direction, namely: first, “how to become an Olympiad”, “what habits should be abandoned,” then I can replenish the blog “algorithms” and consider some particularly interesting and remarkable olympiad problems .

PS I'm a newbie here, so I don’t understand: where is it better to post such posts? Torn between Algorithms , Abnormal Programming and the Learning Process . What do you think? - thanks khayrov
P.PSOf course, I can’t transfer it to the corresponding blog due to the lack of karma. By the way, I did not find anything in the help about restrictions for beginners on the publication in collective blogs. Did I look badly, or are they really gone? - thanks Mithgol
P.PPS Copyright photo: David Hill , taken from the ACM ICPC photo archive .

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