Спортивное программирование *

^{_{Победители мобильного трека}}

В уходящем году Яндекс провел два онлайн-чемпионата по программированию. Мы продолжаем публиковать разборы задач второго чемпионата. Напоминаем, что участникам было предложено четыре трека: машинное обучение, фронтенд, мобильная разработка и бэкенд. Перед вами разбор квалификационного раунда для мобильных разработчиков — 121 человек из числа прошедших квалификацию затем приняли участие в финале. Задачи придумали специалисты из Яндекс.Браузера и других команд поискового портала. В этом хабрапосте мы коснемся темы генетических алгоритмов, напишем бота для тетриса и пройдем квест разными для Android и iOS методами.

Многие, как и я, любят футбольные симуляторы и многие увлекаются программированием. Когда-то, в далёком 2004 году, наигравшись в ФИФУ я подумал, что было бы неплохо совместить два моих увлечения в одной игре, в которой игроки управлялись бы не вручную, а написанным для них скриптом. Этакая игра для программистов, а-ля «RoboCup Simulation Soccer», только на свой лад. Я тогда был начинающим программистом и написал уже несколько простеньких игр, но реализовать свою задумку в полной мере не смог, так как не придумал, как написать подходящий интерпретатор языка программирования игроков. Игр для программистов сейчас стало больше, но такую, как я хотел не нашёл, и спустя много лет и тонны написанного кода, я решил вернуться к своей давней задумке.

Игра получилась такой, как я и хотел — funcball.com.

Новый хабрапост в серии разборов недавно прошедшего чемпионата. Участникам квалификации, которые выбрали секцию фронтенда, нужно было решить несколько задач очень разной сложности: первая (по нашим ожиданиям) занимала 20 минут, последняя — около часа. Мы проверяли широкий спектр навыков разработчика интерфейсов, включая способность разобраться в необычной предметной области.

A. Аннигилируй это

^{Авторы: Максим Сысоев, Константин Петряев}

Первая задача — разминочная. Каждому участнику доставался один из четырёх вариантов задачи, похожих между собой. Мы предложили не только текстовое условие, но и «плохое» рекурсивное решение. Нужно было переделать код (написать жадный алгоритм, который выдавал самое быстрое решение), убрав рекурсию и разные глупости вроде лишних операций и вычислений.

Условие

Вы устроились работать в лабораторию по изучению антиматерии, где проводят различные опыты. Ваш отдел изучает процессы, которые происходят при объединении материи и антиматерии. Вам необходимо провести серию опытов над некоторым количеством молекул.

Всем привет! Меня зовут Лида, и я провожу соревнования по программированию уже 12 лет. (Привет, Лида!) В этом году я присоединилась к Команде ВКонтакте и теперь курирую VK Cup. Целых 5 сезонов это был чемпионат только по спортивному программированию. Но настала пора серьёзных изменений.

Мы убрали большую часть ограничений, отменили парный формат и добавили три новых направления. VK Cup 2019 — это онлайн-соревнования для олимпиадных программистов, мобильных разработчиков, дизайнеров и специалистов по машинному обучению с грандиозным офлайн-финалом в Санкт-Петербурге.

В этой статье я расскажу, что нового мы придумали, а мои коллеги дадут рекомендации для участников. Регистрация на VK Cup открыта по ссылке vk.cc/cup до 4 декабря — осталась всего неделя! Все подробности о треках и этапах — под катом.

В октябре состоялся второй чемпионат по программированию. Мы получили 12 500 заявок, более 6000 человек попробовали свои силы в соревнованиях. В этот раз участники могли выбрать один из следующих треков: бэкенд, фронтенд, мобильную разработку и машинное обучение. В каждом треке требовалось пройти квалификационный этап и финал.

По традиции мы опубликуем разборы треков на Хабре. Начнём с задач квалификационного этапа по машинному обучению. Команда подготовила пять таких задач, из которых составила два варианта по три задачи: в первом варианте были задачи A1, B1 и C, во втором — A2, B2 и C. Варианты случайно распределялись между участниками. Автор задачи C — наш разработчик Павел Пархоменко, остальные задачи составил его коллега Никита Сендерович.

За первую простую алгоритмическую задачу (A1/A2) участники могли получить 50 баллов, правильно реализовав перебор по ответу. За вторую задачу (B1/B2) мы давали от 10 до 100 баллов — в зависимости от эффективности решения. Чтобы получить 100 баллов, требовалось реализовать метод динамического программирования. Третья задача была посвящена построению кликовой модели по предоставленным обучающим данным. В ней требовалось применить методы работы с категориальными признаками и воспользоваться нелинейной моделью обучения (например, градиентным бустингом). За задачу можно было получить до 150 баллов — в зависимости от значения функции потерь на тестовой выборке.

По следам «Наши победили: TopCoder Open 2019» публикую задачи с трека Algorithm (классическое спортивное программирование. За полтора часа нужно решить три задачи на Java, C#, C++ или Python.)

1. Пирог на шестерых

Постановка задачи

Лимит времени — 4 секунды.

У вас есть пирог. Если смотреть сверху, пирог имеет форму (строго) выпуклого многоугольника. Вам даны координаты вершин в целых числах X и Y.

У вас есть пять друзей. Вы хотите поделить пирог на шесть частей равной площади (но не обязательно одинаковой формы). Конечно же, любой может это сделать за пять разрезов, но только профи может сделать это за три разреза.

Найдите три разрезания прямыми линиями через одну точку, которые поделят пирог на шесть равных по площади частей. Выведите {x, y, d1, d2, d3}, где (x, y) — общая точка всех трёх разрезов, а d1, d2, d3 — углы направления разрезов в радианах.

В Хьюстоне 13-16 ноября прошёл финал чемпионата TopCoder Open 2019, и Гена Короткевич (Беларусь) занял первое место сразу в двух соревновательных треках: Algorithm и Marathon. Такое раньше ещё никому не удавалось сделать в один год! Отличное завершение сезона-2019, в котором до этого Гена уже победил в финалах двух других крупных соревнований: Google Code Jam и Facebook Hacker Cup.

Topcoder Open — ежегодный индивидуальный профессиональный турнир по программированию, проводимый компанией Topcoder Inc. Проводится по системе Topcoder c 2001 года. Всего в Topcoder шесть видов соревнований: Algorithm, Development, First2Finish, UI Design, UI Prototype и Marathon.

Marathon Match (MM) – это оптимизационная задача, правильный ответ на которую не знают даже организаторы. Программист должен предложить наиболее эффективное решение за короткое время.

Algorithm (SRM) – это классическое спортивное программирование. За полтора часа нужно решить задачи на Java, C#, C++ или Python.

Я готовился к Финалу чемпионата мира Google HashCode 2017. Это крупнейший конкурс с алгоритмическими задачами, организованный Google.

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

После двухдневных соревнований пришли результаты: я выиграл золотую медаль.

Я был в шоке. Я опередил конкурентов с 5-летним опытом. Я знал, что много работал, но это достижение превзошло все мои ожидания. Я понял, что спортивное программирование это моя тема и ушел в нее с головой.

Я знаю, что привело меня к успеху и хочу поделиться этим с вами.

Не мы плохие, а багов много. Разработка искусственного интеллекта для игры “Хоккей” за ~7 часов.

Изначально статья планировалась о стратегиях участников, о том, что они успели сделать за конкурсное время и рады ли проделанной работой, но, опросив финалистов восемь, стало ясно, что ничего не выйдет и надо срочно менять направление.

Дело в том, что на интересующие нас вопросы мы получали максимум 6 слов, а потом сразу же слышали недовольства о багах, с которыми столкнулись участники. Только один человек написал:

Не хочу писать ничего отрицательного, думаю, это некорректно, да и организаторам самим должно быть грустно. Поэтому скажу, что идея задания достаточно интересная, хотя лично мне не очень нравится такой формат соревнований (Анна Прозорова).

Из заголовка статьи понятно, что мы ничего не выиграли. И да, именно “мы”. За конкурсные дни у меня появилось много хороших знакомых, в том числе и Анна (odrus), являющаяся соавтором данной статьи. Также в последний момент мы разговорились со Львом (zadamantiy) и с его разрешения описали участие в финале.

Лично я являюсь участником движения “A Complaint Free World”, но я перевешу свой браслет на другую руку и буду жаловаться, хоть и в шуточной форме, ведь, с другой стороны, таковы условия конкурса и нужно быть хорошим специалистом, чтобы выиграть в нём и совладать с недочётами! Никаких претензий у нас нет, наоборот — большое спасибо!

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

Цель статьи — это собрать фейлы конкурса как со стороны участников, так и со стороны организаторов, зарубить их себе на носу и больше никогда не наступать на те же грабли. Надеемся, что статья повысит уровень очередного конкурса.

Рассказываем о мероприятиях, которые пройдут у нас в ближайшие два месяца. Вместе с этим — делимся конкурсами для тех, кто проходит обучение на технических и других специальностях.


^{Фото: Nicole Honeywill / Unsplash.com}

---

Конкурсы

---

Студенческая олимпиада «Я — профессионал»

Когда: 2 октября — 8 декабря
Где: онлайн

Цель олимпиады «Я — профессионал» — проверить не только теоретические знания учащихся, но и их профессиональные навыки. Задания составляют профессора крупных российских университетов и специалисты ИТ-компаний. Проявившие себя участники смогут поступить в отечественные вузы без экзаменов. И пройти стажировку в Яндексе, Сбербанке и других организациях.

«Я — профессионал» — это попытка исключить ситуации, когда студенты слышат фразу: «Забудьте обо всем, чему вас учили в вузе». Чтобы компаниям не приходилось переучивать полностью подготовленного специалиста. Организован проект силами Общероссийского объединения работодателей и более 20 ведущих вузов России. Техническим партнером выступает Яндекс.

Привет! Меня зовут Дмитрий Андриянов, я работаю разработчиком интерфейсов в Яндексе. В прошлом году я участвовал в подготовке нашего онлайн-соревнования по фронтенду.

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

Меня зовут Волков Игорь. Я работаю в консалтинговой компании на позициях Java разработчика, архитектора, руководителя команды, технического менеджера. Разные роли в зависимости от текущих потребностей проекта. Обратил внимание на конкурсы от mail.ru давно, но активно поучаствовать получилось только на Paper IO.

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

На Positive Hack Days уже в четвертый раз проводилось соревнование The Standoff: это кибербитва между командами атакующих, защитников и экспертных центров безопасности (SOC) за контроль над инфраструктурой виртуального города F.

Перед атакующими стояли те же цели, к которым обычно стремятся киберпреступники, — украсть деньги из банка, похитить конфиденциальные данные, устроить технологическую аварию. Они старались выполнить задания, а команды защитников совместно с командами SOC обеспечивали безопасность своих предприятий и были готовы оперативно отражать атаки противников. Также в этом году к соревнованию присоединились команды разработчиков: в рамках The Standoff проводился хакатон, о его результатах мы уже рассказывали в предыдущей статье.

За ходом The Standoff наблюдал экспертный центр безопасности Positive Technologies (PT Expert Security Center). Наши спецы проанализировали события, которые были зафиксированы средствами защиты Positive Technologies — MaxPatrol SIEM, PT Network Attack Discovery, PT Application Firewall, PT MultiScanner, PT ISIM. С их помощью была восстановлена полная картина противостояния. В этой статье мы расскажем о том, что происходило на площадке и как действовали команды при атаках на различные предприятия и на инфраструктуру города. Для тех, кому лень читать лонгриды, есть сокращенная версия отчета на Anti-Malware.

В этой статье перечислены некоторые трюки, которые применяли участники моего маленького конкурса программирования Commodore 64. Правила конкурса были просты: создать исполняемый файл C64 (PRG), который рисует две линии, чтобы сформировать изображение ниже. Побеждал тот, чей файл меньше по размеру.


Конкурсные работы публиковались в открытых твитах и личными сообщениями, которые содержали только байты PRG-файла и хэш MD5.

Две вещи наполняют душу всегда новым и все более сильным удивлением и благоговением, чем чаще и продолжительнее мы размышляем о них, — это звездное небо надо мной и моральный закон во мне. Иммануил Кант

JS1k — ежегодное соревнование, где надо вместить демо, игру или все что угодно, в 1024 символа на JavaScript. В этом году мое демо заняло четвертое место (до третьего не хватило каких-то два балла). Посмотреть демо можно на сайте JS1k. У кого не открывается или не работает, выглядеть должно так:

Минифицированный и полный исходный код лежит на github. А под катом разбор того, как сейчас минифицируют JavaScript для таких конкурсов.

Мы продолжаем публиковать разборы задач, которые предлагались на недавнем чемпионате. На очереди — задачи, взятые из квалификационного раунда для специалистов по машинному обучению. Это третий трек из четырёх (бэкенд, фронтенд, ML, аналитика). Участникам нужно было сделать модель исправления опечаток в текстах, предложить стратегию игры на игровых автоматах, довести до ума систему рекомендаций контента и составить ещё несколько программ.

Привет, Хабр!

Каждый программист хочет прокачать свои навыки и каждая компания хочет видеть у себя квалифицированных специалистов, но как этого достичь? На помощь приходят олимпиады, об участии в одной из них и будет эта статья.

На прошедшем PHDays 9 мы проводили соревнование по взлому завода по перекачке газа — конкурс Industrial Ninja. На площадке было три стенда с различными параметрами безопасности (No Security, Low Security, High Security), эмулирующих одинаковый индустриальный процесс: в воздушный шар закачивался (а потом спускался) воздух под давлением.

Несмотря на разные параметры безопасности, аппаратный состав стендов был одинаков: ПЛК Siemens Simatic серии S7-300; кнопка аварийного сдува и прибор измерения давления (подсоединены к цифровым входам ПЛК (DI)); клапаны, работающие на накачку и спуск воздуха (подсоединены к цифровым выходам ПЛК (DO)) — см. рисунок ниже.



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

Стенды отличались сложностью включения данного режима: на незащищенном стенде сделать это было проще всего, а на стенде High Security, соответственно, сложнее.

За два дня были решены пять из шести задач; участник, занявший первое место, заработал 233 балла (он потратил на подготовку к конкурсу неделю). Тройка призеров: I место — a1exdandy, II — Rubikoid, III — Ze.

Однако во время PHDays никто из участников не смог одолеть все три стенда, поэтому мы решили сделать онлайн-конкурс и в начале июня опубликовали самое сложное задание. Участники должны были за месяц выполнить задание, найти флаг, подробно и интересно описать решение.

Под катом мы публикуем разбор лучшего решения задания из присланных за месяц, его нашел Алексей Коврижных (a1exdandy) из компании Digital Security, который занял I место в конкурсе во время PHDays. Ниже мы приводим его текст с нашими комментариями.

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

Тем временем мы подготовили разбор задач чемпионата, которые предлагались фронтенд-разработчикам. Это задачи из квалификационного этапа. Напоминаем, что чемпионат проводился по четырём направлениям: бэкенд, фронтенд, машинное обучение и аналитика.

A. Градусник пробок

Условие

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

Привет! Большинство из нас, специалистов в IT сфере, любит играть в игры — карточные, настольные, компьютерные и другие. Зачастую бывает, что игры пользы никакой не приносят, а хотелось бы всё и сразу — удовольствие, фан и знания. Специально для вас мы стараемся изобретать «игры для программистов», которые сочетают в себе всё вышеперечисленное. Предлагаем вам познакомиться с ними и приглашаем принять участие в соревновании по искусственному интеллекту Mini AI Cup #4!