Чемпионат

Чемпионат VK Cup — это открытый чемпионат по программированию, проводимый компанией ВКонтакте, проектом Codeforces и Саратовским государственным университетом. Финал чемпионата пройдет в июле в Санкт-Петербурге. Лучшие 50 участников по результатам третьего отборочного раунда будут приглашены на финал соревнования. Расходы по проезду и проживанию берут на себя организаторы чемпионата.

Участники

Вы молоды и любите решать задачи по программированию? Этот чемпионат для вас! Участником чемпионата может стать любой желающий, кто удовлетворяет следующим требованиям:

• возраст не менее 14 и не более 23 полных лет на момент регистрации;
• не является сотрудником компании ВКонтакте и/или членом оргкомитета или жюри чемпионата;
• не является дисквалифицированным членом сообщества Codeforces.

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

Соревнование индивидуальное, участие в какой-либо коллективной форме не допускается.

Ну что, делимся впечатлениями, признаемся, кто участвовал, в какой команде и что нарешал? Ужасно не хватает более детальной информации по контесту — стран участников и общего балла явно недостаточно :-)

Список команд:

И немного впечатлений от Progopedia в моем лице.

Всем привет. Меня зовут Михаил Тихомиров, и сегодня я — автор раунда. При подготовке задач мне очень помогли Геральд Агапов (Gerald) и Артем Рахов (RAD), условия на английский язык перевела Мария Белова (Delinur), за что им от меня огромное спасибо.

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

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

Раунд завершился, всем спасибо!

Результаты:

div1:

1. tourist
2. peter50216
3. Egor
4. YuukaKazami
5. gchebanov
6. kelvin
7. shangjingbo
8. rowdark
9. kterry
10. rng_58

div2:

1. jonathanasdf
2. Tranvick
3. ProForward
4. Eurekash
5. neex.emil

Теперь полный разбор здесь.

Итак, разбор задач. Я старалась подбирать задачи так, чтобы каждая из них раскрывала какой-то аспект языка — особенность или часто используемый глагол. Если участник его узнавал/нагугливал, задача должна была стать очевидной.

153A - A + B

Сразу скажу, что приведенный в посте пример работет и в Custom test, и в ideone, и локально — если вводить числа по одному на строку и (внимание!) после второго тоже поставить перевод строки. Этот последний перевод строки не отображается в тестах, но на самом деле он там есть! И для COBOL это важно. Все тесты на Codeforces сгенерированы аккуратно, с переводом строки всюду, где нужно, поэтому при сабмите проблем возникать не должно было.

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

Раунд окончен, надеюсь, вам понравилось. Разбор задач здесь.

Язык этого раунда — COBOL (диалект COBOL85), один из старейших языков программирования (1959 год "рождения", то есть вдвое старше меня). Несмотря на почтенный возраст, до сих пор активно используется, но не в спортивном программировании, так что для присутствующих должен стать сюрпризом :-)

Задача "A+B" (числа A и B заданы в отдельных строках) решается вот так:

       IDENTIFICATION DIVISION.
       PROGRAM-ID. SOLUTION.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 A        PIC 9(10)   VALUE ZEROES.
       01 B        PIC 9(10)   VALUE ZEROES.
       01 STR      PIC X(10).

       PROCEDURE DIVISION.
         ACCEPT STR
         MOVE STR TO A
         ACCEPT STR
         MOVE STR TO B
         ADD A TO B
         DISPLAY B
         STOP RUN.

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)²)).

Добрый день!

Мы успешно пережили уже две недели нового семестра и рады поприветствовать вас на очередном рейтинговом раунде Codeforces для участников Div. 2. В нем как всегда могут принять участие все желающие.

Этот раунд подготовлен командой из трех человек: Gerald, NALP и Polichka. Мы благодарим за помощь в подготовке раунда и переводе задач Артема Рахова (RAD), Михаила Мирзаянова (MikeMirzayanov) и Марию Белову (Delinur).

Сегодня Петя запутался в таблицах:-( И вы можете помочь ему! Это же так просто!

Распределение баллов по задачам следующее: 500-1000-1500-2500-2500

Всем легких решений и высокого рейтинга!

UPD:

Всем спасибо за участие!

Разбор задач доступен по ссылке: Разбор задач

150E - Замерзаем красиво

Идея:

1. Сделаем бинарный поиск по ответу. Пусть мы хотим проверить существование пути с медианой Mid.

2. Если ребро  ≥ Mid положим его вес равным  + 1, иначе  - 1. Теперь надо проверить существование пути не отрицательного веса, у которго длина  ≥ l и  ≤ r. Назовем такой путь хорошим.

3. Подвесим дерево за какую-то вершину V.

4. Сначала предположим, что путь проходит через V. Затем удалим эту вершину и сведем задачу к нескольким меньшим.

5. Если в качестве вершины V выбирать центр дерева (такую вершину, что после подвешивания за нее, размер всех поддеревьев не превохсодит половины размера всего дерева), то таких шагов будет не более Log(N).

6. Т.е если мы сейчас научимся за O(F(N)) проверять наличие хорошего пути, то мырешим задачу за сложность O(F(N) * log²(N)).

7. Для начала научимся ее решать за O(NLog(N)). Для каждой вершины посчитаем ее глубину, стоимость пути от нее до корня, и первое ребро на пути от корня до нее. Вершины будем обрабатывать пачками, в одну пачку попадают вершины с одинаковым первым ребром. Это сделано чтобы все учтенные пути были простыми. Сначала для каждой вершины из пачки вычислим максимальную стоимость хорошего пути, начинающегося в ней, проходящего через корень, и заканчивающегося в вершине из уже обработанной пачки. В силу того, что мы обрабатываем вершины пачками, условие прохождения через корень выполнится автоматически. Построим дерево отрезков на массиве q[x] =  максимальная стоимость пути длиной x начинающегося в корне. Тогда для нашей вершины искомая величина это просто максимум на отрезке с L - dep по R - dep. Затем после обработки всей пачки сделаем апдейты в дереве интервалов.

8. Чтобы получить АС нужно было очень аккуратно написать это решение (его сложность O(N * log³(N)) ~ 8 * 10⁸ операций или заметить, что можно заменить дерево отрезков очередью с максимумом.

150D - Миссия непроходима

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

Состояния:

Best[l][r] — лучший результат который можно получить на подстроке с l по r.

Full[l][r] — лучший результат который можно получить на подстроке с l по r, при этом удалив ее полностью.

T[l][r][Len] — лучший результат который можно получить на подстроке с l по r, чтобы в результате получился палиндром длины ровно Len и больше ничего.

Переходы:

1. Full[l][r]. Давайте посмотрим какой ход мы сделаем последним. Это будет удаление палиндрома какой-то длины len, причем c[len] ≥ 0. Какой результат мы в итоге получим? c[len] + T[l][r][len], где T[l][r][len] — это оптимальный способ оставить на отрезке только палиндром длины len.

2. Best[l][r]. Либо мы удалим отрезок целиком, либо существует буква, которую мы не трогали. Но тогда каждый удаляемый палиндром лежит либо строго слева либо строго справа от этой буквы. Другими словами можно решать задачу независимо для левой половины и правой. Получаем что либо Best[l][r] = Full[l][r] либо Best[l][r] = Best[l][m] + Best[m + 1][r] для какого-то m, l ≤ m < r.

3. T[l][r][len]. len = 0, len = 1 — два частных случая, которые надо рассмотреть отдельно. В общем же случае давайте посмотрим на самую левую букву. Она либо войдет в оставшийся в результате палиндром либо нет. Если нет, то переберем позицию m (l < m ≤ r) самой левой буквы которая войдет в ответ. Все что находится слева от нее необходимо полностью удалить, из оставшейся строки все еще нужно оставить палиндром длины len. Получили Full[l][m - 1] + T[m][r][len] (for l < m ≤ r). Аналогично для самой правой буквы. Если она не войдет в ответ, то мы целиком удалим какой-то суффикс нашего отрезка. Получаем T[l][m][len] + Full[m + 1][r] (for l ≤ m < r). Остался последний вариант: и самая левая и самая правая буквы войдут в ответ, но тогда они обязаны совпасть. Значит в случае когда s[l] = s[r] мы можем их обе оставить и набрать оптимально палиндром на 2 символа короче на отрезке с l + 1 по r - 1. Получаем последний переход T[l + 1][r - 1][len - 2] (if s[l] =  = s[r]).

150C - Хитрый жук

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

2. Для каждого маленького отрезка пути (перегон между соседними станциями) посчитаем матожидание заработка если мы не продадим билет на него.

3. Теперь, когда нам нужно решить задачу для пассажира едущего с L до R, на самом деле надо найти под отрезок с максимальной суммой.

4. Это можно сделать например при помощи дерева интервалов. Каждая вершина дерева покрывает какой-то отрезок массива с l по r. Будем в ней хранить следующие величины: префикс с максимальной суммой, суффикс с максимальной суммой, сумму на всем отрезке и просто лучший результат. Для отрезка длины 1 все эти величины вычисляются очевидным образом. И в то же время, зная все эти величины для обоих сыновей вершины, мы с легкостью можем пересчитать значения в нашей.

150B - Количество строк

У задачи есть два принципиально разных решения:

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

2. Разобрать четыре случая:

   • k = 1 или к > n ответ mⁿ.
   • k = n ответ m^{(n + 1) / 2}.
   • k mod 2 = 1 ответ любая строка вида abababab..., т.е. ответ m².
   • k mod 2 = 0 все символы в строке совпадают, т.е. ответ m.

150A - Победи или замерзни

• Если Q — простое или Q = 1 то первый игрок уже выиграл.

• Проигрышные позиции: p * q и p², где p и q — простые.

• Вполне очевидно, что из всех остальных позиций мы можем сделать ход в одну из проигрышных. Значит они выигрышные.

Остается лишь аккуратно проверить, что у нашего числа есть делитель удовлетворяющий условию проигрышности. Это можно сделать за O(sqrt(Q)) факторизовав наше число.

151B - Телефонные номера

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

151A - Газировкопитие

Газировки хватит на gas = (K * L) / (N * l) тостов.

Лаймов хватит на laim = (C * D) / N тостов.

Соли хватит на sol = P / (p * N) тостов.

Итого ответ: res = min(gas, laim, sol).

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

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

Тем кто будет писать раунд предстоит окунуться в атмосферу ледяного февраля в городе XXXvodske и помочь компании друзей не умереть от холода. Помните, какая ответственность на вас лежит)

Пользуясь случаем хотелось бы поблагодарить всю команду Codeforces за то большое дело, которое они делают, Артема Рахова (RAD) за помощь в подготовке задач, Марию Белову (Delinur) за перевод условий на английский язык, маму, папу, нашего звукооператора и виноделов провинции Тоскана за то, что мы не заболели и смогли готовить для вас этот раунд.

Разбалловка ожидается следующая:

div. 1: 500-500-1000-1500-3000 (да-да, последняя задача того стоит)

div. 2: 500-1000-1500-1500-3000

Good luck & have fun!

149A - Командировка

Во-первых, ясно, что если сумма всех чисел a_i меньше, чем k, то Петя в любом случае не сумеет вырастить цветок до нужной высоты, и следует вывести <<-1>>.

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

149B - Марсианские часы

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

До какой величины следует перебирать основание? На самом деле, достаточно до 60, потому что 60 – верхнее ограничение на допустимые числа. Это следует из того, что если число в неизвестной системе счисления состоит из одного знака, то ее значение в десятичной не меняется никогда, а иначе его значение не меньше основания.

Также стоило разобрать случай с ответом <<-1>>, для этого, например, можно было проверить большое основание, например 100, и если для даже для него время корректно, то и для всех больших оно тоже корректно и ответ равен <<-1>>.

149C - Разделение на команды

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

Первые два требования очевидно выполняются.

Для доказательства третьего рассмотрим геометрическое представление: пусть каждый мальчик обозначается точкой на оси X со значением, равным его умению играть. Соединим отрезками точки с номерами 1 и 2, 3 и 4, и так далее. Если n нечетно, то соединим эту точку с ближайшей предыдущей.

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

149D - Раскрашивание скобок

Введем обозначения цветов: 0 – черный, 1 – красный, 2 – синий. Заметим, что у отдельно взятой пары скобок всего 4 варианта раскраски: 0-1, 1-0, 0-2, 2-0.

Рассмотрим динамическое программирование, где состояние имеет вид – (l, r, c_l, c_r), где пара (l, r) задает одну из пар скобок, а с_l и c_r означают фиксированные для них цвета. Значением динамики является количество способов раскрасить все скобочки внутри отрезка (l, r) с соблюдением всех условий.

Выпишем все пары скобок, которые вложены непосредственно в пару (l, r), пусть их k штук. Причем, будем рассматривать только первый уровень вложенности, именно непосредственно вложенные. Для того, чтобы подсчитать значение динамики для состояния, внутри этого состояния будем подсчитывать еще одну динамику, где состояние – это пара (i, c) которое означает количество правильных раскрасок первых i непосредственно вложенных скобок и всех внутри них, если последняя закрывающая скобка имеет цвет c. Пересчитывать такую динамику вперед очень просто – попробуем раскрасить (i + 1)-ую скобочку в один из четырех вариантов, учитывая возможные конфликты. У такой динамики начальным состоянием является пара (0, c_l), а итоговый результат – сумма по состояниям вида (k, c), где c не должно конфликтовать с c_r.

Ответ на всю задачу считается аналогично внутренней динамике. Асимптотика решения – O(n²) с коэффициентом порядка 12.

149E - Марсианские строки

Будем решать задачу отдельно для каждой из m строк. Итак, пусть у нас есть строка p, ее длина l, и нам нужно проверить, может ли марсианин ее увидеть.

Введем дополнительные массивы: пусть pref[i] – минимальная позиция в s начала вхождения префикса строки p длиной ровно i, а также пусть suff[j] – максимальная позиция в s конца вхождения суффикса строки p длиной ровно j.

Нетрудно понять, что марсианин сможет увидеть p, если существует такое i, что suff[l - i] ≥ pref[i] + l–1.

Как подсчитать массивы? Для массива pref достаточно найти Z-функцию строки p#s, а для массива suff – Z-функцию строки r(p)#r(s), где r(t) означает перевернутую строку t. Используя массив Z-функций значения массивов suff и pref подсчитать тривиально.