540A - Кодовый замок

Для каждого символа посчитаем, в какую сторону выгоднее вращать диск. Это можно сделать либо формулой: min(abs(a[i] - b[i]), 10 - abs(a[i] - b[i])), либо даже двумя циклами for: в прямом или обратном направлении.

540B - Школьные оценки

Посчитаем количество оценок, меньших y. Если таких больше штук, то мы не сможем удовлетворить второму условию (про медиану), и ответ -1. Иначе получим ровно столько оценок y, чтобы количество оценок, больших или равных y, было как минимум штук (возможно, это уже выполняется). Это минимальное необходимое действие для удовлетворения второго условия.

Теперь, чтобы не нарушить первое условие, сделаем оставшиеся неизвестные оценки как можно меньше — единицами, и проверим сумму. Если она больше x, то ответ снова -1, иначе требуемые оценки найдены.

540C - Ледяная пещера

Я выделил здесь три случая, хотя некоторые из них можно объединить.

1. Если начальная и конечная клетка совпадают, посмотрим на количество целых соседей этой клетки. Если есть хотя бы один целый сосед, то пойдем туда и сразу же вернемся обратно, выполнив задачу — в этом случае ответ YES.
2. Если начальная и конечная клетка являются соседями, то посмотрим на тип конечной клетки. Если конечная клетка треснувшая, то ответ YES. Иначе для положительного ответа необходимо, чтобы у нее был хотя бы один целый сосед — пойдем на конечную клетку, затем на этого целого соседа, а потом вернемся обратно.
3. В наиболее общем случае проверим, существует ли путь по целым клеткам от начальной клетки до конечной. Если нет, то ответ NO. Иначе посмотрим на тип конечной клетки. Если она целая, то для существования ответа необходимо наличие у нее двух целых соседей — по одному мы придем в нее, а второй используем как промежуточную точку, а если конечная клетка треснувшая, то у нее должен существовать один целый сосед.

540D - Остров невезения (мой код: http://pastebin.com/3s6dRK3A)

Будем считать величину dp[r][s][p] — вероятность возникновения ситуации, когда в живых осталось r камней, s ножниц и p бумаг — для всех возможных значений r, s, p. Начальная вероятность равна 1, а для подсчета остальных необходимо сделать переходы.

Пусть у нас имеется r камней, s ножниц и p бумаг. Найдем для примера вероятность того, что в этой ситуации камень убьет ножницы — остальные две вероятности считаются симметрично. Количество случаев, в которых кто-нибудь умрет, равно rs + rp + sp, а количество случаев, в которых умрут ножницы, равно rs. Так как все случаи равновероятны, нужная нам вероятность равна . Именно с этой вероятностью мы перейдем в состояние dp[r][s — 1][p], где ножниц станет на 1 меньше.

В конце, чтобы получить вероятность, что, например, камень выживет, надо просуммировать все величины dp[i][0][0] для i от 1 до r (аналогично для остальных видов).

540E - Бесконечные инверсии (мой код: http://pastebin.com/QFEMRbNP)

Запомним, на какой позиции какое число будет стоять после выполнения всех swap-ов. Теперь будем считать ответ. Ответ состоит из двух частей. Первая часть — это инверсии, образованные исключительно теми элементами, которые поучаствовали в swap-ах. Их можно посчитать одним из двух стандартных способов: mergesort-ом или с помощью сжатия координат и дерева Фенвика. Вторая часть — это инверсии, в которых один из элементов пары участвовал в swap-ах, а второй — нет. Для простоты рассмотрим тест:

2
2 6
4 8

Перестановка будет выглядеть так: [1 6 3 8 5 2 7 4 9 ...], а массив swap-нутых элементов так: [6 8 2 4].

Давайте поймем, с какими элементами будет образовывать инверсии число 8. Очевидно, такими элементами могут быть лишь те элементы, которые находятся между начальной позицией числа 8 (где сейчас число 4), и текущей его позицией. Вот этот подотрезок: [5 2 7]. Чисел на этом подотрезке, которые не участвовали в swap-ах, две штуки: 5 и 7. Число 2 учитывать не надо — ведь оно участвовало в swap-ах, и мы его посчитали на первом шаге решения.

Таким образом, надо взять количество чисел между начальной и конечной позицией числа 8 в глобальной перестановке (т.е. 8 - 4 - 1 = 3), и вычесть из него количество чисел между позициями числа 8 в массиве swap-ов (т.е. 4 - 2 - 1 = 1). Чтобы избавиться от дополнительного вычитания единицы, можно просто из правого индекса вычитать левый. Так мы получим количество инверсий, образованные элементом 8 и элементами глобальной перестановки, не участвовавших в swap-ах. Для завершения второго шага надо лишь посчитать эту величину для всех чисел, участвовавших в swap-ах. Все операции второго шага можно выполнить при помощи сортировок и бинарного поиска.

Всем привет!

Мне выпала честь открыть четвертую сотню раундов на Codeforces. К сожалению, мы с друзьями пока что не смогли придумать сложных задач, так это всего лишь Div. 2 раунд. Но мы обязательно сделаем общий раунд когда-нибудь в будущем! Как всегда, благодарю Zlobober за помощь в подготовке задач, Delinur за перевод и MikeMirzayanov за сам Codeforces.

Для участников из первого дивизиона задачи должны быть совсем простыми, поэтому давайте поставим челлендж: красные должны все решить за 30 минут, желтые — за час, а фиолетовые — за полтора часа. Интересно, как много народу сможет управиться?

Разбалловка будет стандартная. Всем полных решений и успешных взломов!

UPD 1. Поздравляю победителей в официальном зачете:

1. PauGra
2. cuvwqe496
3. tgehr

и в неофициальном:

1. niyaznigmatul
2. I_love_Tanya_Romanova
3. dreamoon_love_AA

UPD 2. Разбор лежит тут: /blog/entry/17643.

Доброго времени суток, дорогие друзья.

В этом посте я расскажу об одной из негативных сторон языка Java на соревнованиях по программированию (да и вообще), а точнее, как я попытался ее решить. Как известно, язык Java страдает недостатком при работе с коллекциями: ограничения этого языка заставляют программиста использовать объектные типы данных даже там, где этого как бы и не требуется. Сравните ArrayList<Integer> и vector<int>: в Java-варианте лист хранит объекты типа Integer, которые создаются при каждом добавлении элемента в список и распаковываются при каждом обращении, тогда как C++-ный вектор хранит обычные честные int-ы. Это замедляет работу программ на Java и много кому не нравится.

Вся фигня в том, что нельзя просто так взять и написать примитивный тип внутри угловых скобок. Ну не спроектировали так Java, бывает. Несколько месяцев назад я подумал: а почему бы не обойти эту проблему? Ведь можно просто написать собственные коллекции, и дело в шляпе. Тем более что ни одного подобного проекта, где действительно были бы реализованы все коллекции, я в интернете не нашел.

Так родился маленький проект под названием EZ Collections (ссылка на репозиторий на Github). Я, разумеется, не писал все возможные коллекции для всех возможных типов данных. Достаточно было написать каждую коллекцию один раз, оставив в исходнике некоторые подсказки для Maven-плагина, который потом сгенерирует все как надо.

Замечу, что библиотека предполагается для использования именно на олимпиадах, ну или просто для личного пользования. Она абсолютно вся thread-unsafe, там нет некоторых валидаций, во время итерирования нельзя менять коллекцию, нет сериализации и, наверное, чего-то еще нет. Но задачки сдаются.

Чтобы начать использовать эту библиотеку, вам необходимо:

1. Установить Git и выкачать себе репозиторий с помощью команды git clone (на главной странице проекта написан URL). Либо просто скачать его, нажав кнопку Download ZIP.

2. Скачать Maven (ссылка на страницу загрузок), установить и настроить его (кто не умеет — Google в помощь, но вроде бы достаточно прописать путь к Maven в системных переменных).

3. Зайти в корневую директорию библиотеки и выполнить команду mvn clean install. После этого в вашем локальном Maven-репозитории, а также в папке target появятся два jar-файла: один с class-файлами, другой с исходниками. Теперь вы можете подключать эти jar-ники к своему проекту.

По прежнему, правда, непонятно, как применять это на олимпиадах. Придется вспомнить про плагин Egor-а CHelper для IntelliJ IDEA. После его переезда на Github наконец-то был замержен пулл-реквест, исправляющий некоторые проблемы. Собранную последнюю версию (коммит 29dc20b), включающую в себя этот пулл-реквест, можно скачать отсюда и подключить самостоятельно.

После обновления плагина достаточно добавить библиотеку в ваш олимпиадный проект, указав путь к jar-файлу с исходниками. И можно пользоваться!

Пример использования: решаем задачу 118E - Дороги в Бертауне

• используем List<Integer>[] для хранения графа: 8293080 — 1060 мс, 39100 КБ
• используем EzIntList[] для хранения графа: 8293086 — 654 мс, 12148 КБ

(в этой задаче достаточно большие входные данные, чем они больше — тем более заметен будет выигрыш в производительности)

Еще один пример: решаем задачу Timus 1521

С помощью TreeList все пишется буквально в несколько строчек:

int n = in.readInt();
int k = in.readInt();
EzIntList a = new EzIntTreeList(n);
for (int i = 0; i < n; i++) {
    a.add(i);
}
int idx = 0;
for (int i = 0; i < n; i++) {
    idx = (idx + k - 1) % a.size();
    out.print(a.removeAt(idx) + 1);
    out.print(' ');
}

Что же сейчас есть в EZ Collections? На данный момент присутствуют:

• ArrayList
• ArrayDeque (с возможностью обращения по индексу)
• Heap
• Sort (гарантированная за NlogN)
• HashSet
• HashMap (я использовал открытую адресацию. Не уверен, ломается ли моя реализация, но кажется, что не должна)
• TreeSet
• TreeMap
• TreeList (массив, умеющий делать add, set, insert и removeAt за логарифмическое время)
• классы Pair

Также хочется отметить, что существует известная библиотека Trove (ее репозиторий располагается тут), и, возможно, многие используют ее на работе, но проблема в том, что они сделали лишь ArrayList, HashSet и HashMap. А для олимпиад этого явно не хватает.

Некоторые замечания и планы:

• Не поддерживаются NaN, POSITIVE_INFITITY и подобная ерунда. И никогда не будут поддерживаться. Вы сам себе знаете кто, если используете такое.

• В связи с невозможностью возвращения null (ведь в коллекциях хранятся примитивные типы) везде, где это необходимо, добавлен метод returnedNull(), который следует вызвать сразу же. Следующие два использования идентичны:

    TreeSet<Integer> set = new TreeSet<Integer>();
    Integer lower = set.lower(42);
    if (lower == null) {
        ...
    }

    EzIntTreeSet set = new EzIntTreeSet();
    int lower = set.lower(42);
    if (set.returnedNull()) {
        // не используйте значение lower, никто не гарантирует, что будет возвращено
    }

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

• boolean считается несравнимым типом, поэтому Pair с boolean-ами не реализует Comparable. После переписывания генерации это должно пофикситься.

• В будущем планируется добавить LinkedList (на массивах). Но это только после того, как перепишу генерацию исходников.

• А потом планируется добавить мапы, у которых ключ — примитивный тип, а значение — объект, или наоборот. Тоже должно дать прирост в скорости.

Пишите ваши замечания и фидбеки мне в личку на Codeforces.

История версий:

• 21.02.2015 — выпущена версия 0.1.0. По содержанию она идентична стандартным коллекциям Java.
• 15.03.2015 — выпущена версия 0.1.1. Добавлен TreeList, а также добавлена возможность задавать собственные хеш-функции для HashSet/HashMap.

Не так давно в нашем вузе был проведен очередной отборочный контест на четвертьфинал ACM ICPC, по результатам которого мы отобрали команды, которые поедут в Саратов этой осенью. Тренировка по задачам этого контеста состоится в воскресенье, 21 сентября, в 11.00.

Ссылка на контест: 2014, Отборочный контест СГАУ на четвертьфинал ACM ICPC

Список предыдущих наших контестов:

• 2012, V Самарская областная межвузовская олимпиада по программированию
• 2012, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2013, VI Самарская областная межвузовская олимпиада по программированию
• 2013, Отборочный контест СГАУ на четвертьфинал ACM ICPC
• 2014, VII Самарская областная межвузовская олимпиада по программированию

Есть разбор задач на русском языке: https://www.youtube.com/watch?v=yLwyPXNEpYM Сразу извиняюсь за то, что я фигово разбираю задачи (мои были A, B, H, J), больше такого не повторится, т.к. я заставлю все задачи разбирать craus-а — он это делает наиболее круто.

Добрый вечер. Столкнулся с задачей, никак не могу решить. Выдает Wrong Answer на 2 тесте. Перепроверил код уже тысячу раз, не знаю, где ошибка.

Вкратце условие: надо поддерживать множество чисел и выводить его размер после каждой операции.
В первой строке задано число n (1 ≤ n ≤ 100000) — количество операций. В n следующих строках заданы операция (add или remove) и число (от  - 10⁹ до 10⁹), через пробел. Если операция — add, надо добавить число в множество, если remove — удалить его оттуда.

Код: http://paste.ubuntu.com/7857687/

На всякий случай, ссылка на анонс и обсуждение.

А теперь разбор.

A div 2: 378A - Игра с кубиком

Заведем три счетчика: для побед каждого из игроков и для ничьи. Переберем все варианты, как можно выбросить кубик — их всего 6 штук. Для каждого варианта определим, кто выиграет, или будет ли ничья, и прибавим единицу к соответствующему счетчику.

B div 2: 378B - Полуфиналы

Можно немного подумать и понять, что достаточно рассмотреть крайние случаи k = 0 и . Все остальные случаи будут средними между этими двумя.

В случае k = 0 мы должны выбрать n максимальных элементов из двух посорченных списков, это можно сделать, например, двумя указателями. А в случае отметим первых спортсменов в каждом списке.

A div 1 / C div 2: 377A - Лабиринт

Запустим поиск в ширину или в глубину из любой свободной клетки. Так как лабиринт связный, этот поиск обойдет все s свободных клеток. Однако мы прервем этот поиск на том моменте, когда он посетит s - k свободных клеток. Очевидно, эти s - k клеток образуют связную область. Оставшиеся k клеток просто превратим в стены.

Претесты проходило также решение, каждым ходом превращающее в стену ту клетку, у которой меньше всего соседей. Это неверно, например, на следующем тесте:

....
.#..
..##
..##

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

B div 1 / D div 2: 377B - Подготовка к соревнованию

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

Вначале отсортируем баги по сложности, а студентов по скиллу (это можно сделать один раз вне бинарного поиска). Посмотрим на самый сложный баг. Кто мог бы его исправить? Очевидно, его могут исправить те студенты, чей скилл не меньше сложности бага. Поместим всех таких студентов в очередь с приоритетами (в которой будет сортировка по стоимости студентов) и выберем оттуда самого дешевого. Так как мы проверяем время t, то этот студент должен пофиксить t самых сложных багов (он точно может их пофиксить). Отметим это, и перейдем к рассмотрению следующего непофикшенного бага. Снова поместим всех студентов, которые могли бы его исправить (по студентам надо проходиться параллельно с багами), в очередь с приоритетами и выберем самого дешевого. И так далее. Если в какой-то момент оказалось, что текущий баг не может исправить ни один студент (очередь с приоритетами пуста), значит время t не подходит в бинарном поиске. Если мы не уложились в требуемое количество зачетов — тоже не подходит. Иначе мы найдем нужное расписание.

C div 1 / E div 2: 377C - Captains Mode

Есть несколько наблюдений, после которых задача становится очень простой. Первое наблюдение — пикать надо всегда самого сильного героя. А вот про баны ничего такого сказать нельзя, в разных ситуациях могут потребоваться самые разные баны. Самое важное наблюдение, которое поможет решить задачу — то, что рассматривать следует только m сильнейших героев. Действительно, при любой игре, где будут пикаться самые сильные герои в каждый момент времени, никакой герой, кроме первых m, не может быть пикнут вообще никогда. Значит, и банить их никогда не надо. И рассматривать тоже.

В итоге у нас остается в худшем случае 20 героев, а, значит, можно решить задачу динамикой по подмножествам: dp_mask — разность между силами команд в ситуации, когда пикнуты либо забанены те и только те герои, чьи биты в маске установлены в единицу. Для переходов перебираем героя, которого команда, чья очередь хода, будет пикать или банить. Проще всего реализовать это с помощью рекурсии с сохранением. Ответ будет храниться в dp_2^m - 1.

К сожалению, мы неправильно оценили сложность этой задачи (несмотря на простое в реализации решение, придумать его, как выяснилось, было не так то и просто — стандартные 1500 баллов были бы лучше), и выставили неправильный TL (так что многие решения на C++ за m²·2^m проходили — следовало опустить ограничение до одной секунды, а то и до 0.75 секунд). Так что если вы решили задачу за m²·2^m, считайте, что вам повезло и что ваш вердикт — Time Limit Exceeded.

Почему можно писать это за m·2^m? Потому что пропуск бана не имеет смысла: вместо этого можно забанить самого слабого героя из доступных — ведь его точно никто никогда не пикнет.

Здесь тоже были слабые претесты, поэтому можно было ломать тех, у кого в решении не было битмасок, чуть ли не любым большим случайным тестом.

D div 1: 377D - Разработка игры

Рассмотрим оптимальный ответ. Заметим, что каждый ответ характеризуется такими двумя числами L и R, что max{l_i} ≤ L, R ≤ min{r_i}, и L ≤ v_i ≤ R. Т.е., зная L и R, мы можем перебрать всех сотрудников и выбрать тех, что подходят под вышеперечисленные условия.

Нарисуем плоскость, по оси абсцисс которой будем откладывать параметр L, а по оси ординат — R. Если точка (L, R) на этой плоскости является оптимальным ответом, то сотрудники, которые входят в ответ, обязательно удовлетворяют соотношениям l_i ≤ L ≤ v_i и v_i ≤ R ≤ r_i. Эта область представляет собой прямоугольник на плоскости. Так как нам надо найти максимальное количество сотрудников, мы должны отыскать такую точку (L, R), что она входит в как можно большее количество указанных прямоугольников.

Это уже совершенно стандартная задача, решающаяся с помощью сканирующей прямой по одной оси и дерева отрезков — по другой. Основная сложность — сведение к ней.

E div 1: 377E - Cookie Clicker

Для начала избавимся от вырожденных строений: оставим для каждого v_i только строение с наименьшим c_i при этом v_i. А также выбросим все строения, скорость которых меньше скорости самого быстрого строения с c_i = 0.

Также довольно очевидно, что имеет смысл в каждый момент времени использовать только самое быстрое строение. И если мы будем в оптимальном ответе когда-нибудь использовать какое-либо строение, то купить его надо сразу же, как только появятся на это деньги (я буду называть печенья деньгами). И сразу же начать использовать.

Представим себе плоскость (x, y), где по оси абсцисс будем откладывать время, а по оси ординат — деньги. Будем поддерживать график y = f(x) функции "максимальное количество денег, которое можно заработать за время x", добавляя на этот график поочередно по одному строению. Этот график представляет собой объединение отрезков прямых с угловыми коэффициентами v_i, каждый из которых активен на некотором отрезке [x_li, x_ri].

К примеру, в начале это просто прямая y = v₁x, где v₁ — скорость строения, которое можно купить за 0 рублей. Пусть следующее по скорости строение можно купить за c₂ рублей. Найдем минимальную точку x₀₂, график функции в которой больше или равен y = f(x₀₂) ≥ c₂, и купим это строение в момент времени x₀₂. Тогда мы должны построить прямую y = y₀₂ + v₂x, где y₀₂ = f(x₀₂) - c₂ — сколько денег останется после покупки. Итого у нас есть две прямых. До какого-то момента (причем не до x₀₂, а немного дольше) выгоднее будет старая прямая, но так как v₂ > v₁, найдется момент времени (это ceil(x₁₂), где x₁₂ — точка пересечения двух прямых), когда выгоднее станет новая прямая. Теперь отрезков прямых в графике две.

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

Если требуется еще и сказать, какие строения надо при этом использовать, надо для каждого отрезка хранить тот, из которого он был получен (т.е. тот, который использовался перед тем, как мы купили этот). Имея такой "массив предков", нетрудно восстановить ответ. Чтобы задача стала немного проще, мы убрали из финальной версии вывод сертификата.

Всем привет!

Авторы сегодняшнего раунда — craus и dalex. Мы не могли просто так пропустить раунд с таким красивым номером, поэтому в 19.30 MSK вам придется решать задачи, которые Павел для вас придумал, а я подготовил.

Благодарим Gerald и Delinur за помощь в подготовке соревнования и MikeMirzayanov за то, что у нас есть Codeforces.

Систему подсчета баллов и их распределение вы узнаете вместе с началом раунда. Все равно эта информация не несет особого смысла, пока контест не начался.

Полных решений и успешных взломов!

UPD. Контест завершился, поздравляем победителей!

Div. 1:
1. Petr
2. tourist
3. Egor

Div. 2:
1. k3e18
2. tongcx1988
3. LeMieux

UPD. 2 Опубликован разбор задач.

Так как администрация сайта не хочет фиксить баг с двумя разными кодефорсесами (1 2), прошу всех пользователей вставлять относительные ссылки.

Это делается так:

• /profile/tourist

• /blog/entry/1

• /contest/1/problem/A

При переходе по такой ссылке вы не будете разлогинены. Спасибо.

В субботу, 12 октября, в 12.00 пройдет очередная 5-часовая тренировка на Codeforces. Уже во второй раз мы делаем отборочный контест для СГАУ, чтобы определить команды, которые поедут в Саратов (прошлогодний аналогичный контест можно найти здесь).

Как многие из вас знают, команда Teddy Bears завершила свои выступления в ACM ICPC. Это повлекло за собой переименование и перенумерацию команд. Теперь у вас есть уникальная возможность обыграть новую первую команду СГАУ и показать им, какое место они способны занять в четвертьфинале. Не пропустите свой шанс!

Контест закончился. Теперь можно просто порешать задачи или написать его виртуально.

Xellos сделал разбор задач, за что ему большое спасибо.

Этот текст я пишу в основном для ребят младших курсов своего университета, чтобы они наконец начали участвовать в соревнованиях Topcoder. Так получилось, что на Codeforces это сделать мне наиболее удобно. Может быть, кому-то еще пригодится.

Что вообще такое Topcoder

Topcoder — это как Codeforces, только менее удобный. На самом деле, помимо соревнований по спортивному программированию там проводится еще куча мероприятий, которым аналогов в мире нет, так что многим деваться просто некуда :) А для тех, кто занимается именно спортивным программированием, это просто еще три-четыре неплохих контеста в месяц.

Если кликнуть на сайте на ссылку Events, а далее — Event Calendar, можно увидеть расписание этих контестов. Время там указано какое-то американское, чтобы получить московское, нужно в разное время года прибавлять либо 8 часов, либо 9. Кроме того, можно кликнуть на конкретный SRM (раунды здесь именно так называются — Single Round Match), и там будет ссылка на timeanddate.com, показывающая, во сколько начнется этот раунд.

Точно так же, как на Codeforces, на Topcoder есть рейтинг, есть красные и серые, есть комнаты и взломы, но устроено это немного по-другому. О правилах — в следующем разделе.

Правила Topcoder SRM

Раунд начинается с регистрации. За три часа до начала открывается регистрация, за пять минут до начала — закрывается.

Раунд состоит из двух частей. Сначала 1 час и 15 минут длится Coding Phase — тут надо решать задачи. Затем следует пятиминутный перерыв, и после него 15 минут идет Challenge Phase — здесь вы можете взламывать решения своих соперников по комнате. В отличие от Codeforces, решение задач и взломы на Topcoder разделены.

В раунде три задачи, обычно они стоят 250, 500 и 1000 баллов, иногда эти числа могут различаться. Изначально все задачи закрыты, но можно открыть некоторые из них и начать решать. Со временем стоимость открытых задач убывает, но нельзя получить за задачу менее 30% от начальной стоимости. Понятно, что пока не решишь одну задачу, невыгодно открывать другие — за них стоимость также начнет убывать. За ресабмит участник получает штраф в 10% от чего-то там, не помню, чего именно. Лучше сразу писать правильно и не ресабмитить.

Успешный взлом дает +50, неудачный дает -25. Затем прогоняются систесты, задачи падают, и участники узнают свои финальные результаты, после чего открывают Codeforces и начинают спрашивать, как решать 500.

Собственно, из правил это все, и дальше пойдет рассказ о конкретной IDE и конкретном языке программирования применительно к Topcoder. Вообще, писать там можно на Basic, C++, C#, Java и Python. Я расскажу про Java и Eclipse.

Arena, или как разработчикам Topcoder удобно кодить

По дефолту контесты пишутся в Арене. Ее можно запустить, протыкав на сайте ссылки Competitions — Algorithm — Single Round Matches — Launch Arena. Это Java-апплет, в котором вы типа должны писать контесты. Но мы не будем этого делать. Большинство людей все-таки используют нормальные среды разработки. Здесь будет рассказано об Eclipse, на странице загрузки подойдет, например, Eclipse Standard, и о плагине EclipseCoder.

Главное меню Арены

Я умолчу о том, что чтобы писать контесты на Java, неплохо бы установить JDK, поэтому этот шаг будет пропущен :) Скачайте Eclipse, распакуйте его и запустите. Теперь пришла пора установить плагин. Нажимаем Help — Install New Software, в строчку впечатываем адрес http://fornwall.net/eclipsecoder/. Понимаем, что можем установить вот такие компоненты (см. картинку). Выбираем Core, Java Support и Problem Archive, принимаем лицензионное соглашение, устанавливаем, перезапускаем Eclipse. Теперь можно писать контесты.

Установка EclipseCoder: выбор компонентов

Добавим вьюшку, из которой можно запускать Арену прямо из Eclipse. Тыкаем Window — Show View — Other, там выбираем EclipseCoder — Problem Statement. У нас появляется еще одна вкладка, на которой есть иконка с логотипом топкодера. Эта кнопка запускает Арену.

Вкладка с кнопкой запуска Арены

Точнее, она смотрит, как версия находится у вас сейчас (необходимые jar-ники качаются в папку ~/.eclipsecoder, где ~ — папка пользователя), обновляет, если нужно, и запускает. Не надо лезть на сайт и искать там ссылку Launch Arena — все делается из IDE.

Обновление Арены из Eclipse при запуске

Посмотрим на настройки EclipseCoder: в Eclipse перейдите по Window — Preferences — EclipseCoder. Здесь, если не боитесь, можно сохранить логин и пароль от своего аккаунта, а в подменю Java можно написать шаблон, который будет у вас появляться автоматически при решении каждой задачи. Довольно несложно догадаться, что означает каждая из этих переменных с долларами.

Шаблон класса

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

Задача Div-2 250: полное прохождение

Давайте теперь для завершения решим какую-нибудь халяву из дорешивания. Процесс решения на контесте и в дорешивании ничем не отличается, так что — запускаем Арену из Eclipse(это важно!), тыкаем там Practice Rooms — SRMs — и я выбрал самый последний раунд: SRM 592 Div 2.

Главное меню SRM 592 в дорешивании

На самом деле по внешнему виду дорешивание не отличается от контеста. Выберем задачу. Нажимаем на Select one и тыкаем 250 — это самая легкая задача.

Окошко с условием задачи

Если бы вы не использовали никаких плагинов, вы бы сейчас кодили в табе Coding Area прямо в этом окошке. Потрясающе удобное времяпровождение. Но мы пойдем наиболее хардкорным путем и откроем Eclipse.

Тем временем в Eclipse

Условие можно читать в Eclipse. Кодить можно в Eclipse. Видим, что нам сгенерировался метод, который нас просили написать, но, к сожалению, return 0; — это неправильное решение и не проходит даже семплы. Слева вы видите результат прогона юнит-тестов: EclipseCoder парсит семплы в условии и создает юнит-тесты, которые можно запустить одним кликом и увидеть, что вернул ваш метод и что он должен был возвращать на самом деле.

Теперь давайте решим задачу. Задача следующая: дан массив чисел pages, надо выбрать из него number чисел так, чтоб сумма была не минимально возможная, но при этом как можно меньше. Еще и все элементы в массиве различны.

Первое, что пришло на ум: выбрать number-1 минимальных чисел, одно пропустить, и выбрать следующее. Давайте попробуем это написать. Пишем, нажимаем Ctrl+F11 (Run). При написании можно писать свои методы и свои вложенные классы, но в этой задаче такое не нужно. Eclipse предложит выбрать, как именно запускать наш проект. Запускаем его как юнит-тесты.

Диалог Run As

Видим, что все тесты зелененькие — значит, мы прошли семплы!

Семплы пройдены!

Давайте добавим какой-нибудь свой тест. Откроем Package Explorer и выберем там класс, название которого оканчивается на Test.

Класс с юнит-тестами

Собственно, тут мы вольны использовать все возможности Junit. Чтобы создать свой тест, надо объявить публичный метод и снабдить его аннотацией @Test. Если при выполнении такого метода не будет никаких исключений, тест будет зелененьким :)

На сгенерированных автоматически тестах есть параметр timeout для аннотации @Test — он поможет вам отловить TL. Если вы хотите подебажить один из тестов — поставьте там timeout = (int)1e9 или вообще удалите этот параметр, поставьте брейкпоинт на внутри тела соответствующего метода-теста и жмите Debug. Либо можно просто выводить что-нибудь в System.out или System.err — топкодер эти выводы игнорирует — ему важно только то, что метод вернул.

Допишем свой собственный тест.

Собственный тест

После запуска выясняется, что он тоже работает правильно! Ну теперь можно сабмитить. Открываем Арену, точнее, то ее окошко, где написано условие задачи, жмем Compile — нам говорят, что все круто. Жмем Test — и запускаем наш код на одном из семплов (в этом режиме код запускается на сервере, я рекомендую в каждой задаче хотя бы один семпл пройти по кнопке Test — ну просто чтоб убедиться, что на сервере все нормально).

Запуск первого семпла на сервере

Видим, что Correct Return Value: Yes. Ну, значит все хорошо. Жмем Sumbit. Так как я писал этот текст одновременно с решением задачи, нам дали 156.76 очков из 250. Это, конечно же, очень мало, и на настоящем контесте за подобные задачи надо получать в районе 240-245 баллов.

У нас приняли сабмит

Систесты, однако, мы не проходили. Это всего лишь сабмит приняли. На настоящем контесте вы по его окончании узнаете, прошла у вас задача или нет, а в Practice Mode можно это проверить. Тыкаем в главном окне Арены Practice Options — Run System Test.

Accepted!

Все, теперь мы умеем решать топкодер. Потренируйтесь немного в Practice Mode, а потом можно приступать к самим SRM.

Раунд кончится в понедельник, 12 августа, в 14-00. Можете считать это небольшой напоминалкой (вход в контест).

Но пост не об этом. Кто вычитывает тексты условий? Уже второй раунд подряд нам предлагают такую ересь from my heart (задача C из Round 1, задача F из Round 2), что ну просто вообще невозможно понять, что от тебя хотят. Может, стоит назначить отдельного человека или даже группу людей, которые будут читать условия и гарантировать, что они понятные?

Вчера, 3 июля, прошел финал ACM ICPC 2013. Этот пост не будет подробно рассказывать о том, как прошел контест нашей команды, этому будет посвящен лишь один абзац. Я поведаю в основном о недостатках и просчетах организаторов финала. Они были, и я надеюсь, что в следующем году этого не повторится.

(осторожно, в этом абзаце вы можете заспойлерить себе некоторые задачи!)
Сначала о контесте: мы заняли 35 место с 5 задачами. Это немного хуже, чем я ожидал (мне казалось, что у нас будет место в районе 25-30). В начале контеста мы сильно растерялись. Я и craus очень долго думали над задачей F — мы сдали ее под занавес первого часа, по пути отсеяв несколько неверных решений и написав то, к которому не получилось придумать контрпример. Затем мы решали задачу D. Не понимая, как ее делать, Hohol распечатал ответы на первые несколько тестов, но ничего не извлек. Потом я вспомнил задачу с тимуса и написал точно такой же перебор — оказалось, что кандидатов на ответ порядка 50 тысяч (конечно, порядочный ACM-щик должен знать, что их мало, но мы такими не являемся), так что работает прекальк. Дальше подоспели решения задач A и H, которые пришлось немного подебажить, так как писать с первого раза мы так и не научились. Затем мы решили задачу C: сабмит в 3:5x был уже правильным, но TL-ным: команда из трех желтых участников не умеет писать maxflow и поэтому копипастит его с Team Reference, где есть лишь алгоритм Диница, да еще и с кучей ArrayList-ов. Заменив все ArrayList-ы на массивы, мы сразу же получили Accepted. Оставалось немногим более получаса, мы решили, что не умеем решать J за это время (задача, надо сказать, очень противная, из тех, что я особенно ненавижу — куча тупейшей бессмысленной реализации), и поэтому попытались решить B, но, как оказалось, надо было решать специфическую системку уравнений за O(1), как когда-то учили на третьем курсе (на самом деле приятная неожиданность — знания, полученные и успешно забытые в универе, оказались нужными в ACM ICPC!).

А теперь о фейлах.

• Мы приехали на поезде в 6 часов утра (примерно в это же время приехали и ИжГТУ). Но в отель нас не заселили, пришлось подождать до 14-00. Разумеется, компания IBM непременно обанкротится, если закажет дополнительные несколько номеров на одни сутки для участников финала чемпионата мира. В то же время craus и I_love_natalia вспоминают, что в 2010 году в Харбине такой фигни не было: тогда их сразу с аэропорта доставили в отель.

• Номера в отеле Англетер по цене OVER 9000 на первый взгляд почти ничем не отличаются от номеров в неплохом санатории, где я отдыхал несколько лет назад, за исключением отсутствия балкона (ну и собственно, самой цены). Но это только на первый взгляд: оказалось, что интернет в Англетере настолько хорош, что видео с Youtube качества выше 240p воспроизводить он не в состоянии. Пламенный привет провайдеру iBAHN.

• Перед открытием состоялось мероприятие IBM TechTrek. Видимо, организаторы считали, что очень комфортно сидеть два часа без перерыва на выставленных в ряд стульчиках. После первого часа количество занятых сидячих мест наполовину опустело — кто гулял, кто вообще вышел на улицу, все пили воду...

• На всех ужинах, проводимых в Манеже, а их было то ли три, то ли четыре — я уже не помню, а заглядывать в расписание лень — был доступен шикарный ассортимент напитков: Coca-Cola, Sprite, Fanta, Nestea и вода. Надо ли говорить, что многие участники вообще не могли пить газированные напитки (к примеру, у меня болело горло, и употребление лимонадов не очень-то способствует состоянию этого самого горла). Поэтому большинство брало себе Nestea, который сразу же после его доставки заканчивался за O(1). Воду пить на такого рода мероприятии тоже не очень круто. Почему нельзя было предоставить банальный чай с горячей водой?

• Во время пробного тура температура в зале была равна 18 градусам. На просьбы сделать потеплее организаторы никак не отреагировали, при том что большая часть участников пришла в одних майках и, я уверен, замерзала. Под конец пробного тура температура поднялась до 22 градусов, что уже приемлемо, но сидеть около 2 часов, ощущая холод вокруг себя, особенно немного приболев, не особенно круто.

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

• Наверное, так принято, но я считаю, что после 5-часового контеста неплохо провести обед. И даже если вы проводите церемонию закрытия, которая заканчивается примерно в 17-30 (а завтрак кончался примерно в 8-00 — разность считайте сами), то после нее надо дать нормально покушать, а не раздавать пакетики с яблоком, пачкой печеньев и минералкой и после этого...

• ... везти в цирк. ЦИРК??? Вы совсем там рехнулись? Какой еще цирк? Пяти сотням взрослых людей интересно смотреть цирковые выступления? Может быть, перед этим хотя бы стоит покушать и отпраздновать победы, не? Лично я половину выступления провел в вестибюле, найдя тот положительный момент, что можно наконец-то позвонить домой и рассказать обо всем, что происходило на финале. Вторую половину выступления я просто гулял по Михайловскому саду. В 19-00 нас таки отвезли в Манеж, где уже были накрыты столы, но на этот раз в холодильниках не было даже Nestea, а когда он появлялся, его мгновенно расхватывали. Это не Celebration Dinner, можно ливать.

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

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

У меня возник вопрос касательно Team Reference Document на финале.

В правилах сказано следующее:

Each contestant may bring a copy of your Team Reference Document.
This document may contain up to 25 pages of reference materials, single-sided, letter or A4 size, with pages numbered in the upper right-hand corner and your university name printed in the upper left-hand corner. Text and illustrations must be readable by a person with correctable eyesight without magnification from a distance of 1/2 meter. It may include hand-written comments and corrections on the fronts of pages only. The document should be in some type of notebook or folder with the name of your institution on the front.

Bring a CD of your Team Reference Document if you are bringing a Team Reference Document.
Label the CD with your university's name. The CD should contain only one file, a PDF of your Team Reference Document, with no active elements.

Соответственно, можно напечатать 25 страниц копипасты и принести ее с собой. Можно записать этот документ на CD, и его скопируют на рабочий компьютер. И вопросы.

• Есть ли PDF-читалка на предоставляемых компьютерах? (да, мы не ставили образ, т.к. Eclipse под виндой точно такой же)

• И что такое with no active elements? Выделяющийся и копирующийся текст — это active element или нет?

Вчера закончилось важнейшее мероприятие в жизни любого ACM-щика из России и стран бывшего СССР, кроме Украины и Молдавии. Сегодня я сижу в торговом центре "Невский" около Московского вокзала и пишу этот пост.

Часть 1: регистрация

30 ноября мы приехали в Санкт-Петербург. Отсидевшись несколько часов на вокзале, попутно иногда согреваясь в кафешках типа "Теремок" (надо сказать, погода была мерзкая, и теплая куртка не особо помогала), мы заселились в хостел (который находился прямо около вокзала), немного отдохнули и поехали в университет.

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

В комнатке для регистрации нас ждали огранизаторы полуфинала, которые отметили, что мы все-таки приехали, сотрудницы Яндекса, которые попросили заполнить их анкетки, сотрудницы Mail.ru, которые дали нам небольшое задание — его надо было отправить по интернету в специальную форму и получить возможность выиграть небольшой приз, и сотрудницы Jetbrains, которые предложили пройти несложный тест по языку Kotlin. Тест мы прошли сразу же. Без маленьких багов не обошлось, но тем не менее они решили дать нам приз. Можно было выбирать из футболки, чайника, кружки и лицензии на один из продуктов Jetbrains. Я подумал, что ворованную IDEA Ultimate IDEA Community Edition я могу и так поставить, поэтому выбрал футболку.

Дальше мы вернулись в гостиницу, решили задания от Mail.ru, немного считерив, воспользовавшись решалкой судоку, решалкой японских кроссвордов и распознавателем QR-кодов, отправили их и дальше весь вечер играли в разнообразные настольные и компьютерные игры.

Часть 2: пробный тур

Наступила зима, а это означало, что пришло 1 декабря и надо ехать на пробный тур. Открытие началось в 11 часов, но из-за неумолимого желания спать, а после пробуждения — еще и покушать, приехали мы примерно в 11-20. Впрочем, это никого не расстроило.

Открытие проходило как всегда: речи замечательных людей здешнего полуфинала переплетались с выступлениями танцевальных коллективов. Не могу не покритиковать ведущих, которые, видимо, никогда не готовятся к произнесению своих речей: в Саратове craus был назван Сёмушкиным, а здесь обижен был сам MikeMirzayanov, фамилию которого почему-то произнесли как "Мирзаян". Ну да ладно, посмеялись и забыли.

Дальше был пробный тур. В качестве пишущего пробный тур был выбран я: по статистике, когда его пишет Hohol, команда сливает контест, а когда я — наоборот. Задачи я решил сдавать в порядке X-Y-Z, т.к. для задачи X требовался стандартный ввод-вывод, а для остальных задач — файловый.

Привыкать к клавиатуре было некогда, поэтому я делал кучу опечаток, но потерял в сумме немного — секунд 30-40 и все-таки сумел получить суммарный штраф 6. К сожалению, с ИТМО-1 бесполезно конкурировать даже на пробном туре: нельзя просто так взять и выиграть пробный тур. Компьютер работал достаточно быстро, PCMS вроде бы тоже не тупил, так что единственное, чем мы остались недовольны — расположением компьютеров в зале. Например, я мог одним движением руки выключить компьютер Saratov SU 2 и Perm SU 1. Не думаю, что их обрадовала такая перспектива, хоть делать мы этого и не собирались.

На встречу с Яндексом и Mail.ru мы не пошли, предпочтя им очередные партии в сет, шахматы, го, покер, прохождение Hitman на максимальной сложности с максимальным рейтингом, прослушивание музыки и прочие бесполезные занятия.

Завтра контест — надо рано лечь спать! Ага, щас. В Петрозаводске лучшие наши контесты были, когда мы играли в покер до двух-трех часов ночи. По странному совпадению в этот день мы легли спать в час ночи — вставать надо было в 7 часов утра. Вроде как идеальная продолжительность сна. Завтра пройдем в финал и окончательно докажем это. Глазки закрывай, баю-бай.

Часть 3: контест

Осторожно: дальше присутствуют спойлеры по задачам!

Итак, наступило 2 декабря, следовательно, надо опять ехать в универ и играть контест. Ну что ж, нам не привыкать, поехали.

В универ приехали за 40 минут до начала. На контест запускали за 15 минут до начала — пришлось подождать в вестибюле. Жюри не гарантировало, что время на компьютерах будет правильное, поэтому я взял у I_love_natalia наручные часы, перевел их на 10.00 и остановил — включу вместе с началом контеста.

3, 2, 1, начали! Hohol берет первую половину комплекта и читает с начала, craus — вторую и читает с конца, я открываю Visual Studio, создаю проект, пишу шаблон. Примерно через 5-6 минут Hohol просится написать задачу A: говорит, изи, решу за 5 минут. Дописываю шаблон — там пара строчек оставалась и отдаю комп, сам читаю с B и дальше. 10:27 — Accepted. Открываем монитор, смотрим: сдают A и G. craus берет G, думает пару минут — идем писать ее.

А переполнения не будет? Что-то я очкую. Пошли на Java напишем. Открываю Eclipse, создаю проект, в это время craus выводит на бумажке формулы. Класс создан, перебиваем решение. Тесты проходит, с TL тоже нормально. Сабмит, WA на примерно 35 тесте. Ctrl+P, Enter, дебаг. Что за фигня? Все вроде работает. Давай посчитаем побольше коэффициентов. Какого черта ответы разные? Ничего не понимаю. Что еще решают? H решают. Hohol идет решать H. Эй, почему тут (k·k)²ⁱ? Надо или (k·k)ⁱ, или (k)²ⁱ! Исправляю, теперь все тесты проходит, даже злобные вроде "64 2". 46:09. Сабмит, Accepted.

Что по H? Ничего? Хреново. Я пошел над ней думать. Комп простаивает. Что еще решили? Во, E решили. craus читает E. Да там же просто жадность! Hohol садится писать. Я в это время придумываю что-то по H: давайте хранить для каждой буквы префиксные суммы по модулю 2, а потом слева направо пересчитывать. Нужно будет что-то вроде ксор-равно на отрезке и сумма на отрезке. craus — а давай в сете хранить все, что слева. В мапе? В мапе. Ммм, 52 * 300000 * логарифм мапы. Не зайдет же. Да ладно, сервак быстрый, если что, на хешмапу переделаем. Ну окей, готов писать.

Hohol дописал E. Сажусь тестить. Вроде все нормально. Сабмит — WA. Что за чушь? Эй, q_i тоже long long! Исправляем. 94:25. Сабмит, Accepted.

Сажусь писать H. Очень быстро дописываю, сабмит, TL. Что? Генерирую макстест, локально 1.8 секунд. Быстрый сервак, говорите? Сабмичу это на уже сданную задачу E — TL. Ну да, быстрый сервак, так мы вам и поверили. Исправляю map на hash_map. Локально 0.8 секунд. Сабмичу на E — Presentation Error. Ну ладно, вроде так успевает. Убираю генератор теста, сабмичу на H. Accepted. Время 118:05. Смотрим монитор. Наша вторая команда отстает от нас на 7 минут штрафа.

Что еще сдают? B сдают, C сдают. craus: мы тут вроде бы запруфили, что ответ равен , но это за квадрат, придумай, как побыстрее. Окей, придумываю. Значит, при фиксированном a_i у нас неравенство . Похоже на уравнение прямой. Давайте нарисуем в плюскости (i, b_i). Похоже, все точки должны лежать по одну сторону от какой-то прямой. Похоже на какую-то касательную к выпуклой оболочке этих точек. Отдаю craus: иди, придумай что-нибудь, вроде все правильно, остались детали.

В это время пишу проверку по задаче B: что, если собрать статистику, сколько какая вещь встречается? Давайте проэмулируем случай 9 и 10 одинаковых вещей, сильно ли они различимы. Хм, совсем не различимы, нельзя так решать. craus: я все вывел, пойдем писать. Ну пойдем. Пишем, тесты проходит. Тестируем, правильно ли написали выпуклую оболочку — все нормально. 179:05. Сабмит — Accepted.

Hohol придумывает решение задачи B: давайте вначале уберем все предметы из рюкзака, а потом положим туда все предметы, не убирая в процессе. Так мы узнаем все веса. Решаем рюкзак, дальше убираем те вещи, которые не нужны в оптимальном ответе. Немного думаю над J, ничего не получается. Начинаю тестить B. Выявляем штук 5 багов. Исправляем, сабмитим. Время 215:38. Accepted.

Что решать: J? Смотрите, еще F сдают. О, да она наверное проще, давайте ее решать, две все равно не успеем. Следующие 20 минут пишем решение, считающее, что поворачивающиеся и неповорачивающиеся элементы змейки чередуются. Блин, да оно семпл не проходит! Нахрена мы это все писали? В семпле они не чередуются! Ладно, тогда вместо динамики пишем просто перебор, наверняка зайдет. Пишем, до конца контеста 10 минут. Семпл прошел. Сабмитим, PE 5. Что, ответ не выводим? Пофиг на штраф, если что, поменяем время на задачу. Ставим assert на то, что не нашли ответ. RE 5. Все-таки не находим. Почему? Непонятно. Contest is over.

Смотрим на замороженный монитор: мы на 9 месте, если убрать лишние команды. Выходим в вестибюль. Говорят, Саратов чуть ли не не проходит. Спрашиваю у Fefer_Ivan: Saratov SU 1, 2, 3 по 5 задач. Ололо, близится сенсация. А, Saratov SU 2 все-таки обогнали JKeeJ1e30? Ну ладно, ололо становится поменьше. Ребята уходят кушать в Subway, я иду в столовку, встречаю там Izhevsk STU. Сколько кто сдал? Ижевск — 7 задач, СПбАУ — 7 задач. Окей, мы теперь 11-ые. Уфа — 6, по штрафу мы лучше. Кто там еще нас может обогнать? University of Latvia — встречаю их в актовом зале, говорят, у них 5. Petrozavodsk SU с 4 задачами сделали три сабмита — спрашиваю Дениса Власова, говорят, ничего не сдали. Странно, Петрозаводск вроде неплохая команда. Подходит yarrr, ему страшно, он не сдал шестую задачу. Смотрим вместе с ним монитор — а ведь их команду мало кто обгоняет. Кто там еще? Altai STU, Moscow SU of Steel and Alloys имеют 5 задач и два вопросика. Ну ладно, мы в худшем случае 13-ые, вроде проход, в том году было 16 команд, а ведь еще и финал в Петербурге.

Разбор задач. Говорим наше решение задачи C, зал дружно смеется. Ну и пихайте дальше ваш бинпоиск с даблами :D Наше решение на самом деле очень небольшое и быстро пишется, сложность только в придумывании. Скоро награждение.

Монитор начинает размораживаться снизу вверх. Наша вторая команда занимает 42 место и получает диплом третьей степени — к сожалению, задачу C они в заморозку не решили. Никогда еще вторая команда СГАУ не была так высоко. Сразу перед ними — две команды Belarusian SUIR, одна из которых — действующий бронзовый призер финала. Сенсации только начинаются.

Дальше команды с 5 задачами. Среди них Moscow IPT The Sun, как мне казалось, самая сильная команда МФТИ (простите, если кому-то казалось не так), команда Новосибирска, почти весь Саратов. Altai STU — оба вопросика превращаются в минусы, тоже 5 задач. Теперь мы точно 11-ые, если удалить лишние команды. Выходим на сцену, получаем благословление от руки Petr.

IITU сдали 8. Молодцы, хорошо сыграли, я рад за эту команду. А по рейтингу на Codeforces такого и не предположишь! SPbSU 4 таки сдают свои 4 задачи в заморозку. Belarusian SU сдают последнюю свою задачу на 299:36 и выходят на второе место! Moscow SU ST сдают последнюю задачу на 299:57 и выходят на второе место! ITMO 1 не сдает задачу K, the hardest problem ever given on NEERC. Контест удался.

Объявляют команды, прошедшие на финал. Мы 11-ые, Ufa SATU 12-ые. Так, команды с 5 задачами все-таки проходят. Алтай, Каунас, МАИ. 16 место достается Saratov SU 2 — предполагаемый гнев MikeMirzayanov должен несколько спасть. 17, 18! 18-ое, как позже выяснилось, предпоследнее место достается Perm SU, которые, по их словам, даже и не надеялись. Скоро становится доступна информация, что квота на самом деле 19, и последними на подножку уходящего финала запрыгнули Novosibirsk SU. Результаты доступны на сайте NEERC, а также у Снарка, где красным цветом выделены прошедшие команды.

Заключение

Мне очень понравился контест. Задачи классные, намного лучше, чем в 2010 и 2011 годах. Почти не требуется знаний каких-то жестких алгоритмов и структур данных, зато подумать надо, и много, этим славится NEERC, и мне кажется, что это хорошо. А решать меньше 7 для команд, которые ставят цель выйти на финал, на этом контесте, вроде бы, позор. Меньше 6 — совсем позор. Квота 12 команд, по мнению некоторых, была бы очень кстати. Но не мне это решать, меня и так все устраивает :)

ACM-карьера продляется до 3 июля. Увидимся на ACM ICPC World Finals 2013!

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

Задание: кооперативный мат в 2 хода. Кому лень читать статью по ссылке — черные начинают первыми, каждая сторона делает по два разрешенных правилами хода, и вторым своим ходом белые объявляют мат. При этом стороны действуют сообща, т.е. черные хотят, чтобы им как можно быстрее поставили мат, и белые это знают.

Вчера я стал почти уверен в том, что быстрейший способ решить эту задачу — написать программу для ее решения. Наверняка тут есть люди, не понаслышке знакомые с шахматами — сможете опровергнуть мое утверждение? :)

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

Всем привет!

Только что закончился четвертьфинал Южного подрегиона NEERC, и я хотел бы немного рассказать, что происходило сегодня и вообще на этой неделе в Саратове.

Часть 1: читайте инпут, посоны!

Hohol, как обычно, решил выиграть пробный тур. Как это делать, Hohol прекрасно помнил, ведь на его счету два выигранных пробных тура в 2011 году :) На сей раз, как выяснилось на открытии, жюри четвертьфинала решило добавить интерактивную задачу, поэтому на пробном туре нас тоже ждали интерактивные задачи.

Порешили на том, что Hohol садится за клавиатуру и пишет две стандартные задачи саратовского пробного тура, я слежу, как он это делает, а craus решает интерактивку. Посабмитив две первые задачи примерно на 2:10 и 3:30, мы обнаружили, что первая из них получила WA 1 (забыли считать инпут), а вторая — TLE 11 (инпут был слишком большой для cin). Так что мы забили на идею победить в пробном туре, открыли студию и начали спокойно писать две интерактивные задачи.

Сдав эти интерактивные задачи, мы с удивлением и смехом обнаружили себя на первом месте (одна из интерактивок была довольно неплохой сложности и многим не поддавалась). На следующий день нас ждало Code Game Challenge.

Часть 2: не оставляйте known issues, посоны!

Code Game Challenge заключался в следующем: дано игровое поле с двумя большими препятствиями в центре и четыре танка машинки, управляемые программами участников. Машинки должны были ездить по полю, собирать флаги (которые давали очки) и лечиться на своей ремонтной станции. Особенностью этого Code Game Challenge было то, что машинки погибали навсегда — поэтому осторожное объезжание препятствий, стен, других игроков было важной частью стратегии. Еще можно было стрелять друг в друга шинами, правда, кажется, это было не очень эффективно — шины просто отталкивали соперников, но не наносили им урона непосредственно.

Code Game Challenge полностью писал я по указаниям craus, который вечером раздумывал над особенностью стратегии. В итоге наша машинка на тестах против случайных машинок была примерно в серединке. К тому же у нас был баг, проявлявшийся примерно в 1 случае из 15. Я не буду раскрывать всех подробностей Code Game Challenge. Вы можете посмотреть видео, понаблюдать за нашим багом своими глазами и вообще насладиться великолепной атмосферой этого шоу.

Часть 3: не сабмитьте ML 1, посоны!

Контест довольно неплохой, так что советую всем его порешать (на acm.sgu.ru, задачи 542-553 или на Codeforces-тренировках). А если при решении возникнут трудности, специально для вас есть разбор задач с места событий.

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

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

В начале контеста мы довольно серьезно тормозили. craus прочитал задачу E и мы начали ее писать. Мы ее написали и обнаружили, что задача была решена неправильно: craus пошел думать дальше, а Hohol сел за задачу L.

Задачу L Hohol писал по ощущениям минут 15, один раз полностью переписывая решение заново. После этого я сел писать задачу J, а Hohol за мной наблюдал. Ее мы написали довольно быстро. Посмотрев на монитор, мы увидели один AC по задаче E от нашей второй команды (Slamur, Sinner, Jeg) и несколько AC по задаче F. Читаю задачу F — да это же халява! Пишем сдаем, AC.

После этого craus придумал (видимо, не очень оптимальное — можно было сэкономить на этой задаче минут 20-30) решение по задаче E, требующее дерево отрезков — я пошел ее писать, распечатал, Hohol нашел в ней пару багов, а в это время мы дописали остальное решение. Получив AC, мы посмотрели на монитор — мы были на 4 месте, а на 3 месте расположилась наша вторая команда, очень быстро сдавшая четыре задачи. На первых двух местах были команды из Саратова.

Следующей нашей задачей стала задача G. Hohol и craus придумали основную идею, а я пошел писать. Написав эту задачу (правда, потеряв, по ощущениям, минут 10), мы решили ее посабмитить. Вердикт: Memory limit exceeded on test 1. Ой!

Итак, всем советую:

1. проверять, сколько ваша программа жрет памяти с помощью Task Manager (Ctrl+Shift+Esc) или опции запуска на сервере.

2. или хотя бы правильно считать размеры массивов на калькуляторе, считая, что тип int занимает 4 байта, а не 1.

Через три минуты мы получили AC, но штрафная попытка, к сожалению, уже была получена.

Затем я и craus пошли думать над задачей B, которую к тому времени сдала команда Saratov SU 1, а вскоре Hohol придумал решение задачи H, которую я перед этим неправильно прочитал и посчитал гробом. Hohol сел за комп и вскоре сдал нашу шестую задачу H. Открыв монитор, мы с грустью увидели отставание в 5 минут от третьего места, на котором расположилась команда Saratov SU 4.

В оставшиеся полтора часа мы пытались написать задачу C (по которой у Saratov SU 2 к этому времени было несколько штрафных попыток) и додумать задачу B (потом оказалось, что мы были на правильном пути и немного недопридумали).

Наша вторая команда в это время пыталась сдать задачу G. Оказалось, что они примерно в течение двух часов слали очевидно TL-ящееся решение. Сразу после заморозки Sinner придумал-таки нормальное решение и они сдали пятую задачу. Потом они написали задачу H, получили по ней WA 16, но ошибки до конца контеста так и не нашли. На NEERC, впрочем, наша вторая команда попала, причем за счет быстрых четырех первых задач у них было даже не последнее место среди тех, кто сдал пять задач.

Итак, сегодня у нас было чуть менее, чем 100500 возможностей занять 3 место, но что-то не сложилось :(

Заключение

Собственно, две команды Samara SAU едут на NEERC, где мы со многими из вас встретимся. Пожелаем нам удачи, ибо это последний сезон и последний шанс попасть на финал. Ждем 2 декабря и спасибо за внимание.

P.S. Вроде бы монитор на сайте соревнования не открывается уже открывается: http://contest.sgu.ru/monitor/?id=1
На NEERC прошли команды вплоть до 19 места, из них из Саратова — только три первых говорят, что четыре, так как проведение контеста дает +1 к квоте.

P.P.S. Видео Code Game Challenge выложено на Youtube. Разбор задач выложен на Youtube.

Я просто оставлю здесь генератор теста: [Codeforces] [Ideone] [Pastebin]

UPD. Аналогичный пост про Java 6: http://codeforces.me/blog/entry/2296

UPD 2. Ссылка обновлена. Новый генератор работает немного быстрее. Однако, кажется, где-то есть ошибка, поэтому для некоторых размеров массива может генерироваться быстросортируемый массив. Всегда проверяйте, действительно ли сортировка работает медленно.

UPD 3. Ссылки еще раз обновлены. Теперь все почти идеально. Есть один недочет, который я пока не придумал, как обойти, но в целом генератор свою функцию выполняет.

Всем привет!

Сегодня, 12 июня, в день, когда Россия отмечает день себя, на Евро-2012 стартуют матчи второго круга, а I_love_natalia празднует свой день рождения, мы представляем вам Codeforces Round #124.

К подготовке контеста имеют отношение команда Samara SAU Teddy Bears (craus, dalex, Hohol) и I_love_natalia. Также спасибо Alex_KPR и команде Codeforces (Gerald, Delinur, MikeMirzayanov). Мы думаем, что контест очень легкий, а вам придется за 2 часа доказать или опровергнуть это утверждение :)

Система начисления очков — динамическая (подробнее о динамической стоимости).
Авторы считают, что задачи упорядочены по неубыванию сложности.

Всем полных решений и успешных взломов!

UPD. Контест закончился, поздравляем победителей!

Div-1 (полные результаты):

1. tourist — единственный, кто решил все задачи!
   
2. RAVEman
   
3. aropan
   

Div-2 (полные результаты):

1. bmerry
   
2. littlefriend
   
3. gstsclq
   

UPD 2. Доступен разбор задач.

Всем привет!

В Самаре 14 апреля прошел сабж, а теперь мы хотим провести тренировку на Codeforces на этих задачах. Тренировка пройдет 11 июня в 11:00, благо, у россиян это выходной. Длительность контеста — 5 часов. Приглашаем всех принять участие!

Контест завершился, поздравляем maksay с победой и с пропихом самой сложной задачи контеста; теперь мы уменьшили на нее ограничения, и пропих, скорее всего, больше не удастся :)

Виртуальное участие тут: http://codeforces.me/gymRegistration/100052/virtual/true
Ссылка на тренировку: http://codeforces.me/gym/100052
Осторожно, в комментах спойлеры!

Контест готовили: I_love_natalia, steiner, pank.dm, Shlakoblock, elena и Александр Ефимов, которого нет на CF.

Особенности:

• Задачи доступны только на русском языке, но не исключено, что в будущем будет перевод.
  
• Сложность контеста выставлена 4 звезды, но на самом деле он немного полегче, где-то 3.5 звезды.
  
• Автор текстов условий — elena (зачем я это пишу? Просто примите участие в контесте!)
  
• Для ввода-вывода используются файлы input.txt и output.txt
  
• Как всегда, не надо использовать %lld, если сдаете решения на GNU C++
  

Осталась одна минута, не забудьте принять участие! :)

http://code.google.com/codejam/

UPD: Результаты: http://code.google.com/codejam/contest/1645485/scoreboard?c=1645485#

Первые 1000 участников проходят в следующий раунд.

Здравствуйте.

Проблема, которую я только что обнаружил, а I_love_natalia тому свидетель, возникла при генерации antiquicksort-теста. В частности, из-за этого бага я сегодня схлопотал неудачный взлом. Я очень удивился, когда во время контеста программа жертвы, взломанная таким генератором, отработала быстро. Однако под конец контеста я поменял размер массива с 100000 на 99987, и взлом стал успешен!

А теперь коротко о том, что же происходит. Вот тест-кейс:

1. Запустим генератор (чуть-чуть измененный, брать отсюда: http://pastebin.com/99RwHR6w) в запуске на сервере CF.

2. Сервер выведет что-то наподобие Sorting ended in 1953ms

3. Добавим в конец файла два перевода строки и запустим снова

4. Результат поражает: Sorting ended in 0ms. Вот что переводы строки животворящие делают!

Можно поэкспериментировать с добавлением и удалением пробелов и переводов строк: результаты будут отличаться: либо сортировка проходит за нулевое время, либо за примерно 2 секунды.

Для любителей острых ощущений прилагается видео: ссылка (осторожно, в распакованном виде оно занимает около 600 МБ)

Что это такое? На моем домашнем компьютере такого не происходит. Баг Java-машины, или сервер CF пытается уберечь участников от взлома?

UPDATE: Судя по всему, на некоторых серверах стоит Java 7, на которой сортировка реализована по-другому и выполняется на этих тестах быстро. Это очень нехорошо, т.к. я выбираю язык Java 6, когда хочу послать задачу, а она, оказывается, может тестироваться под Java 7. Прошу всех принять это к сведению, пока администрация все не поправит.

tourist уже сдал первую задачу, а треда все еще нет! Непорядок!

Делаем ставки:
1. На сколько задач tourist обгонит команду, занявшую второе место.
2. На какой минуте tourist сдаст последнюю задачу.

Результаты, как уже сказано, тут: http://neerc.ifmo.ru/school/archive/2011-2012/ru-olymp-team-russia-2011-standings.html

Осталось поздравить команду Гомеля (tourist, Snich, dimad) с победой!

Выложили материалы олимпиады:

• Условия
• Задачи с тестами и решениями жюри
  
• Презентация с разбором