Розбір завдань відбіркового раунду RCC 2015



В неділю 14 червня пройшов відбірковий раунд RCC 2015. За звання фіналіста RCC 2015 воювали 604 програміста, що пройшли кваліфікацію в попередніх трьох раундах. Хоча б одне правильне рішення надіслали 324 учасника. А тепер герої раунду! Петро Мітрічев посів першу сходинку турнірної таблиці, першим вирішивши завдання B (Розбивка на команди) і F (Освітлення сцени) за 20:32 1:31:41. Геннадій Короткевич йде другим — він першим за 2 хвилини і 30 секунд вирішив задачу A (Гра з рядками) і раніше за всіх справився з завданням D (Декартові дерева) за 14:16. Makoto Soejima з Японії — третій, судячи з усього перед рішенням він перекладав умови завдань через онлайн-перекладач. Михайло Пядеркин перший вирішив задачу C (Карта) за 51 хвилину 4 секунди. Єгор Куліков першим вирішив задачу E (Алея) за 1 годину 5 хвилин і 49 секунд. За підсумками відбірного раунду до фіналу вийшли 50 учасників. 19 вересня у Фіналі визначиться найсильніший програміст року! Всі учасники відбіркового раунду отримають онлайн-сертифікати, а 200 кращих з них отримають футболки RCC 2015.

Завдання A. Гра з рядками
Ідея: Григорій Шовкопляс
Реалізація: Григорій Шовкопляс
Розбір: Григорій Шовкопляс

У задачі дано рядок, з якої можна робити наступні операції:
  • видалити три поспіль йдуть одиниці;
  • видалити два поспіль йдуть нуля;
  • замінити підрядок «
    01
    » на підрядок «
    10
    »;
  • замінити підрядок «
    10
    » на підрядок «
    01
    ».
Потрібно порахувати, скільки існує способів отримати рядок певної довжини з даної, застосовуючи ці операції.

Для початку подивимося на операції замін і зрозуміємо, що це не що інше, як swap. Таким чином, ми можемо отримати з цього рядка будь-яку, в якій міститься така ж кількість нулів і одиниць. Тепер з допомогою цих операцій отримаємо з вихідної рядок, де всі нулі стоять на початку, а одиниці в кінці. З отриманої рядка ми можемо отримати рядок нової довжини, нічого не переставляючи, так як всі одиниці і нулі вже згруповані. Рядок довжини k можна отримати з рядка довжини n, видаливши 3x одиниць і 2y нулів, де k = n — (3x + 2y). Значення x y можна перебрати. І нарешті, для кожної отриманої рядка потрібної нам довжини потрібно врахувати всі перестановки. Їх можна порахувати, наприклад, як кількість поєднань з довжини рядка за кількістю одиниць в ній. Відповідь буде дорівнювати сумі цих поєднань для всіх рядків потрібної довжини, які можна отримати з даної.

Завдання B. Розбивка на команди
Ідея: Григорій Шовкопляс
Реалізація: Дмитро Філіппов
Розбір: Дмитро Філіппов

У задачі дано граф, на кожному ребрі якого написані числа від 0 до 1, що означає, що кінці ребра одного кольору або різного відповідно. Також деякі вершини графа пофарбовані в білий або чорний колір. Питається, чи можна як-небудь пофарбувати в чорний і білий кольори інші вершини, щоб інформація, написана на ребрах, була вірна, і кількість вершин чорного і білого кольору було однаковим?

Розіб'ємо наш граф на компоненти зв'язності. Зауважимо, що, знаючи колір однієї вершини в компоненті, ми можемо відновити колір всіх інших. З цього випливає, що якщо в компоненті хоча б одна вершина вже пофарбована, розфарбування всій компоненти єдина (крім випадку, коли в отриманій розфарбуванні порушиться якийсь з необхідних умов, тоді відповідь на завдання — «
NO
»). Якщо ж ні одна вершина ще не пофарбована, варіантів розмальовки два — можна пофарбувати будь-яку вершину компоненти в білий колір, відновити кольори інших вершин, а після цього, якщо їх інвертувати — отримаємо другу розмальовку.

Нескладно помітити, що ми звели нашу вихідну задачу до задачі про рюкзак: з кожної компоненти ми можемо взяти деяку кількість білих вершин, і всього їх треба набрати n ⁄ 2 (якщо n непарне, відповідь на завдання — «
NO
»). А це вже можна вирішити за допомогою динамічного програмування за O(n2).

Завдання C. Карта
Ідея: Георгій Корнєєв, Віталій Аксьонов
Реалізація: Віталій Аксьонов
Розбір: Віталій Аксьонов

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

Розглянемо спочатку найпростішу версію завдання. Дано прямокутник, і потрібно його скласти, отримавши мінімальну площу. Очевидно, що його треба складати по лінії сітки, найближчій до середини (якщо дві, то можна скласти за будь -). Розглянемо функцію площі від позиції згину. Для прямокутника з кутами (x1, y1) та (x2, y2) ця функція має наступний вигляд:
  • на відрізках (-∞; x1] [x2; +∞) функція дорівнює площі прямокутника;
  • на відрізку [x1; (x1 + x2) / 2] функція лінійно зменшується з коефіцієнтом y2 — y1;
  • на відрізку [(x1 + x2) / 2; x2] функція лінійно зростає з коефіцієнтом y2 — y1.
Загальна: функція змінює свій стан тільки в трьох точках. Між двома підряд йдучими точками функція є лінійною.

Зауважимо, що, так як наша задача дискретна, у разі, коли (x1 + x2) не ділиться на два, краще бити функцію на п'ять ділянок між точками x1, ⌊(x1 + x2) / 2⌋, ⌈(x1 + x2) / 2⌉ x2.

Нехай наш багатокутник задано n вершинами. Тоді нескладно помітити, що опуклий картатий багатокутник можна нарізати на не більш ніж n прямокутників горизонтальними прямими. Тоді функція залежності від площі місця складання буде сумою функцій для прямокутників. Знову ж неважко переконатися, що якщо ми візьмемо всі точки зміни для кожної функції і відсортуємо їх, то між двома сусідніми точками глобальна функція буде лінійною. Тоді в якості відповіді потрібно взяти мінімум із значеннями в цих точках.

Щоб це реалізувати, потрібно скористатися ідеєю подій. Кожна подія буде відповідати точці зміни функції для якогось прямокутника. Тоді обробляючи події зліва направо і перераховуючи коефіцієнт лінійної функції, нескладно порахувати функцію у вибраних точках.

Завдання D. Декартові дерева
Ідея: Артем Васильєв
Реалізація: Ілля Збань
Розбір: Ілля Збань

У задачі дано n чисел yі, потрібно було порахувати, скільки декартових дерев можна побудувати на множині (i, yі). Для початку зауважимо, що якщо всі n чисел yi дорівнюють одному й тому ж числу, то відповідь — Cn, n-е числа Каталана. Зрозуміти це можна, наприклад, виходячи з рекурентної формули: якщо в ліве піддерево визначити k вершин, то в правому виявиться n-k-1 вершин, тобто Cnk=0n Ck·Cn-k-1. Розглянемо всі входження максимального числа в масиві. Будь-яка вершина з таким пріоритетом може бути або коренем, або бути дитиною іншої вершини з таким же пріоритетом. Нехай входження максимуму мають індекси a1, a2, ..., ak. Тоді ми повинні побудувати якесь декартів дерево на вершинах a1, a2, ..., ak, і підвісити до нього якісь декартові дерева, побудовані на вершинах (1, ..., a1-1), (a1+1, ..., a2-1), ..., (ak+1, ..., n). Зауважимо, що для сусідніх aі ai+1 в будь-якому декартовом дереві, побудованому лише на максимальних вершинах, одна з цих вершин буде предком іншою, тому дерево, побудоване на вершинах (aі+1, ..., ai+1-1)ми зможемо однозначно підвісити за одну з цих двох вершин.

Таким чином, число способів побудувати декартів дерево на вершинах l r дорівнює cnt(l, r)=Ck · cnt(l, a1-1) ·… · cnt(ak+1, r). Відповіддю буде cnt(1, n).

Завдання E. Алея
Ідея: Борис Мінаєв
Реалізація: Борис Мінаєв
Розбір: Борис Мінаєв

З математичної точки зору, у задачі дано відрізки цілочисельний довжини. Необхідно розбити деякі з них на більш дрібні так, щоб довжина найбільшого відрізка була якомога менше, а кількість розбиття не перевищувала заданого числа. Завдання дещо ускладнюється тим, що сумарна довжина всіх відрізків може досягати 109, а кількість запитів, на які необхідно дати відповідь, може досягати 106.

Розглянемо, скільки необхідно зробити розбиття, щоб відповідь вийшов не більше Ans. Для кожного відрізка довжини Len необхідно зробити (Len — 1)/Ans розбиття (результат ділення округлюється). Побудуємо функцію кількості необхідних розбиття від відповіді для кожного відрізка. Складемо ці функції для всіх відрізків. Для того, щоб знайти мінімальне значення Ans, яке можна досягти, зробивши не більше ніж K розбиття, скористаємося двійковим пошуком.

Будемо зберігати функції в стислому вигляді, а саме — збережемо значення функції для Ans тільки якщо f(Ans) ≠ f(Ans-1). Можна довести, що для відрізка довжини Len потрібно O(sqrt(Len)) пам'яті, щоб зберегти його функцію. Позиції, в яких змінюється значення функції, можна визначити за час, пропорційний їх кількості. Максимальне сумарне число позицій зміни буде досягатися на тесті, в якому всі відрізки мають однакову довжину. У разі обмежень, які дані в умові задачі, їх кількість не може перевищувати 106·sqrt(103)=107.5.

Щоб об'єднати декілька функцій, які зберігаються в стислому форматі, необхідно відсортувати всі моменти зміни функцій. Для цього розіб'ємо всі позиції, які змінюються, на два класу. У перший клас віднесемо всі позиції, які менше 106. Їх можна відсортувати підрахунком за час, пропорційний їх кількості. Інших же позицій буде небагато, і для їх сортування можна використовувати вбудовані функції мови. Щоб переконатися, що кількість позицій, які більше 106, невелика, зробимо наступне. Для того, щоб відрізок максимальної довжини не перевершував 106, досить зробити не більше Len/106 відрізків розбиття. Оскільки в умові задачі сумарна довжина відрізків не перевершує 109, то кількість змін функції, позиції яких перевершують 106, буде менше 1000.

Завдання F. Освітлення сцени
Ідея: Артем Васильєв
Реалізація: Артем Васильєв
Розбір: Артем Васильєв

У цій задачі з досить заплутаним умовою дан масив пар (потужність, безліч виходів), та для кожної лівої кордону в масиві потрібно знайти мінімальну праву кордон, щоб на цьому подмассиве існувало підмножина пар з наступними умовами:
  1. Сума потужностей повинна бути не менше Z.
  2. Безлічі виходів вибраних прожекторів попарно не перетинаються.
Подмассив з такими властивостями будемо називати гарним. Для початку вирішимо завдання для однієї фіксованої лівої межі. Таку задачу можна вирішити за допомогою динамічного програмування за двійковим масок: dpmask — це максимальна вартість прожекторів, для яких об'єднання множин виходів є підмножиною mask. Формула перерахунку для додавання одного елемента (p, m) виглядає так: dp'mask = max(dpmask, dpmask — m + p), якщо m є подмаской mask, і dpmask — інакше. Додавання одного елемента можна реалізувати зат(2k). Коли dp2k — 1 стає більше або дорівнює Z, треба видати відповідь.

Легко довести, що при зростанні лівої межі відповідна права межа не убуває. Це дозволяє використовувати техніку двох покажчиків для знаходження відповіді. Для реалізації техніки двох покажчиків необхідно реалізувати структуру даних, яка підтримує наступні операції:
  1. Додати елемент в кінець.
  2. Видалити елемент з початку.
  3. Відповісти на запит: «чи Є поточне безліч прожекторів хорошим?».
Рішення даної задачі використовує реалізацію черзі на двох стеках з ідеями методу реалізації черзі з мінімумом. Аналогічно черзі з мінімумом, будемо зберігати в стеках не просто елементи, а пари (елемент; масив dpі, в якому містяться значення ДП для елементів з поточного і нижче). Додавання одного елемента в такий стек можна виконати за O(2k), видалення за O(1). Остаточно, використовуючи таку модифікацію стека в черзі, можна відповідати на запит типу 3 O(2k): відповідь на нього позитивний тоді і тільки тоді, коли maxi = 0..2k — 1 dp1і+dp22k — 1 — i ≥ Z, dp1, dp2 — масиви значень ДП на вершині першого і другого стека, відповідно.

У висновку, згадуючи, що кожен елемент в результати роботи черги, реалізованої на двох стеках, переміщується O(1) раз, отримуємо, що рішення працює за O(n2k) часу і використовує O(n2k) пам'яті.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.