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

Вчера начался новый контест от azspcs.net. Он продлится 3 месяца, так что все успеют поучаствовать.
Задание следующее: нужно придумать 2*25 квадратов размера NxN (от 3х3 до 27х27). В клетках квадрата нужно проставить числа от 1 до N^2 (соответственно «от 1 до 9» для наименьшего квадрата и «от 1 до 729» для наибольшего квадрата), числа не повторяются.

Пару дней назад окончился первый раунд ежегодного чемпионата Russian AI Cup. И по его результатам мы сегодня подготовили для вас всевозможную статистику. К моменту начала первого раунда более 1500 участников загрузили в систему свои стратегии. Из них 900 лучших по значению рейтинга в Песочнице сражались за право участвовать во втором раунде чемпионата. Конкурс составлял три человека на место, поэтому адреналина хватило всем.

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

Говорят, когда он появился на свет, к нему заглянул сам Дональд Кнут. Говорят, когда его пригласили работать в Google, он за 15 минут переписал весь поисковый алгоритм 16 раз. Говорят, он с улыбкой следит за прогрессом квантовых вычислений, так как при виде его числа от страха факторизуются сами. Но мы точно знаем одно: Пётр — настоящий бог спортивного программирования.

В минувшие выходные Clojure-сообщество испытывало… Ой, так начинался прошлогодний пост с отчётом о прошедшем ClojureCup 2013.

ClojureCup — это 48-часовой онлайн-хакатон, обязательным условием которого является написание приложений на языках Clojure/ClojureScript. В этом году в хакатоне участвовало около 50 команд (в каждой по 1-4 человека), которые сделали множество классных приложений.

Приложения оценивают как жюри (известные в Clojure-сообществе люди), так и обычные пользователи: зайти с помощью twitter-а и проголосовать за понравившиеся вам приложения можно на странице приложений.

А попробовать, что у нас получилось, можно вот тут.



Осторожно: под катом много картинок.

Преамбула

Меня зовут Руслан и я алкоголик программист. Со «спортивным программированием» я не сталкивался давненько. Последний раз оно мне помогло поступить в университет, который я так и не закончил. Я занимаюсь разработкой игр почти 9 лет подряд. Сначала работать было интересно. Сервер частенько падал и преподносил сюрпризы, а теперь мы научились не деплоить по пятницам мы научились деплоить по пятницам, чтобы ничего не ломалось не падает и почти не преподносит сюрпризов. В общем, когда-то, чтобы не скучать, я занимался маленькими своими проектиками, потом чуть-чуть фрилансил, а в начале этого года меня угораздило вспомнить про олимпиады про программированию и спортивное программирование.

А ещё заголовок не совсем соответствует тексту статьи, но мне он очень понравился. Если кто-то решит почитать статью, чтобы увидеть меня без футболки — не надо этого делать!

О CodinGame

Кодингейм — это онлайн платформа по проведению конкурсов по программированию. Там есть онлайн редактор, автоматизированное тестирование программы, и даже кое-какие призы. Перед началом конкурса (проводится раз в месяц), предлагается отметить галочками интересных работодателей (они в основном французские), вдруг кто из них захочет взять меня к себе на работу. Я работу не ищу, но по итогам несколько компаний просили прислать резюме. Хотя итоги — более чем скромные. Сегодня обнаружил пункт, «участвую For fun». В следующий раз воспользуюсь.

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

Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


Дело в том, что перед выполнением программы интерпретатор Python компилирует все её части в специальный байт-код. Используя метод, описанный хабрапользователем SkidanovAlex, данный декоратор анализирует получившийся байт-код функции и пытается оптимизировать применяющийся там алгоритм. Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически. Так, чем больше будет количество итераций в цикле, тем в большее количество раз ускорится оптимизированная функция по сравнению с исходной.

Эта статья расскажет о том, в каких случаях и каким образом декоратору удаётся делать подобные оптимизации. Также вы сможете сами скачать и протестировать библиотеку cpmoptimize, содержащую данный декоратор.

Истинные программисты, поздравляем вас с 256 днем года!
В честь такого дня готовы отдать тебе или твоему другу один инвайт в подарок от нашего корпоративного блога взамен на решение интересной головоломки. Победителя из числа претендентов, правильно решивших задачу, определит рандом.
Решил принять участие? Подробности — под катом.

Доброго дня и приятного понедельника всем! Сегодня начало не только рабочей недели, но и чемпионата по программированию искусственного интеллекта Russian AI Cup, организатором которого является Mail.Ru Group. Он проходит ежегодно, начиная с 2012 года. В этот раз перед участниками поставлена задача по написанию алгоритма для команды хоккеистов. Принять участие могут все желающие, любых возрастов и квалификаций. Главное — иметь базовые навыки программирования. Список возможных языков программирования ограничен, вы можете выбрать один из следующих вариантов: C++, Java, C#, Python, Ruby или Pascal. Кстати, в прошлом году предпочтения участников распределились таким образом: 36% выбрали C++, 25% — Java, 21% — C#.

Сегодня начала работу песочница Russian AI Cup 2014. В прошлом году наш AI управлял группой бойцов, а в 2012 танком. Видимо организаторы конкурса решили, что военной тематики достаточно — теперь в нашем распоряжении будет команда хоккеистов.
Второй год подряд спонсором является Mail.ru. Пока в их блоге не размещена информация об этом мероприятии, но скорее всего она будет позже. Поэтому цель у этого топика не подробно осветить мероприятие (вся информация есть на сайте), а создать обсуждение в комментариях.

Доброго времени суток, уважаемые хабрачитатели!

Скорее всего, многие из вас слышали про олимпиады по спортивному программированию. В последние годы появилось очень много соревнований по этому виду программирования. Это и Google Code Jam, и Topcoder Open, и Russian Code Cup. Сегодня мне посчастливилось лично пообщаться с Романом Удовиченко (в рамках AYcamp, по специальной программе «Саурон»), одним из тех, кто добился в них серьезных успехов. Он живет в городе Минске, в прошлом году окончил Белорусский Государственный Университет, работает в компании Яндекс. Он рассказал, как готовился к олимпиадам и чем они помогли ему в жизни.

Всех заинтересованных прошу под кат.

1 августа в офисе Яндекса, открывшемся недавно в Берлине, состоялся финал нашего чемпионата по программированию. И его победителем снова стал известный всем, кто интересуется спортивным программированием, Геннадий Короткевич.

Задания для Алгоритма готовила международная команда. В нее вошли программисты из России, Беларуси, Польши и США. Это специалисты МГУ имени М.В. Ломоносова, Университета Карнеги-Меллон, сотрудники Яндекса и Google. В Яндексе задачи составляли разработчики минского и киевского офиса, а потом проверяли их на своих коллегах. Один из составителей в прошлом году сам был финалистом Алгоритма. Специально для Хабрахабра мы разобрали с авторами все задачи. Кстати, несмотря на то, что соревнование завершено, вы можете попробовать себя в вирутальном контесте.



На победу претендовали многие финалисты. Среди них были победители и призеры АСМ ICPC и TopCoder Open, разработчики Google и Facebook. В финальном раунде сражались призёры Алгоритма-2013 Евгений Капун и Ши Бисюнь, чемпион АСМ ICPC Михаил Кевер, а также один из самых титулованных спортивных программистов мира Пётр Митричев. В этом году побороться за приз решил также Макото Соэдзимо — составитель заданий для Алгоритма-2013 и администратор TopCoder Open.

Борьба за первое место разгорелась между Геннадием Короткевичем и Хосакой Кадзухиро из Токийского университета. Лучший результат — четыре задачи при 66 минутах штрафного времени — показал Короткевич, подтвердив титул чемпиона. Кадзухиро решил столько же задач, но набрал больше штрафного времени (90 минут) и занял второе место. Третье место завоевал Ван Циньши из университета Цинхуа: он решил четыре задачи при 125 минутах штрафа.

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

Комбинационные логические схемы входят в состав всех современных процессоров и других электронных средств обработки информации. Процессоры используются повсеместно и непрерывно усложняются. Количество транзисторов в современном процессоре уже превысило 2 млрд^? И, похоже, рост не планирует останавливаться. Одновременно с этим уменьшаются технологически процессы производства процессоров. Транзисторы становятся все меньше и уязвимее для внешних воздействий. И вот, даже не самые сильные внешние излучения и магнитные поля могут приводить к кратковременным изменениям логических значений в микроэлектронных схемах. Эта проблема особенно актуальна в космических и других критичных к надежности системах. В данной задаче поставим вопрос: как зная логическое назначение схемы сделать её более устойчивой к внешним воздействиям? Вашей задачей будет разработать алгоритм создания такой устойчивой схемы.

Прошлый год я писал статью про ICFPC 2013. Пришло время про ICFPC 2014.

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

В этом году мероприятие пройдет c 25 июля, 12:00 UTC до 28 июля 12:00 UTC. Организаторы олимпиады каждый год различны, в этом году ее организует Оксфордский Университет, и задания будут здесь.

Для абитуриентов МФТИ проводится школа по прикладным математике и физике (подробнее о ней можно прочитать на официальном сайте). 8 июля там будет очная олимпиада по математике и физике, а вот по информатике олимпиада заочная и проводится на http://judge.mipt.ru. Олимпиада проводится по кировской системе на Ejudge. Результаты этой олимпиады будут учтены на собеседовании в МФТИ и при распределении первокурсников по группам по информатике. Победители получат призы от спонсоров – базовых организаций ФУПМ и ФРТК МФТИ — компаний Parallels и Acronis.

Проснувшись однажды утром… (нет). Проснувшись как-то вечером… (нет!). Короче, проснувшись однажды на работе солнечным утром (вот уже провокационно звучит), и протерев глаза от производственной рутины, подумал я о том, что команда наша — конечно великолепная, но технологически несколько узковата… “И надо бы покодить на чем нибудь другом!” — блеснул я оригинальной мыслью. И вот мы сделали собственный хакатон, который заточили не по тематике, а по технологии. Получилось, сразу скажу… неплохо.

Трое студентов Санкт-Петербургского государственного университета стали победителями 38-ого Студенческого Чемпионата Мира по Программированию Ассоциации Вычислительной Техники (ACM-ICPC), глобальным спонсором которого выступает компания IBM. Самое престижное соревнование для программистов со штаб-квартирой в Университете Бэйлора (Baylor University), также известное как «Битва интеллектов» (Battle of the Brains), объединило 122 студенческие команды, которые всего за пять часов должны были справиться с несколькими сложнейшими задачами из реальной жизни.

Сегодня началась регистрация на второй Russian Developers Cup, чемпионат разработчиков мобильных и веб-сервисов, а также игр. Записаться на участие можно будет до 22 июля.

UPD3: Запись трансляции можно посмотреть вот здесь: www.icpc2014.ru/ru/competition/video; а церемонию закрытия вот здесь: www.youtube.com/watch?v=9VzLRDkO3ZU
UPD2: И победителем становится команда Санкт-Петербургского государственного университета (Кунявский, Егоров, Суворов). Наши поздравления! :)
UPD: Чемпионат начался, и трансляция уже идёт! www.icpc2014.ru/ru

Завтра, 25го июня 2014го года в 08:00 мск в Екатеринбурге стартует Чемпионат мира по спортивному программированию (aka ACM ICPC World Finals). Прямую трансляцию можно будет смотреть вот здесь: www.icpc2014.ru/ru.
А этот пост будет посвящён тому, как мы превращали далеко не самое зрелищное мероприятие (с точки зрения непосвящённых!) в классную видео трансляцию.

В рамках международного форума Positive Hack Days IV, прошедшего в Москве 21 и 22 мая, по традиции состоялось хакерское соревнование Capture The Flag. На протяжении двух дней 10 команд из 6 стран мира взламывали сети соперников и отбивали их атаки.

Традиционно инфраструктура и задания Positive Hack Days CTF разрабатываются согласно общей легенде, которая является настоящей изюминкой соревнований. Во время прошлогоднего CTF участники перевоплотились в спасителей сказочного мира D’Errorim, которому угрожала гибель. Справившись с заданием, они осознали, что сражались не на той стороне, и теперь опасность грозит их собственному дому. Таким образом сюжетная линия объединяет PHDays III CTF, через отборочные соревнования CTF Quals, с финальной битвой во время PHDays IV.

Полный текст легенды соревнований — на сайте форума.

В прошедшее воскресенье состоялся отборочный раунд Russian Code Cup 2014. В нем участвовало 802 программиста, показавшие лучшие результаты в четырех квалификациях. В этом этапе участникам предстояло за 3 часа решить шесть задач, что на один час и на одну задачу больше, чем в квалификационных раундах. Да и задачи были существенно сложнее, чем предыдущие. За время соревнования из 802-х только 444 участника смогли решить хотя бы одну задачу. Всего было отправлено 3271 решения, из них правильных 1402.