Гран-прі Саратова

Як розв’язати C і D?
Здається, я десь раніше бачив проблему J

fmota
3 роки тому
37

Як вирішити Е та Н? Вони обидва досить цікава проблема.

Перш за все, ми можемо запитати n запити, щоб знайти всі листя дерева. Щоб перевірити, чи є вершина аркушем, ми задаємо запит, що містить все n - 1 інші вершини; якщо відповідь така n - 1, вершиною, яку ми виключили із запиту, є лист.

Тоді давайте вкорінюємо наше дерево на якомусь листку. Дозволяти L(х) - множина листків у піддереві вершини х . Оскільки вершин із ступенем 2 не існує, то для будь-яких двох вершин х і р L(х) ≠ L(р); крім того, х є родоначальником р iff. Тож якщо ми отримаємо інформацію про L(х) для кожної вершини, тоді ми можемо реконструювати дерево.

Для кореня, L(корінь) - сукупність усіх листків. На кожен другий лист z, L(z) = z>. Тож нам треба знайти L(х) лише для нелистяних. Щоб перевірити, чи є лист z знаходиться в піддереві нелистової вершини р, ми можемо задати запит 3 корінь р z .

Тож якщо кількість листків є л, ми повинні запитати (л - 1) (n - л) запити на пошук L(х) для всіх нелистових вершин. Це не перевищуватиме 2450, тому ми не будемо задавати більше 2550 запитів.

Класно! Це дійсно просте рішення.

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

Отже, для кожного листка ми знаємо «шлях» до кореня (лише вершини, а не їх порядок). Тепер перетин будь-яких двох таких "шляхів" - це також шлях до кореня з якоїсь вершини (їх lca). І кожна вершина - це lca з 2 аркушів (через відсутність 2-градусних вершин). Отже, зараз у нас є список "шляхів" для всіх вершин, і нам потрібно реконструювати дерево, що може бути зроблено простими dfs.

Якщо дерево є бамбуком, відповіді на всі запити першої частини алгоритму повинні бути n - 1, чи не слід? Якщо ні, поясніть, чому.

E: У DAG кожен вузол може бути досягнутий за допомогою A і досягти B, тоді як

A не має ступеня
B не має перевищення ступеня
| ступінь | > = 1 і | ступінь | > = 1 для всіх вузлів, не A, B

Тепер слід вибрати два непересічні набори ребер EA, EB такі, що

краї в EA мають чіткі кінцеві точки
краї в EB мають чіткі вихідні точки

Це можна знайти за допомогою максимального збігу в О(мн 0,5)

Ого, потік для 1000000 країв, це новий запис, який я коли-небудь бачив:)

До речі це можна вирішити без потоку.

Я не розумію, чому це новий запис для вас, але двостороння відповідність на 10 ^ 6 вершин, очевидно, повинна працювати вчасно:)

Однак очищення графіку для кожного ТК було проблемою.

Крім того, це можна зробити за O (м), і навіть це можна зробити за мінімальних загальних витрат країв за O (м) час.

Додамо два ребра від B до A. Тепер у нас є лише умова на градуси. Отримаємо двосторонні grpah з 2 копіями вершин у лівій частині (що відповідає вершині в EA і вершині в EB) та ребрах у правій частині. Кожна вершина у другій частині матиме рівно два ребра (починати з EA та до і в EB). Проблема полягає в тому, щоб знайти ідеальне (за лівою частиною) узгодження на цьому графіку.

Це можна зробити двома способами. По-перше, кожна ланцюг, яку ми шукаємо за методом Куна, має унікальний край на кожному кроці. Отже, ми можемо просто зберегти кінець цього ланцюжка для кожної вершини в неперервному об’єднанні множин.

Інший спосіб, який мені здається більш гарним, - це думати про вершину 2 ступеня як про ребро між сусідами. Можна продемонструвати, що узгодження таке саме, як покриття цього графіка набором ребер, де жоден компонент не має більше ребер, ніж вершин (тобто дерево або цикл із деревами на ньому). Таке покриття може бути здійснено за допомогою чогось на кшталт алгоритму Крускала. І двоє, будьте чесними, видає точно такий самий код, що і перший метод.

І якщо ми відсортуємо краї шляхом збільшення вартості будь-яким із цих методів, це призведе до мінімального рішення.

Хтось знає передбачуване рішення В? Як ви повинні швидко обчислитись після отримання формули відповіді?

Хоча у мене немає змінного струму, я отримав щось у python, що могло б пройти швидшою мовою з вбудованим GMP-gcd з деякими постійними оптимізаціями.

Нехай 'avgbad' - середня вартість нерозумного товару, а 'avgreason' - середня вартість розумного товару. Нехай "поганими" є кількість нерозумних предметів. Тоді відповідь така

Двочлени можна обчислити трохи швидше, просіявши над простими числами, це, ймовірно, може бути пришвидшено більше, обчислюючи продукт у способі поділи і завоюй. Основним вузьким місцем було зменшення фракції. Buitin python gcd має сповільнювати, я знайшов швидший lehmer-gcd тут, але все одно повільно.

Завантаження GMP в c ++ не працює на Яндексі, на жаль (принаймні метод, який працює на з'єднанні, не працює на Яндексі), тому я не зміг спробувати GMP-gcd. Завтра я спробую ще щось.

Редагувати: Отримано пришвидшення в pow_binomal, обчислюючи продукт розумнішим способом, тепер TLE 36 (раніше TLE 34).

Добре, я отримав змінний струм за 1,5 секунди з деякими оптимізаціями.

Формула, що включає лише два різні біноміальні коефіцієнти та деякі менші числа. (Див. Мій пост вище.)
Обчислення двочленів шляхом підрахунку кількості випадків кожного простого числа.
Обчислення отриманого добутку простих степенів шляхом двійкового розщеплення.
(нове) Скасування простих чисел, які зустрічаються в обох двочленах рано.
Використовуйте lehmer gcd.
Використовуйте pypy4, а не python2.7.

Як вирішити задачу F? Як ми використовуємо обмеження ?

Я думаю, нам потрібно скористатися фокусом звідси, якщо ми виберемо випадковий індекс і з імовірністю (а це, за нашими умовами, принаймні, тому ми перевіримо близько 10 випадків), він з’явиться в кінцевій послідовності. Тоді ми знаходимо його найбільший дільник таким, що існує принаймні n - k числа, що ділять це число.

UPD. Щодо останньої частини, припустимо, ми вибрали номер N, вона має щонайбільше дільників. Нехай його дільники дорівнюють 1 = d 1 2 К = N і простими числами ділимо це стор 1 2 т (1 ≤ т ≤ 15). Ми обчислимо масив cnt з cnt i кількість значень у нашій послідовності, які діляться d i . У вищезазначеній проблемі нам дозволено зробити наступне:

Перший сет cnt i бути рівним такому числу значень, що gcd між ним і N дорівнює i .

По-друге, просто повторіть для кожного i від К до 1 і на кожну j від i + 1 до К якщо у нас це є d j ≡ 0 (мод d i) тоді ми збільшуємо cnt j від cnt i .

Тепер нам потрібно його оптимізувати, тому що О(К 2) занадто багато, тому я представив послідовність простих чисел. В основному на кожну прем'єру стор i і для кожного j ми збільшуємо на cnt j позиція в масиві cnt що відповідає дільникам (1 ≤ р, d j ≡ 0 (мод стор i р )). Це можна зробити знову за лінійний час. Тож складність стає такою, що на практиці значно менша.

Якщо ви виявите щось не так, будь ласка, повідомте мене. Сподіваюся, я не пропустив жодного простого рішення:) .

Гран-прі Саратова - Codeforces