В этой статье я решил проанализировать результаты крупнейшего соревнования по спортивному программированию в мире — ACM ICPC. International Collegiate Programming Contest (ICPC) — командное соревнование между университетами. Команды из трех человек пытаются решить как можно больше задач. В соревновании побеждает та команда, которая решит больше задач за наименьшее время. Каждый год команды соревнуются в региональных соревнованиях. Лучшие команды субрегиональных соревнований проходят на региональный уровень, а лучшие команды региональных соревнований выходят в мировой финал.
Рейтинг
Я проанализировал результаты последних десяти лет, чтобы выяснить, какие университеты и страны являются лучшими. В этом рейтинге результаты более поздних лет имеют более высокий вес, чем результаты более ранних лет.
Региональный конкурс для Северо-Западной Европы
| Rank | University | Points |
|------|-----------------------------------------|--------|
| 1. | University of Cambridge | 96914 |
| 2. | Technical University of Munich | 69702 |
| 3. | University of Oxford | 63030 |
| 4. | Karlsruhe Institute of Technology (KIT) | 56824 |
| 5. | KTH - Royal Institute of Technology | 56270 |Поскольку я в настоящее время учусь в этом регионе, я решил представить его первым. В его состав входят университеты из Бельгии, Германии, Дании, Эстонии, Финляндии, Великобритании, Ирландии, Исландии, Нидерландов, Норвегии, Швеции и Люксембурга. В этом регионе Кембриджский университет ежегодно выпускает несколько отличных команд. Все команды, которые они посылают, имеют определенное качество, которое помогает их общему счету. Я приятно удивлен, что мой университет занял второе место, но я могу представить, почему. Отбор на регионы в ТУМ достаточно конкурентный, и команды формируются на основе многомесячных результатов индивидуальных конкурсов.
Центральноевропейский региональный конкурс
| Rank | University | Points |
|------|-----------------------------------|--------|
| 1. | University of Warsaw | 47274 |
| 2. | University of Wroclaw | 37388 |
| 3. | Jagiellonian University in Krakow | 35886 |
| 4. | University of Zagreb | 33526 |
| 5. | Charles University in Prague | 26066 |Центральноевропейский регион включает Австрию, Хорватию, Чешскую Республику, Венгрию, Польшу, Словакию и Словению. Здесь Варшавский университет является бесспорным королем. Также примечательно то, что Польша заняла первые три места. Лично я встречал людей из этих топ-3 университетов на Центральноевропейском региональном чемпионате, и я могу сказать вам, что эти люди рано начинают подготовку к ICPC. Большинство из этих людей — вундеркинды средней школы по математике/программированию. Когда они поступают в университет, они попадают в среду, в которой многие команды серьезно относятся к обучению ICPC.
Региональный конкурс Юго-Западной Европы
| Rank | University | Points |
|------|--------------------------------------|--------|
| 1. | Universitat Politècnica de Catalunya | 36808 |
| 2. | ETH Zürich | 31520 |
| 3. | Ecole Polytechnique | 28346 |
| 4. | École Normale Supérieure de Paris | 23772 |
| 5. | Scuola Normale Superiore | 21664 |Политехнический университет Каталонии каждый год отправляет несколько команд, которые занимают первые места в таблице лидеров. Их общее первое место в регионе впечатляет, поскольку они побеждают ETH, что, безусловно, привлекает очень талантливых студентов.
Мировой финал
Прежде чем раскрыть 10 лучших университетов в ACM ICPC в целом, я хотел показать вам, как национальности представлены в таблице лидеров 50 лучших.
В мире соревновательного программирования за последние 10 лет лидировали Китай и Россия. ЕС не сильно отстает. Во многом благодаря Польше. США также не сильно отстают благодаря университетам, которые привлекают международные таланты, таким как MIT.
| Rank | University | Points |
|------|------------------------------------------|--------|
| 1. | University of Warsaw | 80845 |
| 2. | Shanghai Jiao Tong University | 79284 |
| 3. | The University of Tokyo | 79267 |
| 4. | Moscow State University | 78613 |
| 5. | Peking University | 76460 |
| 6. | Tsinghua University | 75126 |
| 7. | Massachusetts Institute of Technology | 73415 |
| 8. | Moscow Institute of Physics & Technology | 68306 |
| 9. | National Taiwan University | 66248 |
| 10. | St. Petersburg State University | 66185 |А абсолютным победителем стал Варшавский университет! Этот университет каждый год отправляет команду, которая неизменно получает медаль в финале. В топ-10 мы видим еще большее доминирование китайских и российских университетов.
Господство Китая и России
После окончания холодной войны Китай и Россия доминируют в ACM ICPC. Я бы сказал, что это потому, что эти страны сохраняют большую часть своих талантов. Китай и Россия также доминировали на Международной школьной олимпиаде по информатике (IOI). Как только эти талантливые спортивные программисты поступят в университет, они окажутся в среде, где поощряется обучение ICPC.
Когда я тренировался в Петрозаводском лагере по программированию в России, мы тренировались весь день, так как больше было нечего делать. Это была идеальная среда для соревновательной практики программирования. Реальный вопрос заключается в том, как Россия и Китай последовательно выигрывают олимпиады старшеклассников? Я, к сожалению, не тот человек, чтобы ответить на этот вопрос.
Однако я считаю, что эти результаты слегка смещены в сторону стран с более высокой численностью населения. Если бы статистика учитывала численность населения, у нас могли бы быть такие страны, как Швейцария, Сингапур или Тайвань.
Почему США плохо работают?
Несмотря на то, что они претендуют на большинство ведущих университетов в университетских рейтингах (таких как qsuniversityrankings), вузы из США уступают вузам из Китая и России. Я считаю, что тому есть две причины.
Во-первых, рейтинги вузов не совсем точно отражают качество студентов и качество преподавания в этих вузах. Они сосредоточены на исследованиях и объектах. Они сосредоточены на количестве иностранных студентов, и, поскольку большая часть мира говорит по-английски, университеты из англоязычных стран имеют преимущество в привлечении иностранных студентов и преподавателей. Примером может служить Эдинбургский университет, который занимает более высокое место, чем большинство, если не все азиатские университеты. Тем не менее, я просто отказываюсь верить, что Эдинбургский университет, несмотря на то, что он является прекрасным учебным заведением, имеет лучших студентов, чем университет Цинхуа или Токийский университет. В связи с этим рейтинги дают американским учреждениям ложное ощущение превосходства.
Во-вторых, хорошие результаты на ICPC не являются приоритетом для университетов США. Это похоже на большую часть Европы. Гарвард, Массачусетский технологический институт или Стэнфорд определенно привлекают лучших. Однако конкурентная среда обучения программированию в этих учебных заведениях практически отсутствует по сравнению с российскими и китайскими аналогами. Польза от того, что большую часть дня вы тратите на решение сложных задач, невелика. С другой стороны, когда вы поступаете в Стэнфорд, вашей целью может быть стажировка, исследовательский опыт или стартап, а не лидерство в соревновательном программировании.
Методология
В этом разделе я объясню, как я подсчитывал баллы. Во-первых, мы учитываем последние 10 лет существования региона. Если быть точным, то с 2010 по 2019 год. Баллы рассчитываются по следующей форме:
где i = 1 соответствует 2010 году, а i = 10 соответствует 2019 году. Это приводит к тому, что более поздние годы имеют больший вес. значение p_points рассчитывается по следующей формуле:
где k_teams — количество команд, отправленных университетом в этом году на региональную, n_participants — общее количество команд-участниц, а p_i — место i-й команды от университета. Мы возводим в квадрат разницу между позициями и общим количеством участников, потому что мы хотим, чтобы команды, занявшие первые места, внесли больший вклад в общий результат. Затем сумма баллов, набранных каждой командой, делится на квадратный корень из числа команд, присланных университетом. Если бы мы не извлекали квадратный корень, это было бы простое среднее, а нам это не нужно. Потому что это будет означать преимущество для университетов, которые отправляют только свою лучшую команду. Кроме того, мы не хотели, чтобы университеты, отправившие наибольшее количество команд, также были в выигрыше. Это похоже на компромисс, который дает наибольшее количество баллов университетам, отправляющим несколько отличных команд.
Код доступен по адресу https://github.com/JahodaPaul/ACM-ICPC-analysis.
