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

Довольно часто в спортивном программировании или же просто реализации алгоритмов необходимо отсортировать массив входных данных по определённому критерию. В то время как в ответе требуется исходный порядок. В статье я рассмотрю несколько способов сделать это минимальной кровью на C++. Если интересна эта тематика или имеются интересные предложения, прошу под кат…


Автор изображения: Tobias Rad, лицензия Creative Commons Attribution-Share Alike 3.0 Unported

Вступление

Людям, которые увлекаются спортивным программированием, хорошо известны соревнования корпорации TopCoder. Среди них, пожалуй, самым популярным видом является Single Round Match, или SRM. Схема SRM'ов достаточно специфическая, и в чем-то неповторимая. Если кратко — сначала участники решают 3 задачи разных уровней сложности, потом некоторое время ищут ошибки у оппонентов, получая за это дополнительные очки.

Для организации таких соревнований TopCoder создали Java-апплет (TopCoder Arena). Также нашлись умельцы, которые для этой самой арены написали плагины, чтобы упростить жизнь себе и другим. Но установка последних часто вызывает трудности у начинающих SRM'щиков. Именно эта проблема стала мотивом для написания этой статьи.

Вчера вечером прошел третий и последний отборочный раунд ежегодного турнира по спортивному программированию Google Code Jam.
Top-25 участников прошли в финал, который будет проходить 29 июля в Токио. В него вошли представители следующих стран:

• 10 участников из России:
  • vepifanov (Владислав Епифанов)
  • ilyaraz (Илья Разенштейн)
  • Egor (Егор Куликов)
  • ashmelev(Алексей Шмелев)
  • ilyakor (Илья Корнаков)
  • bsod (Евгений Капун)
  • darnley (Михаил Дворкин)
  • natalia (Наталья Бондаренко)
  • andrewzta (Андрей Станкевич)
  • winger (Владислав Исенбаев)
• 5 участников из Китая: Bin.Jin, g201513, hanshuai, acrush, zyz915
• 3 участника из Японии: ir5, omeometo, rng..58
• По одному участнику из
  • США: neal.wu
  • Индонезии: Dolph
  • Польши: meret
  • Беларуси: mystic (Иван Метельский)
  • Словакии: misof
  • Грузии: nika
  • Великобритании: linguo

Официальные результаты

«В наше время считается общепризнанным,
что из всего, так или иначе касающегося искусства,
ничто более не может считаться общепризнаным»
Теодор Адорно

Все началось с того, как один человек пытался выяснить решение задачи контеста, который проходил в данный момент. Задача была очень простая, всем было очевидно, что этот человек не займет хорошего места, не получит футболку и т.п. Но тем не менее ни один из 5000+ членов сообщества не дал ни одной подсказки (ну или хотя бы из 30+ человек, которые это видели и знали ответ). Мне такой результат уже давно кажется закономерным и я попробовал объяснить его в двух словах. Теперь попробую чуть более подробно. Заранее прошу прощения у людей, которые в это понятие вкладывают не то, что я. Я лишь хотел изложить свой взгляд.

С 06.08.2011 по 17.08.2011 в Севастополе на базе Севастопольского Национального университета ядерной энергии и промышленности пройдет II-я Международная летняя школа программирования. Планируется 7 рабочих и 3 организационных дня. В каждый из рабочих дней проводится лекция, пятичасовой контест, разбор задач. Вечером море :). Важная информация: практические туры проводятся на личных ноутбуках участников. Более подробная информация на официальном сайте школы http://issps.org.ua. Регистрация открывается с 6-го июня 2011 года. Контактный телефон +38-068-926-15-61. Контактный e-mail: keem.mss@gmail.com

Медали получили следующие команды:

1. Университет Чжэцзян, Китай (8 задач)
2. Мичиганский университет, США (8 задач)
3. Университет Цинхуа, Китай (7 задач)
4. Санкт-Петербургский государственный университет, Россия (7 задач)
5. Нижегородский государственный университет, Россия (7 задач)
6. Саратовский государственный университет, Россия (7 задач)
7. Университет Эрлангена-Нюрнберга, Германия (7 задач)
8. Донецкий национальный университет, Украина (7 задач)
9. Ягеллонский университет, Польша (7 задач)
10. Московский государственный университет, Россия (7 задач)
11. Уральский государственный университет, Россия (7 задач)
12. Университет Ватерлоо, Канада (7 задач)

Все результаты можно увидеть здесь.

Здесь пойдет речь немного не о том спортивном программировании, к которому многие привыкли. Недавно,
на Codeforces был проведен экспериментальный раунд Unknown Language Round #1.
На нем участникам было предложено решить несколько несложных задач (первая,
вторая, а вот и все
остальные). Особенность раунда — задачи можно решать только на одном языке программирования, который
не известен участникам до начала раунда. Было анонсировано, что язык не является
mainstream языком. Иначе говоря, участникам предлагалось за 2.5 часа соревнования на скорость разобраться
в незнакомом языке и решить задачи на нем.

Здравствуйте, Хабрахабр. В этом после я хочу рассказать о динамическом программировании на примере решения одной из задач. С этой задачей я недавно столкнулся на портале олимпиадных задач (ссылка указана в конце). Сразу перейду к делу.

Задача

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·10⁹.

Технические условия

Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.

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

_{«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.}
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.

Чемпионат мира по программированию ACM ICPC (среди студенческих команд) 2011 должен был состояться в конце февраля — начале марта в Шарм-эль-Шейхе, Египет.

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

Здравствуй, Хабрадруг.

Предлагаю принять участие в конкурсе по решению целочисленных СЛУ на скорость. Сразу хочу предупредить, что конкурс любительский и призов не предвидится, поэтому приглашают тех, кому такое соревнование покажется интересным и тем, у кого есть для этого свободное время. Конкурс может оказаться полезным с той точки зрения, что мало кто умеет решать такого рода задачи достаточно эффективно.

Всё больше и больше крупных IT компаний начали проводить контесты по программированию с целью набрать себе новых сотрудников — IBM, Microsoft, Google, Facebook, Yandex,… Недавно к их числу добавилась и компания eBay.

Компания eBay совместно с yodacode проводит контест, длительностью в месяц, с целью поиска новых талантов.

Доброго всем понедельника. Если понедельник для вас не самый приятный день, то предлагаю вам немного расслабиться и проникнуться моим хобби. Моё хобби — решение олимпиадных задач по программированию: встряхивает мозг, будоражит воображение и заряжает энергией (правда не всегда положительной). Не верите? Попробуйте сами, только честно попытайтесь решить поставленную задачу, получите долгожданный Accepted, и наслаждайтесь полученными эмоциями.

Сегодня случай подкинул нам задачу №10474. Это задача на умение применять вовремя простые алгоритмы, поэтому не ждите от нее чего-то сложного и хитроумного. Если вам не интересно решать задачи за счет пары стандартных алгоритмов, то пропускайте топик, а всем остальным добро пожаловать под кат. Нас ждет пара алгоритмов, выбор наиболее удобного решения, ну и, конечно же, Accepted!

Facebook объявил о проведении первого кубка Hacker Cup 2011, который станет «ежегодным конкурсом для хакеров со всего мира по алгоритмическому программированию».

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

Марк Цукерберг в недавнем интервью для “60 Minutes” объяснял, что «хакер» — это лучший комплимент для программиста. По его словам, хакнуть — значит, разработать что-то очень быстро.

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта 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 было достаточно бота, который в большинстве случаев просто обыгрывал примеры из стартового набора, то теперь прийдётся постараться. О том как это можно сделать, а также о новостях турнира под катом.