Programming as a sport
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 championshipThere 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;
An example of an olympiad problemConsider 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 .
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.