Розбір задач четвертого кваліфікаційного раунду Russian Code Cup 2014

    
 
У неділю, 1 червня, пройшов четвертий, заключний, кваліфікаційний раунд Russian Code Cup 2014.
 
На участь в раунді зареєструвалося 5428 осіб. Як мінімум одне рішення прислали 730 учасників. Всього за раунд було надіслано 4793 рішення, з них правильних — 1531.
 
Найбільше рішень на GNU C + + — 1786.
Рішень на Python — 307, з них правильних 86.
Рішень на PHP — 93, з них правильних 15.
Рішень на Perl — 6, з них правильних 2.
 
Першим задачу А вирішив Філіппов Дмитро (DimaPhil) за 2:42 хвилини, він же першим вирішив і завдання В за 12:09. Завдання С і D першим вирішив Обєдніков Олександр (AOb) на 12:25 і 37:44 хвилині відповідно. Першим задачу Е вирішив Фефер Іван (Fefer.Ivan) на 45:22 хвилині. Іван також першим впорався з усіма завданнями за 1 годину 8 хвилин. Всього 5 завдань вирішило 12 осіб. 10 учасників були дискваліфіковані суддями.
 
Всього за 4 кваліфікаційні раунди у відбірковий пройшло 802 учасника, які будуть боротися один з одним у фіналі 8 червня.
 
 Завдання А . Соцопитування
Ідея: Андрій Станкевич
Реалізація: Микола Ведерников
Розбір: Микола Ведерников
 
У задачі потрібно знайти мінімальне і максимальне можливу кількість учасників, які вирішать задачу. Якщо всього учасників n , з них вміють вирішувати задачу a , а b учасникам завдання противна.
 
Оскільки за умовою задачі її вирішать тільки ті, кому вона не противна і вміють вирішувати, то кількість тих, хто спробує вирішити завдання, буде дорівнює або менше n b . Тобто якщо серед всіх, хто спробує вирішити завдання, будуть ті, хто це вміє, то це буде максимум з тих, хто вирішить. Це min (a , n b ).
 
Мінімум же досягається, якщо всі, кому противна завдання, будуть вміти вирішувати задачу, тоді відповідь max (0, a b ).
 
 Завдання B . Сто
Ідея: Віталій Аксьонов
Реалізація: Павло Кротков
Розбір: Павло Кротков
 
Рішенням завдання є програма, акуратно розглядає кілька нескладних випадків. Найпростішим випадком є ​​ситуація, коли кількість цифр у числі x одно k +1. У цьому випадку необхідно вивести -1, якщо число не містить жодного нуля, і нуль — якщо в числі присутній хоча б один нуль.
 
Якщо ж кількість чисел у числі x перевищує k хоча б на три, цю ситуацію необхідно обробляти більш акуратно. Знайдемо в числі других нуль з кінця. Переконаємося, що за ним стоїть не більше, ніж k +1 цифра. Викреслимо з числа все ненульові цифри, що стоять за другим з кінця нулем, а також викреслимо необхідну кількість цифр, що стоять відразу перед другим з кінця нулем. Зауважимо, що перша цифра ніколи не викреслюється, а значить, в підсумковому числі не буде провідних нулів.
 
Важливо було не забути про те, що операція викреслювання цифри не повинна виконуватися за довжину числа — рішення з такою помилкою отримали перевищення межі часу на третьому тесті.
 
 Завдання C . Похід в гості
Ідея: Георгій Корнєєв
Реалізація: Борис Мінаєв
Розбір: Борис Мінаєв
 
Щоб вирішити поставлене завдання, необхідно акуратно проемуліровать процес, який описаний в умові. При реалізації зручно використовувати вбудовані засоби для підтримки черги. У самих чергах можна зберігати, наприклад, номер людини, яка купив відповідний подарунок. Тоді черговий похід в гості відбувається наступним чином. Візьмемо елемент з черги, яка відповідає людині, яка іде в гості. Якщо його черга порожня, то будемо вважати, що з черги був узятий елемент, який відповідає цій людині. Після цього додамо даний елемент у чергу, яка відповідає людині, до якого прийшли в гості. Якщо значення доданого елемента дорівнює номеру черги, в яку його додали, то необхідно вивести YES, інакше NO.
 
 Завдання D . СНМ
Ідея: Артем Васильєв
Реалізація: Артем Васильєв
Розбір: Артем Васильєв
 
У задачі була описана реалізація системи непересічних множин з рангової евристикою, але без евристики стиснення шляхів. Будемо вирішувати задачу для кожного кореневого дерева незалежно, також слід розглянути випадок наявності циклів.
 
Хоч масив rank і не задавався у вхідних даних, легко зрозуміти, що без стиснення шляхів rank i — це висота піддерева з вершиною i в корені. Також відзначимо, що алгоритм влаштований так, що rank i кожен раз збільшується не більше, ніж на одиницю, а після того, як вершина підвішується до іншої, її parent і rank не змінюються, тому можна будувати від листя до кореня.
 
Розглянемо поддерево з коренем у вершині u . Якщо rank u = r , то у вершини u повинні існувати діти з рангом 0, 1, ..., r -1. Легко показати, що ця умова є достатньою: якщо провести операції union в порядку збільшення рангу сина, всі операції пройдуть коректно.
 
Звідси випливає рішення для одного дерева:
 
 
     
Рекурсивно побудуємо рішення для всіх дітей кореня дерева.
 Перевіримо, що для всіх h від 0 до rank root — 1 існує син з рангом h .
 Проробимо операції union (root , child i ) в порядку збільшення рангу child i .
 
Також можливо реалізувати СНМ і безпосередньо проробити всі операції, перевіривши, що вийшов масив parent збігся з потрібним.
 
Час роботи рішення — O (n log (n )).
 
 Завдання E . Нанороботи
Ідея: Віталій Аксьонов
Реалізація: Андрій Комаров
Розбір: Андрій Комаров
 
У задачі потрібно за мінімальне число дій переміщення або розбиття на дві частини перевести всіх нанороботів з лівого верхнього кута в правий нижній.
 
Будемо вирішувати цю задачу за допомогою динамічного програмування. Позначимо за dp [w ] [x ] [y ] мінімальне число кроків, за яке можна довести робота масою w з клітки (x , y ) до фінальної клітини (n , m ). Початкові значення dp [w ] [n ] [m ] = 0 говорять про те, що з цільової клітини йти нікуди не треба. Після того, як dp буде пораховано, відповідь буде міститися в комірці dp [w ] [1] [1].
 
Навчимося рахувати dp . Щоб порахувати dp [w ] [i ] [j ], зробимо одне з двох:
 
 
     
Дійдемо до фінішу, не розбиваючи робота на частини. Для цього, за допомогою обходу в глибину, знайдемо найкоротший шлях до фінішу по витримує клітинам.
 Або дійдемо до якоїсь клітини, розіб'ємося на дві частини і дійдемо ними звідти.
 
Щоб не було проблем з розумінням того, в якому порядку вважати значення динаміки, можна вважати її ліниво. Підсумкова складність алгоритму: O (w 2 n 2 m 2 ).
    
Джерело: Хабрахабр

0 коментарів

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