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

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

Привет. С вами олимпиадное хобби. Здесь мы выбираем себе олимпиадную задачу по программированию, разбираем ее, вырабатываем возможные пути решения и реализовываем задуманное, после чего отправляем на суд. Нам потребуется знание одного из языков программирования: c, c++, java, pascal, терпение, ловкость и базовые знания английского языка, чтобы понимать условие задачи, хотя последний пункт необязателен, ведь я вольно перескажу условие на русском языке.

Вы не забыли размяться? Если забыли, то быстренько разминайтесь, и возвращайтесь к нам.

Напоминаю, что я беру задачи с сайта http://uva.onlinejudge.org, и сегодня случайный выбор пал на задачку под номером 154 — задачу об утилизации отходов.

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

Я решил, что неплохо было бы поделиться с Вами алгоритмами, размышления, результатами, а также получить качественную критику моих путей решения задач.
Будем брать задачу, разбирать ее по частям, анализировать, выдумывать различные пути решения, выбирать лучший, а потом нести на суд «великих судей». Для многих, по моему мнению, такой час разгрузки будет очень полезным, а кому-то просто будет интересно посоревноваться и придумать свой алгоритм.

Задачи я буду брать с сайта http://uva.onlinejudge.org/, где располагается достаточно большая коллекция задач на любой вкус, и там же можно проверить свое решение. Выбирать буду случайным образом и всегда доводить начатое до финального решения, которое ознаменуется оценкой «Accepted» (Принято). Для решения этих задач нам потребуется знание одного из языков программирования: c, c++, java, pascal, а также терпение, логика и базовое знание английского языка, т.к. условия задач мы получаем на английском языке.

Итак, начнем мы с простой задачки из набора «Для новичков» для разминки, чтобы проверить свои способности.

Здравствуй, хабрачитатель.

С недавних пор мне нравится проводить конкурсы для программистов-математиков, но эти конкурсы несколько отличаются от олимпиад по программированию, хотя бы тем, что я предлагаю задачи, не имеющие эффективного алгоритма решения. Кроме того, предлагаются задачи, которые либо вообще никто раньше не решал, либо решали очень мало, но серьёзных успехов не добились. Последняя особенность этих задач в том, что они так или иначе связаны с перечислительной комбинаторикой, той областью математики, которая в России была похоронена вместе с другими полезными областями науки «сами знаете когда». Но это менее важно.

Доброго времени суток, хабрачитатель!
Пару часов назад я сошел с поезда Саратов-Волгоград, и, немного придя в себя, решил написать небольшой отчет о прошедшем 19-23 октября в славном городе Саратов четвертьфинале ACM ICPC 2010-2011 года.

Главный турнир года на TopCoder (хабраанонс) закончился уже неделю назад, а на Хабре это важнейшее событие до сих пор не освещено! Это странно и удивительно, и я, верный адепт TopCoder, спешу исправить это недоразумение — тем более что в этом году я имела возможность наблюдать финалы вживую.

Algorithm

Самое зрелищное и эмоционально насыщенное соревнование турнира и в этом году не обмануло ожидания зрителей. Многократный чемпион прошлых лет Петр Митричев (Petr) удивил и немножко шокировал своих поклонников, выбыв из соревнования в первом же полуфинале со всего лишь одной решенной задачей. Второй фаворит, TianCheng Lou (более известный как ACRush), уверенно выиграл свой полуфинал и лидировал весь финал до самых системных тестов, которых не выдержала его третья задача, отбросив его на второе место под слитное «аах» зрителей.

Как многие уже знают, недавно началось Google AI Challenge — соревнование по созданию ботов для игры Planet Wars, проводимое университетом Ватерлоо и поддерживаемое Google. Вчера подошла к концу уже вторая (из девяти) неделя с момента официального старта. Соревнование всё больше начинает напоминать гонку вооружений, и если в начале для попадания в топ 50 было достаточно бота, который в большинстве случаев просто обыгрывал примеры из стартового набора, то теперь прийдётся постараться. О том как это можно сделать, а также о новостях турнира под катом.

Лучшие программисты по версии Google в 2010 году

Сайт AskDev.ru проводит конкурс по спортивному программированию с призами в стиле code golf (побеждает самая короткая по длине программа).

Конкурсное задание: написать программу для игры «в города».

На вход подается массив вида

[Калининград, Вологда, Алматы, Дмитров, Архангельск, Тобольск, Краков]

На выходе.

[Архангельск, Краков, Вологда, Алматы, Тобольск, Калининград, Дмитров]

Прошу учесть во внимание что города на букву Ы в данном списке нет, поэтому далее поиск идет по предыдущей букве.

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

Хочу предложить вашему вниманию автоматически генерируемый, по вашему вкусу настраиваемый, куда угодно импортируемый календарь событий TopCoder:
topcoder-calendar.appspot.com



Просто выберите категории соревнований, которые интересны лично вам, и добавьте получившийся календарь в формате iCal в ваш гугл-календарь, Яндекс.Календарь или любую программу-органайзер.

Доброго времени суток!
Сегодня я хотел бы рассказать о методе разрешения некоторых рекуррентностей и разобрать классический пример на эту тему.

Доброго времени суток!
Данная статья будет полезна для прикладных программистов или людей, увлекающихся спортивным программированием. Она расскажет о быстром вводе данных на языке Java.

Здравствуйте!
Сегодня я хочу разобрать еще одну классическую задачу на комбинаторные игры — мизерный ним. Всем известно что в теории игр ним с нормальным окончанием занимает центральное место, так как к нему сводятся все комбинаторные игры с нормальным окончанием. Посмотрим как обстоят дела с модификацией привычного нима.

Привет, %usename%!
В этой статье я хочу немного рассказать про комбинаторные игры и разобрать решение одной из них.

В этом году в рамках открытого кубка ВолГУ по программированию пройдет Code Game Challenge.
Он создан студентами Волгоградского Политеха, у них уже есть опыт создания CGC, можете убедиться здесь habrahabr.ru/blogs/sport_programming/71355, тут есть два ролика про их прошлые проекты, здесь же можно почитать что такое CGC, для тех кто не знает.

В этом году мы решили пригласить всех желающих принять участие в нем онлайн. Таким образом, любой желающий поучаствовать в нашем CGC, должен будет прислать мне до воскресенья в личку сообщение, с именем команды, списком участников и желаемым паролем.
Сам CGC состоится 18-го апреля, воскресенье, с 11.00 до 16.00.
Ссылка на документацию по CGC будет доступна здесь в субботу с 15.00, для ознакомления.

Итак, что за CGC будет в этом году?

На этой неделе начался 2010 TopCoder Open — главное событие года на TopCoder. Турнир состоит из 6 категорий, в которые сгруппированы все виды соревнований, обычные для TopCoder. Соревнования онлайн для 4 категорий из 6 уже начались и закончатся в начале августа, финалы пройдут 11-14 октября в Лас-Вегасе. В призы входят 100 поездок в Лас-Вегас (в зависимости от категории соревнований — либо для участия в финале, либо просто как наблюдатель), $150,000 (увы, только для присутствующих в Лас-Вегасе) и 650 футболок (приз демократичный, но приятный).



Кстати, патрон TCO — NSA, а вот спонсор новый, Яндекс. Как обычно, спонсоры имеют с этого не только паблисити, но и шкурный интерес — они ищут новых сотрудников из числа лучших программистов мира: «Just let us know you exist».

В субботу 20 марта прошел финальный раунд турнира для школьников TCHS 2010. Результаты (приведены первые 6 мест — участники, решившие все три задачи):
1. tourist — Геннадий Короткевич, Беларусь (известный хабрахабру по победе на IOI-2009)
2. exod40 — Болгария
3. neal_wu — США
4. lyrically — Япония
5. rng_58 — Япония
6. meret — Польша

Интересна статистика распределения 100 участников финала по странам: уверенно лидирует Китай (19 участников), второе и третье места делят Польша и Россия (11), Болгария (9), Хорватия (6) и Япония (5) завершают Топ-6 стран с 5 и более участниками. От Украины, традиционно сильно выступающей в студенческих соревнованиях, в финал прошли всего два человека, а участвовал и вовсе всего один. Такой слабый интерес к этому замечательному турниру не может не огорчать (особенно меня, его ярого проповедника, автора второго раунда и апологета ТопКодера в целом).

В субботу 27 февраля пройдет первый из четырех раундов TCHS 2010 — турнира по спортивному программированию для школьников 13-20 лет. Каждый раунд проводится по стандартным правилам TopCoder — 3 задачи на 75 минут + 15 минут на поиск ошибок в чужих решениях.



Узнать больше о турнире можно здесь, зарегистрироваться — здесь (регистрация заканчивается за 24 часа до начала первого раунда).

Многие знают, что такое Perl-гольф. Это своеобразная игра, заключающаяся в написании самого краткого кода на Perl, решающего поставленную задачу.
Исторически так сложилось, что гольф закрепился только среди пишущих на Perl. Но, вспомните, сколько раз Вы говорили о коде: «А вот так было бы короче» или «А вот эдак было бы изящнее».
Да, конечно, на других языках это не так гибко и «загадочно», но это тоже интересно, а в случаях с Ruby и Python и очень кратко. По-крайней мере, мы с коллегами после гольфа на Perl не менее интересно посоревновались на этих же задачках и на C, C++ и Ruby.
А как Вы относитесь к гольфу на других языках?

PS. На acm.mipt.ru есть топ по самому краткому коду, но, увы, без разделения на языки.

Пост по мотивам прошедшего в пятницу финала ACM ICPC 2010, о том, как в буквальном смысле слова «на коленке» поднять зеркало умирающей под нагрузкой странички, прикрутить к нему чат с ее обсуждением, и не загнуться от нагрузки самому :)

Пост будет интересен скорее веб-программистам, нежели олимпиадникам.

Немного статистики, конфигов nginx, полезные трюки, а также ряд граблей, которые должны быть прекрасно известны людям с опытом, но на которые многие все равно часто наступают…