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

Меня зовут Андрей Рыбалка, я участвую в Russian AI Cup под ником lama и я снова расскажу вам, как не выиграть макбук. Благо, я в этом человек опытный — вот этими вот руками не выиграл уже целых 7 штук.

Итак, задачей этого года был платформер/2D-шутер, для которого нужно было написать бота. Выглядела игра вот так:

Бот выглядел так:

Если вам интересно, как картинка #2 играла в картинку #1, прошу под кат.

В прошлом году мы провели онлайн-квест для мобильных разработчиков — Droid Mission. В течение месяца участники должны были решить как можно больше задач в трёх направлениях: fix it! (поиск ошибок и исследование кода), hack it! (реверс-инжиниринг) и dig it! (изучение особенностей Android). Всего в квесте было 23 задачи — они очень похожи на те, с которыми сталкиваются специалисты по Android в реальной работе. В посте мы покажем все условия и правильные решения.

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

Данный пост написан для новичков в олимпиадном программировании и начинающих разработчиков, готовящихся к прохождению алгоритмических интервью. В конце бонусная задачка. Если заинтересовал, прошу под кат :)

^{_{Вручение призов участникам трека бэкенда}}

Мы завершаем серию разборов второго чемпионата по программированию. В последние недели мы опубликовали разборы трёх треков: по ML, фронтенду и мобильной разработке. Осталось разобрать трек по бэкенду. Он оказался самым популярным: 2682 человека приняли участие в квалификации, 320 из них дошли до финала. Задачи для бэкенд-разработчиков придумала команда Яндекс.Такси.

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

В уходящем году Яндекс провел два онлайн-чемпионата по программированию. Мы продолжаем публиковать разборы задач второго чемпионата. Напоминаем, что участникам было предложено четыре трека: машинное обучение, фронтенд, мобильная разработка и бэкенд. Перед вами разбор квалификационного раунда для мобильных разработчиков — 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, аналитика). Участникам нужно было сделать модель исправления опечаток в текстах, предложить стратегию игры на игровых автоматах, довести до ума систему рекомендаций контента и составить ещё несколько программ.