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

Новое поколение программистской элиты собралось в Марракеше, Марокко, чтобы сегодня, 20 мая, сразиться в финале 39-го Студенческого Чемпионата Мира по Программированию (ICPC) Ассоциации Вычислительной Техники, глобальным спонсором которого выступает компания IBM. Чемпионат проходит под патронажем его королевского величества короля Марокко Мохаммеда VI. В этом году принимают чемпионат Университет Мухаммеда V, Университет Аль Ахавейн, Университет Мундиаполиса и Ассоциация ACM в Марокко.

Самое престижное соревнование для программистов со штаб-квартирой в Университете Бэйлора (Baylor University), также известное как «Битва интеллектов» (Battle of the Brains), впервые проходит на африканском континенте. Лучшие студенты-программисты со всего мира за пять часов должны справиться с несколькими сложнейшими задачами из реальной жизни. Все команды соревнуются на время в битве логики, стратегии и выносливости. Спонсором мероприятия выступает IBM. В финал вышли 128 команд студентов из университетов со всего мира, которые сражаются за звание чемпиона по программированию. Победители уже известны, результаты можно просмотреть в конце поста!

Наша команда FlyElephant активно поддерживает разные мероприятия и сегодня мы хотим пригласить всех на ежегодное соревнование программистов — Open Class Programming Competition, которое пройдет 31 мая в Одесском национальном университете имени И.И.Мечникова.

В этом году соревнование приурочено к празднованию 150-летия со дня основания университета.

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

Соревнование будет проходить одновременно в двух режимах — очном и онлайн. Для участия в соревновании необходимо зарегистрироваться на сайте http://codelands.com.

В субботу 25 апреля прошел второй квалификационный раунд Russian Code Cup 2015. 3516 программистов решали задачи в течение двух часов, из них хотя бы одно правильное решение прислали 458 участников.

Первым за 4 минуты и 9 секунд решил задачу A (Турникеты в метро) Машарабов Александр (map). Задачу B (Игра) за 8:48 решил Дубленных Денис (Stigius), задачу C (Палочки и шарниры) за 18:08 решил Нигматуллин Нияз (niyaz.nigmatullin). Задачу D (Числа Фибоначчи) за 1 час 5 минут и 21 секунду решил Лунев Антон (Anton_Lunyov). А последнюю задачу E (Телепорты) за 1 час 44 минуты и 55 секунд решил Кунявский Павел (PavelKunyavskiy), который занял 1 место в рейтинге по итогам раунда. Последняя успешная попытка совершена Альбертом Саакяном за 4 секунды до конца соревнования. Все пять задач сдал только Павел Куявский.

Всего участники отправили на проверку 4287 решений, на С++ их было 3145, на Java — 613. Отметим, что из 2166 решений, сданных на GNU C++, 1218 решений использует С++ 11 стандарта, а остальные все еще не применяют новые возможности языка. Правильных решений на этот раз всего 913, из них на С++ — 726, на Java — 141.

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

Например, Питер Норвиг буквально недавно рассказал, что в Гугле есть негативная корреляция между победами человека на олимпиадах для программистов и его успехами в работе. По его мнению, спортивное программирование приучает концентрироваться на сиюминутных задачах, тогда как на работе надо думать о будущем проекта.

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



Все этапы Яндекс.Алгоритма в этом году пройдут в онлайне, так что поучаствовать в нём смогут и те, кто не готов куда-то ехать. Алгоритм состоит из нескольких отборочных раундов, в каждом из которых нужно решить пять задач за 100 минут. В финал, который состоится 6 августа, выйдут 25 лучших по результатам отбора. Тренировочный раунд, до которого стоит зарегистрироваться, пройдет 3 мая.

Дорогие друзья!
Приглашаем вас на главное студенческое событие этой весны – IMAGINE DAY!
Imagine Day – это российский финал Imagine Cup и Student Day. Мероприятие состоится 18 апреля 2015 года, с 9:00 до 18:00, в Конгресс-центре Технополис Москва. Для тех, кто живет далеко и не сможет приехать в Москву – мы организуем онлайн-трансляцию докладов и интервью с командами на сайте imaginecup.ru. Начало трансляции в 10:00 (МСК). Вас ждут прямые включения с площадки, интервью с участниками, а также беседы с жюри!

Итак, вчера мы с вами поиграли в джавовский вариант «Интеллектуальное казино против знатоков», и при этом, при всем уважении к хабровчанам, телезрители выиграли! Победителем этого этапа стал Сергей SerCe Целовальников, решивший три задачи. Как и обещали — мы вручаем ему небольшой приз: VIP-билет на JPoint!

Но радости в сторону. Вчера нас с телезрителями обвинили в том, что большинство вчерашних задач были связаны с Java весьма косвенно. Мы принимаем это обвинение, и поэтому сегодня у нас вариант на чистой Java! никаких спрингов, эксэмэлей и паттернов. Это будет настоящее испытание для истинных любителей хардкора!

Под катом — ответы на вчерашний раунд и суперблиц! Против знатоков сегодня играет телезритель из Петербурга Андрей apangin Паньгин.

Привет! Мы тут собрали тусовку одних из самых крутых русскоязычных Java-практиков и попросили их дать по задаче, чтобы вы сломали зубы, мозг и бились об стену, пытаясь понять, как это работает. Собственно, мы поспорили на бутылку Хеннеси, что за 12 часов после публикации никто не пришлёт все правильные ответы. Я уверен, что кто-то сможет. Поэтому если вы это сделаете первым – с меня бутылка.

Первая задача простая, она от телезрителя Николая Гарбузова, специалиста по скалкам, любящего рекурсию, паттерн-матчинг и магию компиляции:

Скомпилируется ли следующий аспект AJC компилятором?
Если да — то что он выведет на консоль при компиляции?

public aspect QuizAspect {
    public static int count(int i) {
        return i++;
    }

    before (int n) : execution(public int QuizAspect.count(int)) 
            && args(n) && if(QuizAspect.count(1)>1) {
        System.out.println("QuizAspect " + n);
    }
}

Пока просто, правда?

Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.

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

Наивный алгоритм

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

static BigInteger FactNaive(int n)
{
    BigInteger r = 1;
    for (int i = 2; i <= n; ++i)
        r *= i;
    return r;            
}

На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.

Совершенно случайно узнал об интересной задаче, которая очень даже может взбодрить.

Задача:

На столе лежат 12 совершенно одинаковых по виду шаров, но один из них — фальшивый. Он отличается от остальных шаров по весу (мы не знаем, легче он или тяжелее). В вашем распоряжении имеются чашечные весы без гирь. Нужно найти аномальный шар за минимальное количество взвешиваний (подсказка — решение можно найти за 3 взвешивания).

В субботу 28 марта прошел первый квалификационный раунд Russian Code Cup 2015. 3093 программиста решали задачи в течение двух часов, из них хотя бы одно правильное решение прислали 1012 участников. Верное решение для всех пяти задач сдали двое: Геннадий Короткевич и Петр Митричев. Всего участники отправили на проверку 4069 решений, 2517 на С++, 705 на Java, 425 на Python, 318 на C#. Правильных решений — 1745, из них на С++ прислано 1099, на Java — 339.

Первым за рекордные 2 минуты и 2 секунды решил задачу A (Магические карточки) победитель RCC 2014 года — Геннадий Короткевич (tourist). Он же первым решил задачи B (Домашнее задание) за 6:50 и C (Конгресс юных любителей) за 25:43. Задачу D (Расшифровка) за 51 минуту и 42 секунды решил победитель RCC 2013 года Петр Митричев (Petr). А последнюю задачу E (Занимательная криптография) за 1 час 2 минуты и 52 секунды решил участник из Японии (anta). Последняя успешная попытка совершена Михаилом Тихомировым за 6 секунд до конца соревнования. Самая простая задача A, самая сложная задача — E, задачу E сдало всего 13 человек.

В воскресенье прошел тренировочный warmup-раунд Russian Code Cup. Первое место занял Михаил «mmaxio» Майоров из Перми. Второе — Игорь «kraskevich» Краскевич из Москвы. Третье — Валентин «ValenKof» Кофман из Москвы. Поздравляем победителей!

Впереди квалификационные раунды чемпионата. Напоминаем, что первый квалификационный раунд состоится 28 марта в 18:00 мск, а регистрация на чемпионат проходит на сайте http://www.russiancodecup.ru/ до начала третьего квалификационного раунда.

Russian Code Cup — это возможность для русскоязычных программистов со всего мира проверить свои силы и продемонстрировать мастерство, решая оригинальные задачи различной сложности, а также заявить о себе экспертному IT-сообществу. Олимпиада проходит в три этапа: квалификационные раунды, отборочный тур и финал, — на каждом из которых участникам олимпиады предлагается от четырех до восьми разноплановых задач. Задания и техническую часть соревнования обеспечивают специалисты Mail.Ru Group и эксперты Университета ИТМО — соорганизатора Russian Code Cup.

А сейчас разберемся с решением задач warmup-раунда.

Задача A. Воздушные шарики

Привет Хабражителям!

В 2014 году мы провели свой первый совместный контест по спортивному программированию совместно с Codeforces, об этом мы писали здесь.

Коротко о том, как это было:

Контест состоял из 6 задач, на решение отводилось 2,5 часа (ознакомиться с задачами прошлого года и даже попробовать свои силы в их решении вы можете здесь).
Конечно же, даже на сугубо девелоперском мероприятии мы остались верны себе, поэтому все задачи были придуманы по мотивам наших игр, и, разумеется, мы их заботливо проиллюстрировали:



Впервые за всю историю Codeforces в контесте приняли участие одновременно более 2148 человек (зарегистрировалось более 4600 (!) со всего мира. К слову сказать, первые 3 места заняли

С 5 марта открыта регистрация на участие в главном российском чемпионате по спортивному программированию — Russian Code Cup (RCC). Победители чемпионата завоюют звание лучших программистов года и разделят призовой фонд в размере 750 000 рублей. В RCC ежегодно принимают участие несколько тысяч русскоговорящих участников со всего мира. Они сражаются за звание не только самого талантливого, но и самого быстрого программиста, поскольку решение оригинальных и сложных задач чемпионата оценивается сразу по двум критериям: качество и скорость. Этот чемпионат дает молодым программистам прекрасную возможность продемонстрировать свое мастерство, получить признание профессионального сообщества и обратить на себя внимание крупных IT-компаний.

В одном нецентральномотдаленном регионе нашей необъятной страны как-то раз проходил очередной региональный этап Всероссийской олимпиады школьников по информатике и программированию. До 2014 года всё было хорошо, проводили олимпиаду на старой системе, написанной в далеких 2004 годах очень одаренным программистом, на Delphi. С тех пор его никто не менял — работал, ну и ладно. В 2014 году решили попробовать ejudge. Поднимать всё с исходников не стали, решили взять готовое, образ для виртуальной машины. Всё было хорошо, все работало.

Но тут наступил 2015 год, в котором некоторые пункты проведения олимпиады немножко, совсем чуть-чуть поменяли, и нужные «человеки» об этих изменениях узнали только за 1-2 дня до начала…

Тут-то и начинается самое веселое.

С середины ноября по 31 декабря 2014 года мы в проекте KolibriOS проводили конкурс разработчиков игр. За полтора месяца нужно было написать новую игру для Колибри (или портировать свою собственную существующую). «Исходники» игры (включая все «ресурсы» — картинки, спрайты, звуки, музыку, если таковые имеются) должны были быть выложены на SVN проекта под одной из open-source лицензий. Игра должна была компилироваться из исходников с помощью системы авто-сборки Tup на сервере КолибриОС.

Всего на наш призыв откликнулись 7 человек, которые создали для конкурса в сумме 10 игр (один участник написал целых 3 игры, ещё один — 2 игры; остальные участники написали по одной игре каждый). Сегодня мы выносим эти игры на суд читателей Хабра, и просим вас проголосовать за наиболее понравившиеся. Чтобы поиграть в конкурсные игры, нужно скачать с сайта KolibriOS последнюю ночную сборку дистрибутива («Универсальный образ Flash/HDD» либо «Загрузочный компакт-диск LiveCD»). Игры находятся в папке /KolibriOS/games. Качать нужно русскую сборку, так как некоторые игры (имеющие исключительно русскоязычный интерфейс) присутствуют только в ней.

TL;DR: Если нет времени, возможности или желания читать все описания игр и играть в них самим, но всё равно очень хочется проголосовать, то можно посмотреть ролик с обзором игр от независимого блоггера Кирилла Лейфера, и оценить игры на основании ролика:

В заголовке порядок слов не перепутан.



Живет в Венгрии юный программист Адам Кишш. Он участвует в чем-то типа онлайн-олимпиады KöMaL. Для решения заданий по информатике предлагается использовать несколько обычных языков программирования: С, С++, Python и некоторые другие. В одном из заданий требовалось написать Сапер и бота для игры в него. Такая задача очень легко решается средствами табличного процессора — того же Excel, например, и пачки макросов. Однако же, макросы использовать нельзя. Адам выкрутился необычным способом: реализовал в книге Excel простенький виртуальный компьютер, который программируется на Ассемблере — Excembler.

Есть много материала по решению запутанных задачек на Прологе (например, страница Hakan Kjellerstrand о B-Prolog). Однако часто приводятся задачи, которые либо создавались для решения вручную (имеют маленькое пространство поиска), либо изначально ориентированы на решение при помощи логического программирования.

Я хочу показать мое решение на Прологе задачи AAAAAA с первого раунда Facebook Hacker Cup 2014. Задача имеет достаточно большое пространство поиска и создана с прицелом на решение опытными спортивными программистами на распространенных языках программирования.

Потоки ввода-вывода в стандартной библиотеке C++ просты в использовании, типобезопасны, устойчивы к утечке ресурсов, и позволяют простую обработку ошибок. Однако, за ними закрепилась репутация «медленных». Этому есть несколько причин, таких как широкое использование динамической аллокации и виртуальных функций. Вообще, потоки — одна из самых древних частей стандартной библиотеки (они начали использоваться примерно в 1988 году), и многие решения в них сейчас воспринимаются как «спорные». Тем не менее, они широко используются, особенно когда надо написать какую-то простую программу, работающую с текстовыми данными.

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

Сегодня в комментариях у посту возникло обсуждение о медленности iostreams. В частности, freopen пишет

Забавно смотреть на ваши оптимизации, расположенные по соседству со считыванием через cin :)

а aesamson даёт такую рекомендацию

Можно заменить на getchar_unlocked() для *nix или getchar() для всех остальных.
getchar_unlocked > getchar > scanf > cin, где ">" означает быстрее.

В этом посте я развею и подтвержу некоторые мифы и дам пару рекомендаций.

Конкурс конкурсу рознь. Одно дело, когда успешный на локальном рынке фреймворк открывает API и хочет конкурсом рассказать всему миру об этом событии. И совсем другое – когда корпорация пытается поднять с колен свою экосистему приложений или выпускает новое устройство. Тут другие бюджеты с разницей даже не в разы, а на порядки, другие модели соревнований и, вроде бы, другие шансы.

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.