Hey, folks!

I am not a fan of sport-programming t-shirts, but surely know that some of you would like to have one. If you wanna get a t-shirt, just add yourself in Google Form. After a couple of days I will pick a person randomly from the list, and contact him/her for contacts.

Also, I didn't decide how to calculate a random seed fair enough. So, feel free to propose something :)

Cheers!

Edit 1: Guys, please, don't mess around with the doc. Now you cannot edit the doc, please, add a comment with your handle.

Edit 2: Ok, you forced me to delete Google Doc, and spend more time, thanks :) Please, add you handle again in Google Form. Pay attention, you can only add your handle once. Make sure you wrote it correctly. Also to prevent cheating, I will chose among people who participated in at least 2 competitions.

Edit 3: Seems that everybody who wanted to participate in this put nickname in form. So, we can start the lottery.

I was super lazy, so I decided not to do anything complicated. I wrote python script:

#!/usr/bin/python                                                                                                                                                              
import random

filename = "input.txt"
times = 20

with open(filename) as f:
  lines = f.readlines()
  random.seed(314159265)
  for i in xrange(times):
    index = random.randint(0, len(lines) - 1)
    name = lines[index]
    print index, name[:len(name)-1]

Firstly, I picked 20 nicknames:

• 202 TooSchoolForCool
• 179 Hdz_78
• 202 TooSchoolForCool
• 259 LouisCK
• 18 serghov
• 324 krismaz
• 290 dutzul
• 188 Swift
• 86 Elk-cloner
• 233 TahaMahmoud
• 251 bnick
• 179 Hdz_78
• 168 muratt
• 107 heaton
• 6 zeulb
• 53 Prestige
• 157 bayram
• 242 Mohammad_Mohsin_COU
• 120 sampriti
• 199 gridnevvvit

Interesting that Mohammad_Mohsin_COU wrote his nickname in a wrong way, but I fixed it :)

Then I ran the same program with another filename and times=1. And the winner is: muratt. Congratulations to him!

Добрый вечер!

Завтра в 16:00 по Москве состоится финальный раунд Coder-Strike 2014, задачи которого, как и задачи всех предыдущих раундов Coder-Strike, готовили: Gerald, HolkinPV, Igor_Kudryashov.

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

Регистрация на контест откроется сегодня в 4:00 ночи по Москве, закончится она за 5 минут до начала соревнования. Неофициальные участники из первого дивизиона должны регистрироваться на контест "Coder-Strike 2014 — Финал (трансляция, Div. 1)", неофициальные участники из второго дивизиона на контест "Coder-Strike 2014 — Финал (трансляция, Div. 2)", официальные участники на контест "Coder-Strike 2014 — Финал".

Надеюсь, что задачи раунда вам понравятся, мы очень старались хорошо их подготовить.

Желаю удачи на контесте!

UPD. В связи с проведением онсайта соревнования Coder-Strike 2014, мы вынуждены ограничить доступ к сайту на время подведения итогов. Ориентировочно, сайт будет недоступен 15-30 минут после окончания контеста.

Упала задача B или C, прочитай разбор задач! :]

Добрый день!

Завтра утром состоится Coder-Strike 2014: Раунд 2. Как обычно, для участия в нем нужно зарегистрироваться на странице.

Аналогично прошлому раунду, все желающие могут принять участие в раунде. Раунд будет рейтинговым для всех официальных участников раунда (лучшие 50 официальных участников первого раунда), а также для неофициальных участников из второго дивизиона. Рейтинг по официальным и неофициальным участникам будет считаться отдельно. Для неофициальных участников из первого дивизиона раунд будет нерейтинговым, но не расстраивайтесь, финальный раунд обязательно будет рейтинговым для первого дивизиона.

Если есть какие-то вопросы, не стесняйтесь, задавайте их в комментариях.

Удачи и до встречи на раунде!

UPD 1. Прошу прощение за небольшое опоздание, разбалловка стандартная.

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

Доброе время суток!

Совсем скоро начнется Coder-Strike 2014: Раунд 1. Напоминаю, что его официальными участниками будут школьники Москвы и Московской области, решившие на квалификационном раунде хотя бы одну задачу. Все остальные могут поучаствовать в раунде неофициально.

Как обычно, для участия в раунде нужно зарегистрироваться на него на странице.

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

Раунд готовили я, HolkinPV и Igor_Kudryashov. Мы очень старались подготовить его как можно лучше. Если есть какие-то вопросы, не стесняйтесь, задавайте их в комментариях.

Надеюсь задачи раунда вам понравятся. Удачи!

UPD 1. Распределение баллов по задачам будет стандартное: 500-1000-1500-2000-2500.

UPD 2. Соревнование перенесено на 10 минут. Все, кто не успели зарегистрироваться, могут попытать счастье еще 5 минут. :]

UPD 3. Из-за сложностей с распределением комнат в этом раунде Div.1 и Div.2 участники будут в одних и тех же комнатах.

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

Добрый вечер!

Прошла квалификация, приближается раунд 1, пора подвести итоги квалификации. К сожалению, несмотря на многочисленные предупреждения, некоторые из пользователей, которые зарегистрировались на соревнование в качестве официальных участников, очевидно, не являются школьниками из Москвы или Московской области. Конечно, такие участники были удалены из официальной таблицы результатов и не будут допущены до официального участия в раунде 1. Если, по ошибке, вы оказались среди таких участников, как можно скорее напишите мне (Gerald) личное сообщение.

Еще одна новость состоит в том, что, так как количество школьников, проявивших интерес к соревнованию, оказалось меньше ожидаемого, сетка соревнования была пересмотрена. В раунд 2 пройдут лучшие 50 официальных участников раунда 1. Квота на финал не изменилась: 25 лучших официальных участников раунда 2 пройдут на финал. Кроме того, каждый официальный участник раунда 1, решивший хотя бы одну задачу в нем, получит памятную футболку чемпионата Coder-Strike 2014.

Все те, кто не являются школьниками из Москвы или Московской области, и те, кто не прошел квалификацию, могут поучаствовать в раунде 1 неофициально. Раунд будет рейтинговым для всех неофициальных участников раунда 1 из Div. 2, а также для всех официальных участников раунда 1. Рейтинг будет считаться отдельно для официальных участников и неофициальных участников. Неофициальные участники из Div. 1 также могут насладиться задачами раунда :], для них раунд будет нерейтинговым.

Удачи на предстоящем раунде!

411A - Проверка пароля

В первой задаче нужно было аккуратно реализовать написанное в условии. Например, так:

string s;
cin >> s;
bool upper = false, lower = false, digit = false;
for(int i= 0; i < s.size(); ++i){
    if(isupper(s[i]))
        upper = true;
    if(islower(s[i]))
        lower = true;
    if(isdigit(s[i]))
        digit = true;
}
puts((upper && lower && digit && s.size() >= 5) ? "Correct" : "Too weak");

411B - Многоядерный процессор

В этой задаче важно было внимательно прочитать условие и разобрать несколько принципиальных случаев. Далее нужно было аккуратно реализовать в коде разбор случаев. Авторское решение делало это следующим образом:

1. Будем хранить массивы blockedCell[] (значение в ячейке i равно 1, если соответствующая клетка заблокирована, и 0 иначе), blockedCore[] (значение в ячейке i равно 0, если соответствующее ядро еще не заблокировано, и номеру такта, когда ядро заблокируется, иначе).
2. Будем итерироваться по тактам начиная с первого. Рассмотрим некоторый такт k.
3. Проходом по процессорам пересчитаем, какие ячейки заблокируются на такте k. Выставим в соответствующих ячейках массива blockedCell[] единицы.
4. Далее, для каждого ядра i, если выполняется условие ([blockedCore[i] равно 0] И [blockedCell[x[i][k]] равно 1]), тогда ядро i заблокируется на такте k. Запишем blockedCore[i] = k.

411C - Кикер

Для того, чтобы решить эту задачу нужно было воспользоваться логикой (математической логикой) :]. Логика подсказывает, что:

1. Если для какого-то расположения первой команды, не существует расположения второй команды, при котором она может гарантировать себе хотя бы ничью, тогда гарантированно выигрывает первая команда.
2. Если для любого расположения первой команды, существует расположение второй команды, при котором она может гарантировать себе победу, тогда гарантированно побеждает вторая команда.
3. Иначе, никто не может победить гарантированно, нужно вывести Draw.

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

Добрый день!

Напоминаю, что Квалификационный раунд Coder-Strike 2014 стартует очень скоро. Раунд будет проводиться по правилам ACM ICPC и будет нерейтинговым для всех участников. Для прохождения в следующий этап соревнования Coder-Strike 2014 достаточно будет решить хотя бы одну задачу.

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

Зарегистрироваться →Только для школьников Москвы и Московской области

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

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

UPD 1: Список официальных участников, которые зарегистрировались, находится по ссылке. Все участники, которые зарегистрировались, но не являются школьниками Москвы или Московской области не будут допущены к официальному участию в следующем раунде.

UPD 2: Регистрация для неофициальных участников открыта.

UPD 3: Напоминаю, что регистрация открыта до конца соревнования, не до его начала, как обычно.

UPD 4: Соревнование завершилось, надеюсь задачи вам понравились. Для тех, кому интересно, как решаются задачи, опубликован разбор задач.

Желаю всем удачи!

Завтра, 28-го июня 2013 года в 00:00 состоится Testing Round #7. Цель этого раунда — хорошенько протестировать платформу. Недавно было сделано много улучшений/нововведений. В частности, большая часть проекта Codeforces была перенесена на другой сервер.

Приглашаю вас принять участие. Раунд будет происходить по схеме Div.2 + неофициальное участие Div.1. Он будет состоять из трех задач, как определенная разминка — будет интересно всем. Я попрошу не участвовать тех, кто был на зимней школе в Харькове в этом году — вам эти задачи могут оказаться знакомы. Претесты в задачах будут необычно слабыми, чтобы спровоцировать побольше взломов. Конечно, раунд не будет влиять на рейтинг.

Спасибо всем, кто примет участие!

Upd. Раунд прошел удачно, огромная благодарность всем поучаствовавшим!

Всем привет!

Совсем скоро начнется очередной раунд Codeforces. Он пройдет по уже привычным вам правилам Codeforces.

Автор сегодняшнего раунда Михаил Граник (Fcdkbear), сейчас слушает лекцию в зимней школе по программированию в Харькове. Поблагодарим его за подготовленный контест!

Разбалловка на раунде будет стандартная: 500-1000-1500-2000-2500.

Всем удачи на раунде!

Доброго дня!

По техническим причинам было решено перенести трансляцию раунда на чуть позднее время. Трансляция будет проведена отдельным соревнованием КРОК-МВТУ 2012, Финальный раунд (Online версия, Div. 2), пожалуйста, регистрируйтесь на это соревнование.

Трансляция будет рейтинговым раундом для участников из Div. 2.

UPD. Совсем скоро начнется трансляция. Напоминанию, что соревнование будет проводиться по обычным правилам Codeforces. Разбалловка: 500-1000-1500-1500-2000.

Удачного контеста!

245A - System Administrator

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

    int[] accepted = new int[2];
    int[] lost = new int[2];
    for (int i = 0; i < n; i++) {
        int z = nextInt() - 1;
        accepted[z] += nextInt();
        lost[z] += nextInt();
    }

    for (int i = 0; i < lost.length; i++) {
        if (accepted[i] >= lost[i]) {
            out.println("LIVE");
        } else {
            out.println("DEAD");
        }
    }     

245B - Internet Address

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

    String s = nextToken();
    if (s.startsWith("http")) {
        out.print("http://");
        s = s.substring(4);
    } else {
        out.print("ftp://");
        s = s.substring(3);
    }

    out.print(s.substring(0, s.lastIndexOf("ru")));
    out.print(".ru");
    s = s.substring(s.lastIndexOf("ru") + 2);
    if (s.length() != 0) {
        out.print("/");
        out.println(s);
    }

245C - Game with Coins

У этой задачи было несколько решений, видимо, самое простое для осознание использует идею динамического программирования. Динамическое программирование dp[i][up], сколько нужно ходов, чтобы опустошить сундук номер i и все зависящие от него сундуки, при условии, что в нем сейчас находится max(0, a_i - up) монет.

Чтобы посчитать dp[i][up] переберем сколько раз мы возьмем монету из этого сундука. Пусть мы возьмем из него p, тогда должно выполняться max(0, a_i - up - p) = 0. Перебрав p переходим к подзадачам dp[2·i][p], dp[2·i + 1][p].

После подсчета всех состояний, ответ на задачу будет содержаться в dp[1][0].

Сколько операций выполнит подсчет такого динамического программирования. Очевидно, что p не имеет смысла брать более 1000. Тогда всего состояний в таком dp будет n·1000. Умножить на количество переходов, получается 100·1000·1000 = 10⁸, операций в худшем случае.

245D - Restoring Table

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

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j){
            cin >> b[i][j];
            if(i == j)
                continue;

            a[i] |= b[i][j];
        }

245E - Mishap in Club

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

    int in = 0, out = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == '+'){
            in++;
            out = max(out - 1, 0);
        }
        if(s[i] == '-'){
            out++;
            in = max(in - 1, 0);
        }
    }
    cout << in + out << endl;

245F - Log Stream Analysis

В этой задаче нужно было аккуратно распарзить входные данные. Перевести все даты в секунды. А затем, одним проходом по отсортированному массиву чисел, сделать ровно то, что написано в условии. Важно заметить, что размер входных данных был достаточно большим, поэтому читать эти данные нужно было достаточно быстро.

245G - Suggested Friends

В этой задаче планировалось решение за O(m²) с маленькой константой. Для начала предложим, что заданный во входных данных граф отношений связный, тогда количество вершин в нем n ≤ m + 1. Будем хранить такой граф в виде матрицы смежности a и ввиде списка смежных вершин для всех вершин. Теперь переберем вершину, которая будет общим другом предполагамых друзей. Далее переберем пару вершин, из списка смежных ей вершин, проверим, что они не соединены ребром, и сделаем инкремент в некоторую другую матрицу в ячейку b[u][v]. Эта матрица будет хранить количество, общих друзей между u, v, если u и v не соединены ребром.

После того, как мы построили матрицу b можно легко посчитать возможных друзей.

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

245H - Queries for Number of Palindromes

Решение задачи динамическое программирование. dp[i][j] — количество палиндромов в подстроке s[i...j], isp[i][j] — является ли палиндромом подстрока s[i...j]. Переходы dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + isp[i][j], isp[i][j] = 1, если isp[i + 1][j - 1] = 1, и s[i] = s[j]. Иначе isp[i][j] = 0.

Объявление: Все официальные участники, кто решил три и более задачи приглашаются 26 ноября в офис КРОК (ул. Волочаевская, 5) на финал Чемпионата. Победителей ждут призы, а подарки достанутся всем! Более подробная информация будет разослана по электронной почте.

Добрый день!

Совсем скоро начнется отборочный этап Чемпионата КРОК по программированию среди студентов МГТУ им. Баумана. В конкурсе принимают участие официальные участники чемпионата, все остальные будут в таблице результатов вне конкурса.

Соревнование проводится по широко известным правилам студенческого чемпионата мира по программированию ACM-ICPC. Продолжительность соревнования 2 часа. Допустимые языки программирования — C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml и D.

Раунд будет рейтинговым для див-2 участников независимо от того в конкурсе чемпионата участник или нет. Для див-1 участников раунд нерейтинговый.

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

Всем удачи!

UPD0. Соревнование завершено, всем большое спасибо за участие! Надеюсь, что проблемы с очередью не сильно испортили Вам впечатление от контеста. Завтра будут объявлены результаты отборочного раунда для участников в конкурсе. Рейтинг обновится совсем скоро.

UPD1. Появился разбор.

Добрый день, Codeforces!

Обратите внимание, что произошли существенные изменения в расписании соревнований! Соревнование Codeforces Round #148 перенесено на воскресенье, также добавлено новое соревнование Bayan 2012/13 Elimination Round.

Последнее является отборочным к BAYAN 2012/13, также оно обязательно будет рейтинговым для участников из Div1. Вопрос рейтинговости для участников из Div2 в данный момент решается. Не проходите мимо, регистрация начинается прямо сейчас!

Обратите внимание, что соревнование Bayan 2012/13 Elimination Round проводится по правилам ACM ICPC, также условия задач этого соревнования будут доступны только на английском языке.

Набирайтесь сил перед предстоящими соревнованиями! Всем Удачи!

Доброго дня, Codeforces!

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

Соревнование — индивидуальное, оно будет рейтинговым для обоих дивизионов.

Обратите внимание, что время начала соревнования отличается от обычного. Также обратите внимание, на необычную продолжительность соревнования.

До встречи на Codeforces Round #145! Надеюсь, что все найдут время поучаствовать в соревновании.

UPD. Соревнование закончено, скоро появится разбор.

Итак, начнём разбор.

219A - k-String

Давайте для каждой буквы l посчитаем, сколько раз она встретилась в строке --- массив c[l]. Подсчет осуществляется примерно так: c[s[i]]++. Если количество вхождений какой-то буквы не кратно k, то мы уже сразу понимаем, что составить нужную нам строку невозможно. Теперь построим строку p: добавим в неё букв 'a', букв 'b', и так далее. Выведем полученную строку k раз.

219B - Special Offer! Super Price 999 Bourles!

Переберем количество девяток на конце числа от 1 до 18. Пусть эта величина равна k. В таком случае максимальное число не превосходящее заданное p можно получить так:

• сотрем последние k цифр числа x:  = p / 10^k
• добавим справа k девяток y:  = x·10^k + 10^k - 1
• если значение y больше p, то уменьшим число x (то, что идет до k девяток) на 1 и к результату допишем k девяток y:  = (x - 1)·10^k + 10^k - 1

Если получившееся y >  = p - d, то обновим ответ значением k.

219C - Color Stripe

Разберём 2 два случая:

1. k равно 2. Тогда нам подходят только две строки — чередующиеся буквы 'A' и 'B'. Выбираем из них тот, который требует меньшего числа перекрасок.
2. k больше 2. Возьмем самый левый блок из одинаковых букв. Пусть его длина равна k, тогда надо не менее k / 2 перекрашиваний, чтобы избавиться от соседних одинаковых клеток в этом блоке. Если k нечетно, то можно каждую вторую клетку в блоке перекрасить в любой из цветов, отличных от цвета блока. Если k четно, то можно делать тоже самое, но аккуратнее выбрать цвет: он должен отличаться не только от цвета блока, но и от цвета следующей клетки за блоком. Это всегда возможно сделать, так как количество цветов больше 2.

219D - Choosing Capital for Treeland

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

В задаче были достаточно большие ограничения, поэтому нельзя было просто посчитать все эти значения n обходами в глубину. Авторское решение запускает только два обхода в глубину. Первым обходом в глубину посчитаем ответ для города номер 1. Заметим, что если посчитан ответ для вершины x, то ответ для вершины y, которая соединена с x, можно посчитать за O(1). А именно, ans(y) = ans(x) - direction(x, y) + (1 - direction(x, y)), где direction(x, y) — равно 1, если ребро (x, y) ориентировано не так как во входных данных, и равно 0, иначе.

Пользуясь описанным фактом, можно посчитать все значения ans(v) одним обходом, зная ans(1).

Итоговая ассимптотика решения O(n).

219E - Parking Lot

Будем поддерживать две структуры: множество отрезков свободных парковочных мест, в котором отрезки отсортированы по их началу, и множество отрезков свободных парковочных мест отсортированных по размеру. Такие структуры должны поддерживать операцию быстрого поиска первого больше либо равного элемента, удаление элемента и его вставку, нахождениe максимума и следующего по величине элемента.

В языке C++, авторское решение использовало set <pair<int,int>> и map <int, set<int>>. Set отрезков и Map из длины отрезка в набор отрезков с заданной длиной. Операция поиска больше либо равного элемента в этих структурах называется lower_bound.

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

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

Отдельные случаи возникает при рассмотрении крайних отрезков.

Итоговая сложность решения O(m log n)

Доброе утро, Codeforces!

Разбираясь с задачей C(Div1), E(div2) я пришел к выводу, что авторское решение неверное, за что приношу вам всем огромные извинения.

Однако, как выяснилось, все претесты были верными, а некорректных взломов было очень мало (всего 3). Обсудив все с MikeMirzayanov, мы приняли такое решение:

• Для Div2 задача E почти никак не влияет на результаты соревнования (взломов по ней не было, да и сабмитов было мало), поэтому для Div2 раунд будет рейтинговым.

• Для Div1, контест можно будет считать рейтинговым, только если у этой задачи найдется какое-либо правильное приемлемое (в смысле времени его работы) решение. Я потратил всю ночь на поиски этого решения, но увы ничего хорошего у меня не вышло, поэтому предлагается силами сообщества побороть эту задачу (если это вообще возможно). Если в течение дня, то есть спустя 24 часа после публикации этого поста, не найдется правильное решение, Div1 контест будет нерейтинговым.

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

Обратите внимание, что задача появилась в архиве задач. Сейчас все тесты к ней корректные, так что вы можете попробовать сдать решение в архив.

UPD: 24 часа прошло. К сожалению, никто не написал правильного решения или близкого к нему. Div1 раунд объявляется нерейтинговым. Огромное спасибо всем тем, кто приложил свои усилия и попробовал решить эту задачу.

С уважением, Агапов Геральд.

Добрый день, Codeforces!

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

Буду очень признателен любым методам подсчета быстрее чем линия (или около-линия).

Доброго дня, Codeforces!

Напоминаем, что в 17:15 начнется финал Открытого чемпионата Москвы и МО по программированию (КРОК).

Как обычно в соревновании смогут принять участие все желающие. Но поскольку соревнование достаточно сложное, оно будет рейтинговым только для участников из Div.1.

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

Доброго дня, Codeforces!

Сегодня, 19:00 начнется первый раунд Открытого чемпионата Москвы и МО по программированию (КРОК).

Это будет обыкновенный двухчасовой Codeforces раунд со взломами и падением баллов во время соревнования. В Раунд 1 допускаются все, кто прошел Квалификацию и зарегистрировался на соревнование. Также вне конкурса допускаются к участию все остальные зарегистрировавшиеся на раунд. Как обычно, раунд будет рейтинговым для всех. Для прохождения в Раунд 2, Вам нужно набрать не меньше баллов, чем участник на 300-ом месте (при условии положительного числа набранных баллов).

В раунде вас ждут несколько задач, примерно расположенных по возрастанию сложности. Разбалловка за задачи стандартная (500-1000-1500-2000-2500). Во время раунда задачи тестируются системой только на претестах, а системное тестирование состоится после окончания соревнования. Претесты не покрывают все возможные случаи входных данных, так что тщательно тестируйте свои программы!

До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия и проч. Будьте честными и пусть в Раунд 2 пройдут сильнейшие. После того как раунд завершится, можно будет обсуждать задачи и решения.

Хочется отдельно отметить, что раунд может показаться сложным для участников из div2. Не забывайте, что рейтинг будет пересчитан только для тех участников, которые сделают хотя бы одну посылку по задаче.

В подготовке сегодняшнего раунда участвовали: Ripatti, havaliza, haas, RAD, Gerald, MikeMirzayanov, Delinur. Огромное всем им спасибо за проделанную работу!

Всем удачного Раунда!

152A - Оценки

В этой задаче нужно было сделать ровно то, что написано в условии. Вот приблизительный код решения.

for (int i = 0; i < n; ++i){   
    bool wasBest = false;
    for(int j = 0; j < m; ++j){
        bool isBest = true;
        for(int k = 0; k < n; ++k)
            if(a[k][j] > a[i][j])
                isBest = false;
        if(isBest)        
            wasBest = true;
    }
    if(wasBest)
        ans++;
}      

152B - Шаги

В этой задаче нужно бюло посчитать формулу — для позиции (x, y) и вектора (dx, dy), сколько шагов до упора может сделать мальчик. Эту же величину можно было считать пользуясь "почти" бинарным поиском. Ниже приведу код вычисления этой величины, написанный RAD.

for (long long cof = 1100000000; cof; cof /= 2)
    while (onField(xc + cof * dx, yc + cof * dy)) {
        xc = xc + cof * dx;
        yc = yc + cof * dy;
        ans += cof;
    }      

152C - Записная книжка

В этой задаче нужно было заметить, что на месте первого имени можно получить любое имя специального вида. А именно, любое имя вида s = s₁ s₂ s₃ s₄ ... s_m, где s₁ — первый символ любого из заданных имен, s₂ — второй символ любого из заданных имен, ... s_m — m-й символ любого из заданных имен. Тогда ответ на задачу — это произведение cnt_i (1 ≤ i ≤ m), где cnt_i — это количество различных букв стоящих в именах на позиции i.

152D - Рамки

Нужно было понять: нарисовано ли на картинке две рамки.

Так как у рамок длина стороны была не менее 3, то давайте выделим те x- и y-координаты, на которых встречаются хотя бы 3 подряд идущих символа '#'. Понятно, что координаты углов рамок следует выбирать только из этих выделенных x и y. В общем случае различных выделенных x не более 4, и различных выделенных y не более 4.

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

Например:

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

Первая рамка:

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

Вторая рамка:

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

В примере различных y-координат 7.

Аккуратно обработаем такие случаи отдельно, что вполне просто. (Оставим всего 4 y-координаты: минимум, максимум, второй минимум и второй максимум).

Иначе, если количество выделенных x- и y-координат не более 4, то переберем углы первой первой и второй рамки и проверим, что выбранные рамки — корректные рамки и нет лишних символов '#'. Проверка осуществляется за O(n + m) или за O(1) (с использованием частичных сумм).

152E - Сад

Задача решалась динамическим программированием. Пусть dp[mask][v] — это стоимость минимального корректного покрытия бетоном, если мы рассматриваем в качестве важных элементов только элементы маски mask и покрытие дополнительно покрывает вершину v = (i, j) поля.

Есть два вида переходов.

Во-первых мы можем, как бы разрезать покрытие по вершине v. Тогда нужно перебрать подмаску вершин submask, которые уйдут в левое покрытие и сделать соответсвующий переход. Обновить dp[mask][v] значением dp[submask][v] + dp[mask ^ submask][v] - cost(v).

Во-вторых, возможно, в данной вершине v в оптимальном покрытии маски mask, захватывыющим вершину v, нельзя сделать разрез разделяющий множество вершин. В таком случае, эта вершина образует своеобразный <<хвост>>. То есть существует такая вершина u, в которой можно сделать разрез, при этом кратчайший путь из вершины u в v целиком принадлежит оптимальному покрутию. Преподсчитаем заранее кратчайшие пути между всеми парами клеток. Теперь чтобы сделать этот переход, первоначально посчитаем значение динамики dp[mask][v] для всех вершин v только с учетом первого перехода. Теперь можно делать второй переход. Для всех u, dp[mask][v], обновить значением dp[mask][u] + dist(v, u) - cost(u).

Отдельно нужно обработать состояние, в котором ровно один бит в маске, при этом вершина соответсвующая этому биту равна v. В таком случае ответ, понятно, равен cost(v).

Таким образом, каждое получается решение за O(min(3^k·n·m, 2^k·(n·m)²)).

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

UPD: Разбор задач

Всем привет! Меня зовут Геральд Агапов. Я учусь в Саратовском государственном университете. Сегодня я предоставляю вам набор, надеюсь, интересных задач. Желаю всем удачи!