Відбірний раунд Russian Code Cup 2014: підсумки та розбір задач

    
 
Минулої неділі відбувся відбірковий раунд Russian Code Cup 2014 . У ньому брало участь 802 програміста, що показали кращі результати в чотирьох кваліфікаціях. У цьому етапі учасникам належало за 3 години вирішити шість завдань, що на одну годину і на одну задачу більше, ніж у кваліфікаційних раундах. Та й завдання були істотно складніше, ніж попередні. За час змагання з 802-х тільки 444 учасника змогли вирішити хоча б одну задачу. Всього було відправлено 3271 рішення, з них правильних 1402.
 
Найбільше рішень на GNU C + + — 1516.
Рішень на Java 7 — 333.
Рішень на Java 8 — 106.
 
Першим задачу A вирішив Геннадій Короткевич (tourist) за 2:52 хвилини. Геннадій так само швидше за всіх вирішив завдання В, С і D на 7:05, 24:29 і 13:05 хвилинах відповідно. Задачу E першим вирішив Дмитро Єгоров (Dmitry_Egorov) на 40:59 хвилині. Завдання F стала однією з найскладніших за всю історію Russian Code Cup — з усіх учасників її вирішили правильно тільки три людини, і першим задачу F вирішив переможець RCC 2013 Петро Митричев (Petr) за 2:25:46.
 
Першим з усіма завданнями впорався Павло Кунявській (PavelKunyavskiy) за 2 години 47 хвилин. Всього 6 завдань вирішило 3 людини, 5 і більше завдань вирішили 100 осіб. Останнім у заповітні top 50 потрапив Роман Білий (RomaWhite), що здав п'яту задачу через 2 години 30 хвилин після початку.
 
За волю до перемоги відзначимо Єгора Куликова (Egor), який увійшов в топ 50, здавши одну із завдань з 7 спроби. А також Петра Мітрічева (Petr), який, не придумавши як вирішити задачу C, відмовився від спроб її вирішити, перший вирішив найскладнішу задачу F. А потім, повернувшись до задачі C, здав її за 4 хвилини до кінця і посів у підсумку 3 місце.
 
Територіальний розподіл учасників в цьому раунді було наступним:
                                                                                                                  
Росія 515
Україна 112
Білорусь 77
Казахстан 26
США 17
Вірменія 8
Узбекистан 8
Швейцарія 6
Німеччина 4
Латвія 4
Австрія 2
Болгарія 2
Великобританія 2
Грузія 2
Молдова 2
Польща 2
Республіка Сінгапур 2
Азербайджан 1
Аргентина 1
Ірландія 1
Канада 1
Кіпр 1
Литва 1
Республіка Корея 1
Словаччина 1
Туреччина 1
Швеція 1
Японія 1
При цьому вперше в Russian Code Cup були учасники, які не знають російської мови з Австрії, Аргентини та Японії! Як зізнався один з них, умови задач раунду він перекладав через сервіси онлайн перекладу.
 
Боротьба у відбірковому раунді була напруженою. У підсумку у фінал вийшли 50 найсильніших програмістів. Детально про них ми розповімо пізніше.
  
 Завдання A. Розбір задач
 
 Ідея: Анна Малова
 Реалізація: Андрій Комаров
 Розбір: Андрій Комаров
 
У задачі потрібно скласти план розбору завдань так, щоб сумарна тривалість розбору була мінімальною. Завдання повинні розбиратися в порядку з першої до m -й. Час розбору одного завдання становить t секунд. Заміна разбирающего задачу члена журі — c секунд. Якщо один і той же член журі розбирає кілька завдань підряд, то заміна не потрібно. Про кожного члена журі відомо, які завдання він хоче розбирати, а які — ні.
 
Це завдання вирішується жадібним алгоритмом. Виберемо члена журі, який вміє вирішувати максимальне число завдань, починаючи з першої. Нехай він вміє вирішувати k завдань. Потім, виберемо того, хто вміє вирішувати максимальне число завдань, починаючи з k -й. Будемо продовжувати так, поки не будуть розібрані всі завдання. Тоді відповіддю на завдання буде m · t + q · c , де q — число проведених замін.
 
Чому це є оптимальною відповіддю? Нехай у якийсь момент був обраний член журі, бажаючий проводити розбір НЕ максимального числа завдань. Тоді, від того, що його замінять на того, хто вміє розбирати більше і дати йому розібрати більше, відповідь може тільки покращитися.
 
Дане рішення працює за O (n · m).
 
Також можна було написати просте рішення за допомогою динамічного програмування. dp [i ] [j ] одно мінімального часу, який витрачається, якщо розібрали i завдань і i -ю розбирав j -й член журі. Даний масив можна легко порахувати за O (n 2 m) .
 
 Завдання B. На далекій Амазонці
 
 Ідея: Віталій Аксьонов
 Реалізація: Демид Кучеренко
 Розбір: Демид Кучеренко
 
У цьому завданню необхідно побудувати орієнтований граф, що складається з n вершин, в якому виконуються наступні умови:
 
     
в графі не повинно бути циклів;
 в кожну вершину веде максимум одне ребро;
 в графі повинно бути рівно a вершин, з яких існують вихідні ребра;
 в графі повинно бути рівно b вершин, в які існують входять ребра.
 
Для початку розберемо випадки, коли відповідь «IMPOSSIBLE». Це випадки, коли виконується хоча б одна з умов:
 
     
матерів більше, ніж дочок;
 матерів більше, ніж n -1 (всі матерями бути не можуть);
 дочок більше, ніж n -1.
 
Якщо такий граф можливо побудувати, то спочатку побудуємо ланцюжок з a ребер. Таким чином у нас буде задіяно a +1 жінка, і буде a матерів і a дочок. Після чого, доповнимо дочками будь-яких матерів, щоб дочок стало рівно b . Може вийти так, що деякі жінки не будуть ні матерями, ні дочками, але це не суперечить умові завдання.
 
 Завдання C. Лабораторна з фізики
 
 Ідея: Віталік Аксьонов
 Реалізація: Артем Васильєв
 Розбір: Артем Васильєв
 
У даній задачі потрібно визначити, яку температуру води можна отримати при змішуванні води з двох судин з холодною і гарячою водою. Було потрібно відповідати на кілька таких запитів при заданій температурі.
 
Запишемо формулу температури води, якщо ми змішуємо холодну воду з посудини об'ємом c i і гарячу воду з посудини об'ємом h j : T = p / q = (C · c i + H · h j ) / (c i + h j ) Перетворивши цю формулу, отримаємо, що (H · q — p) / (p — C · q) = c i / h j Таким чином, ми звели задачу до наступної: задана нездолана дріб і безліч числителей і знаменників, чи можна вибрати чисельник і знаменник так, щоб вийшла задана дріб?
 
Введемо позначення A x — безліч всіх c i / x, де c i ділиться на x . Аналогічно, B y — безліч всіх h i / y, де h i ділиться на y . Тоді нескоротних дріб p / q можна представити тоді і тільки тоді, коли A p і B q перетинаються. Варто відзначити, що сумарний розмір усіх множин A x і B y дорівнює O (M log M ), де M — обмеження на обсяг судин (в даній задачі M одно 10 5 ).
 
При поданні A x і B y у вигляді відсортованих списків один запит можна виконати за O (M / max (x, y)) . Якщо уявляти A x і B y як бітові множини, то виходить рішення за O (M / 64) на запит.
 
Найшвидше рішення виходить, якщо не вважати відповіді для однієї і тієї ж дробу кілька разів. У цьому випадку можна довести більш точну оцінку на час роботи рішення. Доведемо оцінку O ((M + k) sqrt (M)) , де k — кількість запитів. Якщо максимум з p і q більше, ніж sqrt (M) , то запит можна виконати за O (sqrt (M)) , переглянувши всі елементи меншого з множин. Оцінимо суму часів виконання всіх інших запитів. Запитів, що виконуються за O (M / x) максимум, ніж 2 x . Cумміруя по всіх x, і враховуючи, що x максимум, ніж sqrt (M) , отримуємо оцінку O ((M + k) sqrt (M)) Сумарний час роботи рішення: O ((M + k) sqrt (M)) .
 
 Завдання D. Конструювання пив
  
 Ідея: Микола Ведерников
 Реалізація: Микола Ведерников
 Розбір: Микола Ведерников
 
У задачі потрібно порахувати кількість перестановок, таких що:
 
     
a 2 · i -1 ≤ a 2 · i
 a 2 · i a 2 · i + 1
 
Для всіх i від 1 до n / 2. Назвемо таку перестановку зростаючою пилкоподібної .
 
Зауважимо, що кількість таких перестановок дорівнює кількості перестановок, у яких на непарних позиція стоять числа, більше своїх сусідів. Биективное відповідність: b i = n — a i . Назвемо таку перестановку спадної пилкоподібної. Це нам згодиться далі для вирішення завдання.
 
Очевидно, що якщо довжина перестановки дорівнює 0 або 1, то відповідь — 1.
 
Нехай ми знаємо відповідь для всіх довжин від 0 до n , знайдемо відповідь для n +1. Будемо вважати загальна кількість пилкоподібних послідовностей. Для того щоб отримати кількість зростаючих, потрібно загальне число послідовностей розділити на 2, так як кількість зростаючих дорівнює кількості відбувають.
 
Нехай n +1 поставили на позицію 2 · k , тоді спочатку у нас йде зростаюча пілообразная довжиною 2 · k -1, а після зростаюча довжиною n -2 · k +1. На перші 2 · k -1 позицій ми можемо вибрати будь-які з n чисел. Разом, отримуємо, що кількість перестановок довжини n +1, у яких число n +1 на позиції 2 · k : ans 2 · k -1 · ans n -2 · k +1 · Binom (n , 2 · k -1).
 
Нехай n +1 поставили на позицію 2 · k +1, тоді спочатку у нас йде спадна пілообразная довжиною 2 · k , а після зростаюча довжиною n -2 · k . На перші 2 · k позицій ми можемо вибрати будь-які з n чисел. Разом отримуємо, що кількість перестановок довжини n +1, у яких число n +1 на позиції 2 · k +1: ans 2 · k · ans n — 2 · k · Binom (n , 2 · k ).
 
Разом, загальна кількість пилкоподібних послідовностей довжини n +1: ans n +1 = Σ n k = 0 ans k · ans n-k · Binom (n, k) .
 
 Завдання E. Зарплата
 
 Ідея: Анна Малова
 Реалізація: Павло Кротков
 Розбір: Павло Кротков
 
У цьому завданню дан орієнтований граф. Всі ребра можна було класифікувати на три частини:
 
     
при будь розстановці окладів і бонусів у вершинах цього ребра умова керівництва виконуватиметься;
 для виконання умови керівництва необхідно або поміняти оклад з бонусом в обох вершинах цього ребра, чи не змінювати ні на одній;
 для виконання умови керівництва необхідно поміняти оклад з бонусом рівно в одній з вершин цього ребра.
 
Забудемо про всі ребра першого типу і про орієнтованість ребер другого і третього типу. Після цього об'єднаємо вершини, досяжні один з одного по ребрах другого типу. Після цього завдання про перевірку того, чи можна виконати вимогу керівництва, зводиться до перевірки того, чи можна розфарбувати вийшов граф в два кольори, решающейся обходом в глибину.
 
Для отримання мінімальної кількості вершин, в яких потрібно поміняти місцями оклад з бонусом, модифікуємо цей пошук в глибину. Після обходу і розмальовки в два кольори черговий компоненти зв'язності, порахуємо кількість вершин (вихідного графа, до об'єднання по ребрах другого типу), розфарбованих у той і в інший колір, і, при необхідності, інвертуємо розмальовку.
 
 Завдання F. Робот
 
 Ідея: Борис Мінаєв
 Реалізація: Борис Мінаєв, Артем Васильєв
 Розбір: Борис Мінаєв, Артем Васильєв
 
У задачі потрібно порахувати кількість різних шляхів з однієї клітини поля в іншу за певну кількість кроків. При цьому робот, який вчиняє дії, не може відвідати кінцеву клітку раніше ніж в останній хід. Також робот може ходити тільки по одній чверті нескінченної площині.
 
Для початку знайдемо кількість способів дістатися з однієї клітини в іншу без умови, що не можна відвідувати кінцеву клітку раніше останнього ходу. Таке завдання можна вирішувати незалежно за координатами, а потім перебрати, скільки ходів було скоєно по одній координаті, а скільки по іншій. Як вирішувати проблему в одновимірному випадку? Нехай спочатку робот має координату x 1 , а наприкінці повинен мати координату x 2 . Нехай a = | x 2 x 1 |, а всього було скоєно t ходів. Тоді кількість різних способів дорівнюватиме кількості сполучень з t по (t a ) / 2 (при цьому t a повинно бути невід'ємним і парних). Однак потрібно врахувати, що робот може мати тільки позитивну координату в процесі подорожі. Для цього необхідно просто відняти з отриманого результату кількість способів дістатися з клітини — x 1 в x 2 . Це справедливо, тому що між шляхами з x 1 , які порушують вимогу позитивності координати, а також всіма шляхами з — x 1 можна показати взаємно однозначна відповідність. Відповідні один одному шляху матимуть дзеркальні перші частини (до моменту входу в клітку 0) і загальні другого частини.
 
Повернемося до розгляду двовимірної задачі. Нехай ми вже порахували кількість способів дістатися по кожній координаті від однієї клітини до іншої (для кожної фіксованої довжини подорожі). Щоб порахувати аналогічні значення для двовимірної задачі, необхідно перебрати кількість часу, який витрачено на кожну координату, а потім перемножити відповідні значення у вже порахованих масивах, а також помножити на кількість різних способів вибрати які саме ходи будуть відповідати яким координатах. Щоб порахувати ці значення швидко, можна скористатися перетворенням Фур'є. Щоб звести завдання до перемножування поліномів, необхідно позбутися від присутності у формулі кількості поєднань. Для цього розпишемо його через факторіали. Згрупувавши доданки, отримаємо, що можна i -е елементи вихідних масивів поділити на i !, Перемножити отримані поліноми, а потім значення в i -м розряді помножити на i ! У задачі модуль, по якому необхідно виконувати всі операції, був підібраний таким чином, що по ньому можна виконувати швидке перетворення Фур'є.
 
Тепер розглянемо, як врахувати те, що робот не може заходити в кінцеву клітку до останнього ходу. Будемо вважати відповідь за допомогою динамічного програмування. Нехай вже пораховано кількість способів дійти до клітки за менше ніж t ходів. Щоб порахувати це значення для t ходів, розглянемо загальна кількість способів зробити це за t ходів і віднімемо з нього всі способи, які заходять в кінцеву клітку до ходу t . Для цього переберемо номер першого ходу, в який робот відвідає кінцеву клітку і помножимо відповідну йому кількість способів на кількість способів вийти з клітини (x 2 , y 2 ) і повернутися до неї за решту час. При цьому, робот може скільки завгодно разів відвідувати кінцеву клітку (у другій частині).
 
Зауважимо, що викладене рішення працює поки за t 2 . Для більш швидкого вирішення слід міркувати в термінах виробляють функцій. Позначимо f (x) = f 0 x 0 + f 1 x 1 +… + f t x t +… , де f i — відповідь не завдання. Аналогічно визначимо count (x) — виробляє функція для кількості шляхів, без урахування умови першого заходу в кінцеву клітку на останньому ходу, cycle (x) — виробляє функція для кількості шляхів з кінцевої клітини в саму себе. З рекурентних співвідношення для f i , можна вивести співвідношення на виробляють функції: f (x) = count (x) — f (x) cycle (x) , звідки f (x) = count (x) / (cycle(x) + 1) = count(x) (cycle(x) + 1) -1 . Для обчислення f необхідно порахувати перший t + 1 членів дробу в правій частині. Це можна зробити, обчисливши зворотний до cycle (x) + 1 многочлен по модулю x t +1 , і перемноживши count (x) з результатом. Взяття зворотного многочлена за модулем x t +1 можна виконати за час O (t log t ) з використанням швидкого перетворення Фур'є. Підсумкове час роботи: O (t log t ).

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

0 коментарів

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