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

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

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

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

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

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

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

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

На выходе.

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

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

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

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



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

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

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