Most Intellectual Competition: World Programming Championship

Livejournal blogger Sergei Mukhamedov writes: The other day, a Nedosmi correspondent was at a very significant and almost secret international event. You will not find his photographs on the Internet, except for the presentation of the cup or, at best, general plans, although it has been going on since 1977. Do not even try to guess what it is without looking under the cut - the year of the first championship will surely confuse you.

(Total 37 photos)

Source: Journal/ottenki-serogo

1. Sports arena. One hundred and twenty teams. Spectators. Two TV cameras online broadcast. And... absolute silence for five hours.

2. No action, just incredible thought work.

3. It's hard to imagine how these competitions were held 37 years ago. Felix arithmometer, slide rule and a pencil with a piece of paper? Computers at that time were the size of a house or a room.

4. This is the final of the ACM ICPC International Team World Programming Championship. For the first time in history, it was held in Russia.

5. This is the coolest team programming competition in the world.

6. 35 thousand participants from 2322 universities in 91 countries competed to get into this room and solve 11 complex algorithmic problems

7. These are the best young brains in the world.

8. Despite the fact that they are still studying at universities, everyone who has reached the final has already been employed

9. They started following them from the sixth grade, when they won their first programming olympiad.

10. They are already guaranteed salaries of $120,000 a year and shares in companies.

11. And it is not at all necessary that these companies will be foreign

12. In our country they will be paid no less than in the West. And the motivation of such people is completely different.

13. They already belong to the whole world. There are very few companies that can constantly load programmers of this level with tasks.

14. They are very complex people. The company's stock could collapse by millions of dollars if its main developers leave. It is difficult for them to create conditions for work and it is almost impossible to assemble a team in which they could work.

15. Companies that you use daily are waiting for them - these are Google, Facebook, Yandex ... And of course, complex and interesting startups. They consider work in banks "below the plinth".

16. But the very concept of the championship does not involve hunting for employees. The same Yandex, acting as an official partner of ACM ICPC, did not even have any advertising banner in the hall. The company knows all the Russian, Ukrainian and Belarusian children personally, thanks to its academic programs for which it spent a billion (!) Rubles over six years.

17. The main goal is different - to support an environment in which talented guys can grow and develop.

18.

19.

20.

21.

22. Balls are awarded for solved problems, as well as for other merits such as "The first team to complete task F"

23. In 5 hours, these guys in black T-shirts will be the winners. Prior to this, in different compositions, the Pererburg team of the National Research University of Information Technologies, Mechanics and Optics (NRU ITMO) became world champions four times.

24. The second place was taken by the team of Shanghai Technical University, the third - the University of Tokyo

25. For example, the translation of one task of this year. The original was of course in English:

The recent recession has hit entertainment venues hard, including gambling. There is fierce competition among the casinos, and in order to attract players, some of them began to hold especially attractive promotions.

The casino promotion includes the following: you can play as much as you want. And after you finish, no matter how much you have lost since you started, the casino returns x% of your losses. Naturally, if you win, you take it all.

At the same time, there are no restrictions on the duration of the game, nor on the amount of money with which you enter the game, but you can use this promotion only once.

For simplicity, let's assume that all bets are worth $1 and the winnings are $2. Now let's say that x is 20. If you make only 10 bets before you end the game and only 3 of them win, then your total loss is $3.2. If 6 bets win, then your winnings will be $2.

Given x and p (the probability of winning a single bet in percent), you need to write a program to determine the maximum expected payoff you can get using any game strategy.

The input consists of a single test that contains a return percentage x (0 ≤ x < 100) and a percentage win probability p (0 ≤ p <= 50). x and p have at most two decimal places.

Output the maximum expected payoff with an absolute error of no more than 10 -3

26. For those who know the basics of probability theory and know how to program, the task may seem simple, but it is not - when the parameters approach the acceptable limits, serious problems arise ...

27. This is how Aleksey Dergunov from the Samara State Aerospace University team, which took 35th place, described the championship:

At the beginning of the contest, we were very confused. craus and I thought about problem F for a very long time - we handed it in at the end of the first hour, weeding out a few wrong solutions along the way and writing one for which we could not come up with a counterexample. Then we solved Problem D. Not understanding how to do it, Hohol printed out the answers to the first few tests, but didn't extract anything. Then I remembered the task from the thymus and wrote exactly the same enumeration - it turned out that there were about 50 thousand candidates for the answer (of course, a decent ACM specialist should know that there are few of them, but we are not like that), so the precalc works. Then the solutions to problems A and H arrived, which had to be debugged a little, since we never learned how to write the first time. Then we solved problem C: the submission at 3:5x was already correct, but TL-ny: the team of three yellow participants cannot write maxflow and therefore copy-pastes it from the Team Reference, where there is only the Dinits algorithm, and even with a bunch of ArrayList- ov. Replacing all ArrayList-s with arrays, we immediately got Accepted. With a little over half an hour left, we decided that we couldn’t solve J in that time (I must say, a very nasty task, one of those that I especially hate - a bunch of stupid, meaningless implementation), and so we tried to solve B, but, as it turned out, it was necessary to solve a specific system of equations in O(1), as they once taught in the third year (actually a pleasant surprise - the knowledge gained and successfully forgotten at the university turned out to be necessary in ACM ICPC!)

28.

29.

thirty.

31.

32.

33.

34.

35.

36.

37. The day after the final, Russian Defense Minister Sergei Shoigu instructed to find (!) St. Petersburg students who had become world champions in programming five times in order to staff the scientific companies being created in the Russian army. Mikhail Kever, Niyaz Nigmatullin and Gennady Korotkevich, finish your studies and stay away from the minister. You deserve more than stuffing school essays to the son of the head of the unit.