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

Через три недели, 6—7 декабря, «облачный localhost» Koding проводит онлайн-хакатон, участвовать в котором можно из любой точки земного шара. Организаторы настаивают, что это первый в мире хакатон в таком формате, но верится как-то слабо.

Новый Год уже не за горами, а какой же Новый Год — без новогодних конкурсов с подарками? Мы в проекте KolibriOS решили не отходить от традиции, и провести наш собственный конкурс, с денежными призами.

Поскольку находимся мы на Хабре, простой случайный розыгрыш призов вроде конкурса от Mail.Ru мы считаем здесь неуместным, и призы нужно будет заработать. Поскольку KolibriOS — хобби-проект, конкурс будет связан с развлечениями. Ну, а поскольку мы не такие богатые, как Mail.Ru, то и призы будут поменьше :-)

Задачей конкурса является написание своей собственной игры для Колибри. Сделать это нужно до наступления Нового 2015-го года по московскому времени, т.е. до 31 декабря 2014г. 24:00 MSK.

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

Для игры можно использовать любой язык программирования — хоть FASM (предпочтительно), хоть JAVA, хоть Brainfuck. Однако, если компилятор выбранного вами языка в данный момент отсутствует под Колибри, вам придётся сначала научить этот компилятор собирать программы под Колибри. Поэтому мы рекомендуем выбрать такой язык, для которого уже есть компилятор (для Brainfuck, кстати, есть).

Исходный код игры (включая все «ресурсы» — картинки, спрайты, звуки, музыку, если таковые имеются) должен быть выложен на SVN проекта под одной из утверждённых open-source лицензий. Игра должна компилироваться из исходников с помощью системы авто-сборки Tup на сервере КолибриОС. Для облегчения добавления игры в авто-сборку (а также принимая во внимание предыдущий параграф), лучше всего писать игру на языке, для которого уже есть пример авто-сборки (FASM, NASM, C--, GCC, MSVC). Но мы же не ищем лёгких путей, правда?

Игры всех участников, успешно выполнивших задание, будут выставлены на голосование на Хабре в январе 2015 г. По результатам голосования, будут присуждены призы:

• 1 место — $1,000 США
• 2 место — $500 США
• 3 место — $250 США

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

Под звуки фанфар мы торжественно объявляем о завершении ежегодного чемпионата Russian AI Cup за 2014 год. Последние полтора месяца были очень трудными и напряжёнными как для участников, так и для организаторов мероприятия. Однако мы всё же надеемся, что вы не только получили массу удовольствия и хороших впечатлений, но и улучшили свои навыки программирования, научились чему-то новому.

4 октября прошел финальный раунд крупнейшей в России ежегодной олимпиады по спортивному программированию Russian Code Cup. Победителем Russian Code Cup 2014 и обладателем главного приза — $10000 — стал Геннадий Короткевич. Второе место занял Петр Митричев — он получил $5000. Третьим финишировал Егор Куликов, его денежный приз составил $3000. Также в этом году впервые были награждены все участники, вошедшие в первую десятку: обладатели 4-10 мест получили по $1000.

Вчера начался новый контест от 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.

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