Разбирая одну олимпиадную задачу мы отправимся по петляющим коридорам генерации лабиринтов и их прохождения, а также увидим, что на языке Julia простота реализаций алгоритмов граничит с их псевдокодом.
Вдохновлялись продакшеном и баскетболом: как Яндекс готовит чемпионат по программированию
6 мин
В конце мая начнётся наш чемпионат по программированию. Он будет проходить в онлайне и позволит проверить себя в одной из четырёх сфер: бэкенд- или фронтенд-разработке, машинном обучении или аналитике данных. Задачи для секций разработали в управлении машинного интеллекта и исследований, Поиске и геосервисах.
Всем участникам сначала предстоит преодолеть квалификационный раунд. После подачи заявки вы сами выберете, когда его проходить. Квалификация 4-часовая и включает в себя от 4 до 6 задач. Самых лучших мы пригласим к участию в финале, который пройдёт 1 июня, тоже в онлайне. Результаты станут известны 5 июня. Победители в каждом направлении получат по 300 тысяч рублей, второе место — 150 тысяч рублей, третье — 100 тысяч. Регистрация открыта и продлится до последнего дня квалификационного раунда — 26 мая, но лучше отправить заявку пораньше.
В этом посте мы поделимся опытом проведения подобных конкурсов — в части аудитории и составления сложных алгоритмических задач.
Всем участникам сначала предстоит преодолеть квалификационный раунд. После подачи заявки вы сами выберете, когда его проходить. Квалификация 4-часовая и включает в себя от 4 до 6 задач. Самых лучших мы пригласим к участию в финале, который пройдёт 1 июня, тоже в онлайне. Результаты станут известны 5 июня. Победители в каждом направлении получат по 300 тысяч рублей, второе место — 150 тысяч рублей, третье — 100 тысяч. Регистрация открыта и продлится до последнего дня квалификационного раунда — 26 мая, но лучше отправить заявку пораньше.
В этом посте мы поделимся опытом проведения подобных конкурсов — в части аудитории и составления сложных алгоритмических задач.
МФТИ получил право провести Чемпионат мира по программированию ICPC в 2020 году в Москве
2 мин
Вчера в конгресс-центре «Альфандега» в Порту объявили, что Москва выбрана площадкой для проведения старейшего и самого престижного в мире студенческого чемпионата по спортивному программированию International Collegiate Programming Contest (ICPC) в июне следующего года. Организатором финала выступит МФТИ при поддержке компании RDI.Creative.
За право принять финал боролись в этом году Шанхай, Сидней и Орландо. Исполнительный директор ICPC, профессор Университета Бейлор и член Ассоциации вычислительной техники Уильям Паучер поздравил столицу России с победой: «На финале чемпионата ICPC 2019 в Порту мы встретились с делегацией от МФТИ и наметили план проведения финала в июне 2020 года в Москве. В следующем году мы соберемся вместе, чтобы наградить самых одаренных студентов в области программирования, которые умеют изобретать решения для проблем будущего. Я в предвкушении того, что в Москве состоится крупнейший финал в истории ICPC, и я смогу приветствовать всех по-русски со словами: «Добро пожаловать!».
Интервью с Андреем Станкевичем про спортивное программирование
18 мин
В рамках проекта АйтиХайп мы записали видеоинтервью с Андреем Станкевичем, легендарным тренером команды университета ИТМО по спортивному программированию, которая стабильно из года в год побеждает всех подряд на международных соревнованиях.
А для тех, кому видеоверсия не очень интересна, под катом мы подготовили подробную расшифровку интервью, где Андрей рассказывает про нюансы спортивного программирования, подготовки школьников к олимпиадам, российское образование, зарплаты и встречи с президентами.
«Сражение в прямом эфире»: финал ICPC в Порту
3 мин
Сегодня в португальском городе Порту пройдет финал международных соревнований по программированию ICPC 2019. В нем примут участие представители Университета ИТМО и другие команды из вузов России, Китая, Индии, США и других стран. Расскажем подробнее.
Как волонтёры со всего мира создают прямой эфир ICPC-2019
3 мин
Меня зовут Лида Перовская, я работаю в Яндексе, а ещё с 2015 года помогаю организовывать прямой эфир International Collegiate Programming Contest. ICPC — студенческий чемпионат мира по программированию — проводится ежегодно с 1970-х. Это чуть ли не единственная олимпиада подобного уровня, которое развивается благодаря усилиям сотен волонтёров со всего мира. Сегодня я расскажу читателям Хабра о том, как устроена моя работа на ICPC изнутри. А ещё приглашаю посмотреть трансляцию мероприятия и попробовать собственные силы в решении задачек одновременно с участниками.
Для нас — волонтёров — важно, чтобы мероприятие было интересным и полезным и для участников, и для зрителей. Но сделать это непросто. На один только финал заявлено 135 команд из 110 стран, в каждой команде по три человека, и все они участвуют одновременно! Кого, когда и как пускать в эфир? Какой код показывать? Как комментировать, чтобы это было полезно?
Разбор задач. Бинпоиск_1
3 мин
Здравствуйте, уважаемые хабровчане. Серия статей содержит разбор задач, которые дают в 8 классе на уроках информатики в Челябинском физико-математическом лицее №31. Немного истории… Наш лицей — одно из сильнейших учебных заведений России, который в рейтинге по конкурентоспособности выпускников занимает 5 место, уступив школам Москвы и Санкт-Петербурга. Ученики регулярно побеждают на олимпиадах всероссийского и международного уровня.
Данная статья лишена теории, она содержит только способы решения задач. Подробно про бинпоиск описано здесь.
Так вот, перейдем к задачам. Эти задачи подразумевают собой использование бинарного поиска, в том числе бинпоиска по ответам. Как мы знаем бинпоиск — это алгоритм поиска объектов по заданному признаку в множестве объектов. Применяем для отсортированных по возрастанию/убыванию списков. Всего 4 задачи, 2 из которых направлены на применение "алгоритма без изюминок".
Rekko Challenge
8 мин
Сегодня мы запускаем Rekko Challenge 2019 — соревнование по машинному обучению от онлайн-кинотеатра Okko.
Мы предлагаем вам построить рекомендательную систему на реальных данных одного из крупнейших российских онлайн-кинотеатров. Уверены, что эта задача будет интересна и новичкам, и опытным специалистам. Мы постарались сохранить максимальный простор для творчества, при этом не перегружая вас гигабайтными датасетами с сотнями предварительно посчитанных признаков.
Подробнее про Okko, задачу, данные, призы и правила — ниже.
Классификация рукописных рисунков. Доклад в Яндексе
8 мин
Несколько месяцев назад наши коллеги из Google провели на Kaggle конкурс по созданию классификатора изображений, полученных в нашумевшей игре «Quick, Draw!». Команда, в которой участвовал разработчик Яндекса Роман Власов, заняла в конкурсе четвертое место. На январской тренировке по машинному обучению Роман поделился идеями своей команды, финальной реализацией классификатора и интересными практиками соперников.
— Всем привет! Меня зовут Рома Власов, сегодня я вам расскажу про Quick, Draw! Doodle Recognition Challenge.
— Всем привет! Меня зовут Рома Власов, сегодня я вам расскажу про Quick, Draw! Doodle Recognition Challenge.
Russian AI Cup 2018, история 9 места
11 мин
Итак
Меня, как и в прошлом году, зовут Андрей Рыбалка, только в этот раз мне 33. И, раз уж я оказался в десятке лучших, я решил снова поделиться своим подходом к написанию игрового бота для Russian AI Cup 2018.
В этот раз заданием был футбол. Сама задача несколько напоминала RAIC 2014 года, когда был хоккей, но вот решение было совсем другим.
Мир в этот раз был трёхмерным и эта трёхмерность использовалась по полной программе. Сама игра больше всего напоминала Rocket League.
Не буду утомлять вступительной частью, проще показать, как это выглядело. Посмотреть игры можно на сайте, либо на видео:
История участия (и победы) в Russian AI Cup 2018 — CodeBall
10 мин
Была среда, шло обычное скучное заседание на работе. Дизайнер чесал за ухом, а тестировщик уткнулся в телефон. За окном завелся автомобиль, и мне пришло письмо на телефон — стартовал Russian AI Cup 2018. Вокруг никто ни о чем не подозревал, а я в этот момент уже точно знал, чем буду заниматься в следующие полтора месяца.
Привет всем, меня зовут Андрей Токарев и я хотел бы поделится опытом участия в Russian AI Cup 2018.
Russian AI Cup — ежегодное соревнование по искусственному интеллекту, проводимое с 2012 года. Здесь нужно написать алгоритм который управляет кем-то или чем-то, и эти кто-то или что-то соревнуются между собой. В этом году нужно было управлять роботами играющими в футбол.
У меня уже был некоторый опыт выступления в подобных соревнованиях. В частности я участвовал в Russian AI Cup 2016 (без призового места) и Mini AI Cup 2018 (2-е место).
Привет всем, меня зовут Андрей Токарев и я хотел бы поделится опытом участия в Russian AI Cup 2018.
Что это?
Russian AI Cup — ежегодное соревнование по искусственному интеллекту, проводимое с 2012 года. Здесь нужно написать алгоритм который управляет кем-то или чем-то, и эти кто-то или что-то соревнуются между собой. В этом году нужно было управлять роботами играющими в футбол.
У меня уже был некоторый опыт выступления в подобных соревнованиях. В частности я участвовал в Russian AI Cup 2016 (без призового места) и Mini AI Cup 2018 (2-е место).
Как я обучал нейросеть для реализации функции оценки положения на Russian AI Cup CodeBall 2018
12 мин
Имея возможность качественно оценить положение в игре в какой-то момент времени и возможность симулировать игровой мир, при создании бота, для одного из решений, остается лишь стремиться совершать такие действия, которые приводят к улучшению этой оценки в ближайшем будущем.
Функция оценки положения — возвращает вещественное значение где меньшее означает худшее. На вход такой функции я подавал только положение и вектор скорости мяча. Изначально эта функция была реализована довольно простыми формулами и парой if-ов. Однако это дало хорошую основу для накрутки на localrunner-е множества логов для последующего обучения нейросети. Так я прокрутил 300 игр (по 18000 тиков) локально, что в сумме дало около 12ГБ логов и плюс к этому 145 логов игр топов было скачано с сервера (5.7гб).
Далее нужно было выделить из этих логов обучающую и тестовую выборки. Делал я это следующим образом: отталкиваясь от забитого гола смотрел в «прошлое» на 300 тиков (5 секунд) и шагом в 5 тиков каждое положение и скорость мяча + эталонную оценку брал за пример.
Важный момент: эталонная оценка (выход) здесь вычислялась по формуле где S = -1 если мяч залетает в «мои» ворота и 1 в обратном случае, а T это время в тиках оставшееся до гола.
Функция оценки положения — возвращает вещественное значение где меньшее означает худшее. На вход такой функции я подавал только положение и вектор скорости мяча. Изначально эта функция была реализована довольно простыми формулами и парой if-ов. Однако это дало хорошую основу для накрутки на localrunner-е множества логов для последующего обучения нейросети. Так я прокрутил 300 игр (по 18000 тиков) локально, что в сумме дало около 12ГБ логов и плюс к этому 145 логов игр топов было скачано с сервера (5.7гб).
Далее нужно было выделить из этих логов обучающую и тестовую выборки. Делал я это следующим образом: отталкиваясь от забитого гола смотрел в «прошлое» на 300 тиков (5 секунд) и шагом в 5 тиков каждое положение и скорость мяча + эталонную оценку брал за пример.
Важный момент: эталонная оценка (выход) здесь вычислялась по формуле где S = -1 если мяч залетает в «мои» ворота и 1 в обратном случае, а T это время в тиках оставшееся до гола.
Как победить в цифровом WorldSkills? На практическом примере
6 мин
Привет, Хабр!
В декабре наш коллега от направления «Продвинутая аналитика» Леонид Шерстюк занял первое место в компетенции Машинное обучение и большие данные во II отраслевом чемпионате DigitalSkills. Это «цифровая» ветка известных профессиональных конкурсов, которые устраивает WorldSkills Russia. Всего в чемпионате приняли участие более 200 человек, соревновались за лидерство по 25 цифровым компетенциям – Корпоративная защита от внутренних угроз ИБ, Интернет-маркетинг, Разработка компьютерных игр и мультимедийных приложений, Квантовые технологии, Интернет вещей, Промышленный дизайн и т.д.
В качестве кейса для Машинного обучения была предложена задача по мониторингу и обнаружению дефектов трубопроводов АЭС, нефтяных и газотрубопроводов с помощью системы полуавтоматического ультразвукового контроля.
О том, что было на конкурсе и как ему удалось победить, Леонид расскажет под катом.
В декабре наш коллега от направления «Продвинутая аналитика» Леонид Шерстюк занял первое место в компетенции Машинное обучение и большие данные во II отраслевом чемпионате DigitalSkills. Это «цифровая» ветка известных профессиональных конкурсов, которые устраивает WorldSkills Russia. Всего в чемпионате приняли участие более 200 человек, соревновались за лидерство по 25 цифровым компетенциям – Корпоративная защита от внутренних угроз ИБ, Интернет-маркетинг, Разработка компьютерных игр и мультимедийных приложений, Квантовые технологии, Интернет вещей, Промышленный дизайн и т.д.
В качестве кейса для Машинного обучения была предложена задача по мониторингу и обнаружению дефектов трубопроводов АЭС, нефтяных и газотрубопроводов с помощью системы полуавтоматического ультразвукового контроля.
О том, что было на конкурсе и как ему удалось победить, Леонид расскажет под катом.
Ближайшие события
Две истории о том, как проходили мероприятия по программированию в Екатеринбурге
32 мин
Немного разбавим зимние холодные дни теплыми воспоминаниями о том, как в Екатеринбурге проходили: финал RuCTF 2012 (соревнования по защите информации) и финал 38-ого чемпионата мира по программированию «The 2014 ACM ICPC World Finals».
Много фото внутри.
Создание бота для участия в Russian AI Cup 2018 CodeBall
6 мин
Туториал
Сложилась традиция, что после соревнований по спортивному программированию победитель или просто игрок выкладывает на Хабре статью, чтобы рассказать как здорово было участвовать в соревновании и как вариант победить в нем. Из его статьи конечно же многое можно почерпнуть для будущих соревнований.
Но вот про участие в текущем соревновании на стадии бета тестирования думаю статей мало, понятно, что нельзя публиковать код решения, неизвестно еще как хорошо это решение и вообще много еще неизвестно, ведь сейчас по сути только начало турнира, но в этом и прелесть. Автор дает читателю шанс заскочить на отправляющийся поезд и насладиться новогодней поездкой в мир игровых стратегий.
«Программирование в прямом эфире»: как прошел региональный полуфинал ICPC в Университете ИТМО
9 мин
В начале декабря полуфинал студенческого чемпионата мира по программированию ICPC. Расскажем, какие «испытания» прошли его участники и кто будет представлять регион Северная Евразия весной, на главном мировом турнире спортивных программистов.
«Pascal и уж тем более Basic точно не нужны»: интервью с тренерами по спортивному программированию
10 мин
В этом году ВКонтакте при поддержке Промсвязьбанка запустила стипендиальную программу VK Fellowship для преподавателей информатики. Совместно мы отобрали 15 преподавателей из регионов России: создателей авторских курсов по программированию, школьных учителей, директоров центров дополнительного образования, тренеров, которые готовят школьников к международным олимпиадам по программированию. Они получили стипендии от ВКонтакте и Промсвязьбанка и теперь участвуют в наших выездных школах.
Все преподаватели имеют большой опыт и являются авторами собственных курсов по основам программирования. В этом посте мы попросили трех стипендиатов ответить на наши вопросы о преподавании программирования и информатики вообще.
Все преподаватели имеют большой опыт и являются авторами собственных курсов по основам программирования. В этом посте мы попросили трех стипендиатов ответить на наши вопросы о преподавании программирования и информатики вообще.
HighLoad Cup #2. Чемпионат для backend-разработчиков снова в строю
7 мин
Вы готовы к новым нагрузкам? Приглашаем всех любителей и профессионалов на чемпионат по проектированию и администрированию высоконагруженных сервисов HighLoad Cup #2!
Начало соревнованию было положено еще в прошлом году. Тогда мы знали, что HighLoad Cup — это именно тот чемпионат, которого не хватало в ряде проектов Mail.Ru Group. В первом пилотном соревновании участвовало 449 человек. Было много кода и много пота как у самих организаторов, так и участников (8789 различных решений). Были нюансы в технической реализации, но главное, что всем понравилось! Организаторы провели множество ночей в датацентре, несколько выходных — в офисе. Готовы к этому снова! В конце статьи вы найдете полезные материалы от нас и от участников, которые помогут вам разобраться в механике и найти какие-то best practice-решения.
На этот раз постарались подготовить для вас дельце посложнее. Кроме того, мы расширили аудиторию, теперь в соревновании могут принять участие и англоязычные пользователи. Присоединяйтесь к русскоязычному сообществу в Telegram. Там вы получите множество инсайтов по соревнованию :)
Итак, добро пожаловать на борт!
Алгоритм резервуарной выборки
3 мин
Резервуарная выборка (eng. «reservoir sampling») — это простой и эффективный алгоритм случайной выборки некоторого количества элементов из имеющегося вектора большого и/или неизвестного заранее размера. Я не нашел об этом алгоритме ни одной статьи на Хабре и поэтому решил написать её сам.
Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:
Задача «вернуть K случайных элементов из вектора размером N» уже хитрее. Здесь уже можно ошибиться — например, взять K первых элементов (это нарушит требование случайности) или взять каждый из элементов с вероятностью K/N (это нарушит требование взять ровно K элементов). Кроме того, можно реализовать и формально корректное, но крайне неэффективное решение «перемешать случайно все элементы и взять K первых». И всё становится ещё интереснее, если добавить условие того, что N — число очень большое (нам не хватит памяти сохранить все N элементов) и/или не известно заранее. Для примера представим себе, что у нас есть какой-то внешний сервис, присылающий нам элементы по одному. Мы не знаем сколько их придёт всего и не можем сохранить их все, но хотим в любой момент времени иметь набор из ровно K случайно выбранных элементов из уже полученных.
Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
Итак, о чём же идёт речь. Выбрать один случайный элемент из вектора — это элементарная задача:
// C++
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, vect.size() — 1);
auto result = vect[dis(gen)];
Задача «вернуть K случайных элементов из вектора размером N» уже хитрее. Здесь уже можно ошибиться — например, взять K первых элементов (это нарушит требование случайности) или взять каждый из элементов с вероятностью K/N (это нарушит требование взять ровно K элементов). Кроме того, можно реализовать и формально корректное, но крайне неэффективное решение «перемешать случайно все элементы и взять K первых». И всё становится ещё интереснее, если добавить условие того, что N — число очень большое (нам не хватит памяти сохранить все N элементов) и/или не известно заранее. Для примера представим себе, что у нас есть какой-то внешний сервис, присылающий нам элементы по одному. Мы не знаем сколько их придёт всего и не можем сохранить их все, но хотим в любой момент времени иметь набор из ровно K случайно выбранных элементов из уже полученных.
Алгоритм резервуарной выборки позволяет решить эту задачу за O(N) шагов и O(K) памяти. При этом не требуется знать N заранее, а условие случайности выборки ровно K элементов будет чётко соблюдено.
Фронтенд, алгоритмы и опоссум Фридрих. Разбираем задачи конкурса Яндекса
32 мин
Этим постом мы завершаем серию публикаций о конкурсах Яндекс.Блиц в 2018 году. Надеемся, что вам довелось поучаствовать или хотя бы посмотреть, какие приближенные к продакшену задачи мы предлагаем. Последний контест был посвящен применению алгоритмов во фронтенде. Сегодня мы публикуем подробные разборы 12 задач: первые 6 из них предлагались в квалификационном раунде, а задачи 7–12 — в финале. Мы постарались объяснить, как формировались условия, на какие навыки мы обращали внимание. Спасибо всем участникам за проявленный интерес!
Первая задача должна была быть разминочной, на 20 минут, и мы решили сделать ее условие таким, чтобы она легко решалась с помощью регулярных выражений.
Задача 1
Первая задача должна была быть разминочной, на 20 минут, и мы решили сделать ее условие таким, чтобы она легко решалась с помощью регулярных выражений.