Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированию::
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Наука и технологии
Подписка
Где купить
Авторам
Рекламодателям
Магазин
Архив номеров
Вакансии
Контакты
   

  Опросы

Какие курсы вы бы выбрали для себя?  

Очные
Онлайновые
Платные
Бесплатные
Я и так все знаю

 Читать далее...

1001 и 1 книга  
20.12.2019г.
Просмотров: 5478
Комментарии: 0
Dr.Web: всё под контролем

 Читать далее...

04.12.2019г.
Просмотров: 6657
Комментарии: 1
Особенности сертификаций по этичному хакингу

 Читать далее...

28.05.2019г.
Просмотров: 7941
Комментарии: 2
Анализ вредоносных программ

 Читать далее...

28.05.2019г.
Просмотров: 8232
Комментарии: 2
Микросервисы и контейнеры Docker

 Читать далее...

28.05.2019г.
Просмотров: 7224
Комментарии: 0
Django 2 в примерах

 Читать далее...

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

 Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированию

Архив номеров / 2020 / Выпуск №03 (208) / Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированию

Рубрика: Карьера/Образование /  Олимпиадное программирование

Как и почему МФТИ стал лидером Международной студенческой олимпиады по программированию

В области спортивного программирования, в основе которой лежит работа с алгоритмами, Россия показывает результаты значительно более высокие, чем все другие страны: c 2000 года российские команды завоевали 33 золотые медали, китайские – 13, команды стран Европы – 12, США – 7.
В Московском физико-техническом институте (МФТИ) с 2012 года открыт Центр развития ИТ-образования, который занимается организацией нескольких десятков образовательных проектов (олимпиады, тренировочные сборы, зимние и летние школы) для школьников, студентов и преподавателей

Одним из основных направлений деятельности Центра является подготовка студентов к ведущим международным соревнованиям по спортивному программированию. Для этих целей Центр основал международный проект Moscow Workshops. Его миссия – дать возможность студентам реализовать свой потенциал и улучшить свои позиции в турнирных таблицах соревнований по спортивному программированию, учиться и путешествовать.

Проект состоит из открытых онлайн-курсов, заочных чемпионатов, проектов для школьников и тренировочных кэмпов. В Moscow Workshops уже приняли участие 2950 студентов из 221 вуза 58 стран. Команды московского Физтеха, начиная с 2011 года, привезли пять медалей финала ICPC – Международной студенческой олимпиады по программированию (три золота, одно серебро, одна бронза). Сегодня Физтех – единственный вуз, имеющий непрерывную череду медалей.

Алексей Малеев:

«Главное – не бояться!»

Проректор по международным программам и цифровым инновациям МФТИ, основатель Moscow Workshops, руководитель подготовительных сборов на базе МФТИ национальной сборной России на международную олимпиаду школьников по информатике дает несколько советов тем, кто хочет заниматься олимпиадным программированием или участвовать в соревнованиях по спортивному программированию

 «Нужно попробовать себя. Главное – не бояться сделать первый шаг. Причем, это, наверное, самое сложное. Часто спрашивают: «А что это такое? А как заниматься, мы не знаем. Мы вот где-то попробовали и оказались на 1001 месте. Как быть? Значит, не наше?»

Нет, не надо опасаться изучать новое, делать ошибки. В жизни всегда все начинают с чего-то малого. Нет человека, который родился бы и сразу придумал теорию относительности. К Эйнштейну она тоже пришла не в первый месяц его жизни.

Первые шаги очень важно делать. Сейчас есть много онлайн-ресурсов. Например, Codeforces – крупнейший портал по спортивному программированию. На этом ресурсе еженедельно проводятся бесплатные онлайн-соревнования. Чтобы участвовать в них, наверное, необходимо обладать хотя бы начальным уровнем программирования.

Я в школе тоже занимался олимпиадами. По информатике я помню, что у нашего учителя был простой, но действенный подход. Он давал ученикам какую-то интересную задачу, и показывал, где в книжке можно прочесть базовые вещи. Основы информатики мы должны были ему сдать, но можно было задавать учителю вопросы, и он отвечал на них.

Сейчас есть много литературы, которая поможет в обучении. Поэтому, не бойтесь, пробуйте.»

Помимо этого, Центр создал и продолжает развивать лагерь для школьников по подготовке к Международной олимпиаде школьников по информатике Moscow Workshops Juniors, фестиваль по программированию MosCode, который в этом году расширится и станет всероссийским проектом RuCode, организует Moscow Programming Contest и регулярные тренировки на кампусе Физтеха.

В 2019 году Центр организовал следующие соревнования и сборы: MosCode Festival (Москва), Moscow International Workshop (Долгопрудный), Moscow Pre-Finals Workshop (Долгопрудный), Moscow Programming Contest (Москва и Московская область).

В квалификационном туре Moscow Programming Contest приняли участие рекордное число человек – 1275 студентов и 1009 школьников отборочного тура Московской командной олимпиады школьников по программированию, объединенной с Moscow Programming Contest. Общая цифра участников, 2284, была зафиксирована в Реестре рекордов России.

Также были проведены восемь выездных тренировочных сборов проекта Moscow Workshops: Discover Grodno 2019 by Moscow Workshops (Гродно, Республика Беларусь), Discover Vladivostok 2019 by Moscow Workshops (Владивосток, Россия), Discover Kyrgystan 2019 by Moscow Workshops (Бишкек, Кыргызстан), Discover Baikal 2019 by Moscow Workshops (Иркутск, Россия), Discover Riga 2019 by Moscow Workshops (Рига, Латвия), Discover Singapore 2019 by Moscow Workshops (Сингапур), ByteDance + Moscow Workshops Programming Camp 2019 (Пекин, Китай), Hello Muscat Pre-Finals ICPC (Маскат, Оман).

В прошлом году студенты МФТИ взяли призовые места – в Moscow Programming Contest (Москва), в финале ICPC 2019 (бронза), на открытой международной студенческой олимпиаде по программированию имени С.А. Лебедева и В.М. Глушкова KPI-OPEN 2019 в Киеве (1 место), Открытом чемпионате БГУИР (Минск, Республика Беларусь), в XX открытой Всесибирской олимпиаде по программированию им. И.В. Поттосина, VIII Открытом чемпионате БГУИР по программированию, Baltic Sea Digital Event, Petrozavodsk Programming Camp ICPC, Moscow Capture The Flag М*CTF, сборах Moscow Workshops.

Центр развития ИТ-образования – организатор первого университетского лагеря «Олимпиадные школы МФТИ», который проводится на кампусе Физтеха по STEM-предметам. За семь лет 3500 школьников из 20 стран прошли обучение в лагере. Выпускники «Олимпиадных школ МФТИ» уверенно выигрывают на олимпиадах: за это время треть учеников завоевали дипломы регионального и заключительного этапов Всероссийской олимпиады школьников.

Кроме этого, 16 ноября 2019 года, на площадке «Яндекса» была проведена Всероссийская физико-математическая контрольная «Выходи решать!». В решении онлайн по всей России приняло участие 78 тысяч человек.

В прошлом году Центр провел юбилейную десятую Зимнюю компьютерную школу (Moscow Workshops Juniors) – сборы для школьников 9–11 классов и две смены в центре «Сириус». В 2019 году российские школьники стали единственной сборной, которая завоевала сразу четыре золотые медали.

На базе МФТИ проходят регулярные тренировки команд Физтеха с тренером Михаилом Тихомировым. Помимо них в 2019-2020 учебном году впервые открылись Московские тренировки по спортивному программированию, организованные при поддержке Мэра Москвы, которые может посетить любой студент московского вуза совершенно бесплатно.

С 2018 года в МФТИ проходит отбор и подготовка национальной сборной на Международную олимпиаду школьников по информатике IOI (International Olympiad in Informatics). Сборы проводятся в ноябре и мае, в каждых участвуют более 20 ребят, отобранных по результатам Всероссийской олимпиады школьников и других выступлений и заслуг. В результате четверо из них представляют страну на IOI. Команду готовят к соревнованиям тренеры из ведущих университетов России.

С 20 по 24 ноября 2019 года российские школьники завоевали 37 медалей из 91, в том числе 14 золотых, на Международном турнире по информатике в Шумене (Болгария), из которых 15 победителей – участники сборов МФТИ. Также в 2019 году российская сборная стала единственной командой, завоевавшей четыре золота IOI, проходившей в Баку. IOI проводится в формате индивидуального состязания в два ытура, продолжительностью по пять часов, в каждом из которых нужно решить по три задачи по программированию. За каждую задачу можно получить до 100 баллов в зависимости от полноты представленного решения (количества и сложности правильно решенных подзадач). Следующие соревнования пройдут с 19 по 26 июля 2020 года в Сингапуре.

В 2019 году студенты МФТИ приняли участие в 19 российских и международных чемпионатах и сборах. Участие студентов в соревнованиях поддержал Фонд целевого капитала МФТИ.

В 2020 году Центр развития ИТ-образования МФТИ реализует следующие мероприятия:

  1. RuCode. Со 2 марта стартовал онлайн-курс «Быстрый старт в спортивное программирование» – это первая часть проекта RuCode, реализуемого при поддержке Фонда президентских грантов. В этот день прошли два открытых вебинара тренеров, на которых можно было узнать подробности о программе. Записи вебинаров доступны на канале Центра Laboratory for IT-Education, LITED на платформе YouTube. Программа рассчитана на четыре недели и состоит из следующих модулей: 1. Базовые алгоритмы. 2. Теория чисел. 3. Динамическое программирование. 4. Теория графов.
  2. Финал Всероссийской олимпиады школьников по информатике. Олимпиада состоит из четырех последовательных этапов – школьного, муниципального, регионального и заключительного. Муниципальный этап – для школьников с 7-го класса, региональный и заключительный – с 9-го. Однако можно принимать участие в этих этапах, уже начиная с 5-го класса, но в таком случае участники будут выполнять задания, рассчитанные на обучающихся 7-х или 9-х классов соответственно. С 8 по 13 апреля 2020 года в Москве пройдет заключительный этап, состоящий из 2-х туров. Организуют его МФТИ и компания “1С”.
  3. Moscow Pre-Finals Workshops 2020 (Долгопрудный, кампус Физтеха). 18–26 апреля, дивизионы А/В.
  4. Сборы по спортивному программированию для студентов Discover Grodno 2020 by Moscow Workshops в Гродно (Республика Беларусь) 19-25 июля, дивизионы B, C.
  5. Сборы по спортивному программированию для студентов Discover Vladivostok 2020 by Moscow Workshops во Владивостоке (Россия) 19-25 июля, дивизионы A, B/C.

Самые яркие победы МФТИ 2019 года

  1. XIII открытая международная студенческая олимпиада по программированию имени С.А. Лебедева и В.М. Глушкова KPI-OPEN 2019 в Киеве. Команда Moscow IPT: tmp в составе Максима Мачулы, Александра Кулькова и Артёма Комендантяна второй год подряд стала дипломантом олимпиады, завоевав кубок и звание абсолютного победителя олимпиады в 2019 году. Олимпиада проходила с 1 по 5 июля 2019 года в Национальном техническом университете Украины «Киевский политехнический институт имени Игоря Сикорского».
  2. Учебно-тренировочные сборы ПетрГУ. 8–20 февраля в Петрозаводском государственном университете прошли старейшие, 36-е зимние сборы по спортивному программированию при поддержке Moscow Workshops. В сборах участвовали более 50 студенческих команд из университетов России, Японии, Кореи, Эстонии, Литвы, Польши и Казахстана. Команда МФТИ Shock Content в составе Ильи Степанова, Евгения Белых и Андрея Сергунина заняла пятое место по итогам 9 дней сборов.
  3. ByteDance – Moscow Workshops Programming Camp. Команда МФТИ Shock Content (Илья Степанов, Евгений Белых и Андрей Сергунин) стала серебряным призером, заняв 7-е место дивизиона А.
  4. Hello Muscat Pre-Finals ICPC Programming Bootcamp. Бронзовым призером дивизиона А стала команда МФТИ «Never give up», в составе которой выступали Пётр Кулагин, Сергей Золотарёв и Василий Калмыков.
  5. Финал ICPC. Бронзовую медаль и 10-е место завоевала команда МФТИ Shock Content (Илья Степанов, Евгений Белых и Андрей Сергунин).
  6. VIII Открытый чемпионат БГУИР по программированию. На соревновании 2-е место заняла команда МФТИ Racoons в составе Дмитрия Григорьева, Дениса Шпаковского, Николая Третьякова, 9-е место – команда МФТИ _Press_F_to_Flexxx_ в составе Александра Кулькова, Юрия Семенова, 16 место – команда МФТИ Never Give up в составе Петра Кулагина, Василия Калмыкова, Сергея Золотарева.
  7. RuCTF. В личном зачёте 2-е место занял Владас Булавас.
  8. Тренировочные сборы во Владивостоке Discover Vladivostok by Moscow Workshops. Команда МФТИ Grand Content (Александр Кульков, Андрей Сергунин) заняла 2-е место.
  9. Discover Singapore 2019 by Moscow Workshops ICPC. 1-е место в дивизионе А заняла команда МФТИ Godnotent в составе Александра Голованова, Андрея Сергунина и Евгения Белых.
  10. Discover Baikal 2019 by Moscow Workshops. В дивизионе В команда MIPTON от МФТИ получила диплом за лучший результат дорешивания.
  11. Petrozavodsk Programming Camp ICPC. В Карелии команда МФТИ Good game заняла 5-е место.
  12. XX Открытая Всесибирская олимпиада по программированию им. И.В. Поттосина. Команда МФТИ Godnotent (Белых Евгений, Голованов Александр, Сергунин Андрей) заняла 1-е место.
  13. Moscow Programming Contest 2019. На четвертьфинале 26 октября 2019 3-е место заняла команда МФТИ Godnotent (Андрей Сергунин, Александр Голованов, Евгений Белых). На квалификационном туре 2 место также заняла команда МФТИ Godnotent, 3-е место – команда МФТИ Fennecs (Дмитрий Григорьев, Денис Шпаковский, Николай Третьяков).
  14. Хакатон Junction. Cтуденты 4 курса Физтеха Иван Глушенков, Дмитрий Камальдинов и Раед Романов в составе Russian Hack Team стали призерами крупнейшего хакатона Европы.
  15. Moscow Capture The Flag М*CTF. На соревновании 9 ноября 2019 года команда Физтеха «Cv4k5ie» заняла 5-е место в общем зачете.
  16. II региональные межвузовские соревнования по информационной безопасности CenterCTF 2019.
    13-14 ноября 2019 года во Владимире на соревнования приехали 56 студентов из Тулы, Орла, Липецка, Ярославля, Воронежа, Волгограда, Королева, Владимира и Долгопрудного. Команда МФТИ «Blue_Pist0ls» заняла 5-е место.
  17. Moscow ICPC International Workshop 2019 (Долгопрудный). Сборы проходили с 5 по 13 ноября 2019. В них участвовали 180 студентов из 35 университетов и двух школ. Они представляли восемь стран (Россия, Узбекистан, Армения, Литва, Египет, Казахстан, Республика Беларусь, Сербия). В дивизионе А 3-е место заняла команда Godnotent (Евгений Белых, Андрей Сергунин, Александр Голованов).
  18. Baltic Sea Digital Event. Команда МФТИ победила в одной из номинаций международного бизнес-хакатона Baltic Sea Digital Event, финал которого прошел в Риге (Латвия) 15-16 ноября 2019 года. Мероприятие проводилось при поддержке Россотрудничества, организаторами выступили РУДН и МФТИ. На соревнование приехали три команды из Физтеха, каждая в составе четырех человек. В номинации «Лучшее образовательное решение», в том числе, геймификация (отрасль: Образование и Кадры)» победили студенты МФТИ: Елизавета Жадик, ФАКТ, 4-ый курс, Евгений Сиркиза, ФПМИ, 4-ый курс, Мария Карпенко, ФПМИ, 2-ой курс, Димитрис Голяр, ФПМИ, 2-ой курс.
  19. Полуфинал ICPC 2019 региона Северной Евразии (Northern Eurasia Programming Contest). На соревновании 3-е место заняла команда Godnotent (Александр Голованов, Евгений Белых, Андрей Сергунин), 5-е место – Fennecs (Дмитрий Григорьев, Николай Третьяков, Денис Шпаковский), 18-е место – PrAISo (Дмитрий Протасов, Ален Алиев, Георгий Соколов), 31-е место – loWer_bAund (Иван Белков, Александр Синельников, Елисей Судаков), 50-е место – Sable Love (Александр Гришутин, Илья Степанов, Александр Проскурин), 54-е место – LinkCat (Валерий Згурский, Вячеслав Сурков, Максим Гапонов).

Задача. «Контакт» для двоих

  • Имя входного файла:               стандартный ввод
  • Имя выходного файла:            стандартный вывод
  • Ограничение по времени:       2 секунды
  • Ограничение по памяти:         512 мебибайт

Лось Валера очень любит играть в «Контакт» – широко популярную словесную игру; однако поиграть в нее в последнее время удается нечасто, ведь в игре должны участвовать не менее трех игроков, а собраться вместе как минимум втроем из-за нехватки времени и нестыкующихся графиков крайне затруднительно...

В силу этого, лось Валера придумал новую игру – «Контакт для двоих». Суть ее заключается в следующем. Один из игроков загадывает некоторое непустое слово S, которое второй игрок должен отгадать, и сообщает первую букву этого слова. Второй игрок, пытаясь угадать слово, называет одно за другим слова, начинающиеся на заданную букву, а первый игрок сообщает ему, верное ли слово, причем второй игрок не должен повторяться. Если второй игрок назвал некоторое наперед заданное число K слов и так и не угадал слово, то первый игрок сообщает вторую букву слова; после этого, второй игрок может называть лишь слова, начинающиеся с этих двух букв и не названные им ранее (в том числе и когда он знал лишь одну букву). Если после появления второй буквы, второй игрок сумеет назвать еще K слов, то первый игрок сообщает третью букву, и т.д. Если в какой-то момент оказывается, что первый игрок уже назвал все буквы своего слова, а второй после этого назвал K слов, начинающихся с него, но само слово не назвал, то первый игрок просто сообщает, что уже открытые буквы и образуют загаданное слово, и игра заканчивается.

Чтобы игра была интереснее, лось Валера, играя за первого игрока, старается загадать такое слово, чтобы второй игрок сделал как можно больше попыток угадать его (удачная попытка также считается). Однако сам процесс игры зависит от словарного запаса второго игрока, а также от выбранного числа K. Так как лось Валера хорошо знает своих друзей, то для каждого из них Валера может выписать все слова, которые тот знает. Конечно же, чтобы не расстраивать второго игрока, Валера всегда загадывает слово, которое игрок знает. Однако, не так-то просто выбрать это слово и число K. Поэтому Валера решил написать программу, которая по заданному словарю и Q парам «загаданное слово – значение K» определяет, какое максимальное число слов может назвать второй игрок, пока игра не закончится угадыванием слова вторым игроком или сообщением слова первым.

Лось Валера справился с задачей. Справитесь ли вы?

Формат входных данных

В первой строке записано единственное целое положительное число N – количество слов в словаре потенциального второго игрока. В каждой из следующих N строк записано одно непустое слово этого словаря, состоящее из строчных букв английского алфавита. Суммарная длина слов не превосходит 2 · 105.

Обратите внимание: слова могут быть одинаковыми по написанию, например, потому, что они различаются при произношении ударениями: к примеру, в русском языке слова «замОк» и «зАмок» разные слова, хотя пишутся одинаково. В языке, на котором лось Валера и его друзья любят играть в «Контакт», количество возможных акцентов, делающих одинаково записываемые слова разными по звучанию, очень велико. Во время игры участники полностью различают одинаково записываемые слова, произнося их по разному.

В (n + 2)-й строке содержится целое число Q, (1 ≤ Q ≤  2 · 105) – количество исследуемых

пар «загаданное слово – значение K». В следующих Q строках записаны по два целых числа w и K (1 ≤ w, Kn) – номер загаданного слова из словаря и предполагаемое значение K. Cлова нумеруются в том порядке, в котором они заданы выше, начиная с единицы.

Формат выходных данных

Для каждой из Q пар выведите в отдельное строке единственное целое число – максимальное количество слов, которые может назвать второй игрок.

Примеры

стандартный ввод

стандартный  вывод

6

asassin assistant astronaut abrakadabra abbey automaton

9

1 1

1 2

1 3

4 1

4 2

4 3

6 1

6 2

6 3

3

5

6

3

4

5

2

3

4

3

aa ab ab 6

1 1

2 1

1 2

3 2

2 2

3 1

2

2

3

3

3

2

7

pit

pitbul

piter

pitstop

pitlane

petroleum

pistol

6

1 2

1 3

6 4

7 2

7 3

5 1

6

7

5

5

7

4

 
Разбор задачи читайте в журнале.

Подпишитесь на журнал
Купите в Интернет-магазине


Комментарии отсутствуют

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru