Автори задачі: | Ігор Баренблат, Матвій Асландуков |
Задачу підготували: | Ігор Баренблат, Матвій Асландуков |
Розбір написав: | Матвій Асландуков |
Введемо наступні позначення:
x = \max\limits_{i=1}^n a_i;
N = \sum\limits_{i=1}^T n_i, де n_i — значення в -му наборі вхідних даних;
X = \max\limits_{i=1}^T x_i, де x_i — значення в -му наборі вхідних даних;
— мінімально можлива кількість дивних підпослідовностей серед утворених.
Блок 1 (k = 1).
Існує єдиний спосіб розбити масив на одну підпослідовність. Щоб знайти кількість дивних підпослідовностей серед однієї утвореної, достатньо перевірити, чи є сума елементів масиву простим числом — це можна зробити стандартним алгоритмом за O(\sqrt{s}), де s = \sum_{i=1}^n a_i \leq nx.
Складність обробки одного набору вхідних даних — O(n + \sqrt{nx}).
Складність обробки всіх наборів вхідних даних — O(N + N \sqrt{X}).
Блоки 2, 3, 4, 5, 6, 7, 8.
Для розв'язку наступних блоків доведемо дві допоміжні леми.
Лема 1.
Твердження. Нехай q = n - k. Розглянемо наступний процес:
Створимо підпослідовностей, де -та початково складається з одного елементу a_i.
Виконаємо операцій «об'єднання»: під час кожної операції виберемо дві певні підпослідовності, та об'єднаємо їх в одну.
Тоді задача розбиття масиву на непорожніх підпослідовностей еквівалентна задачі об'єднання одноелементних підпослідовностей за допомогою описаних вище операцій.
Доведення. Дійсно, при виконанні однієї операції, кількість підпослідовностей зменшується на 1, а отже після виконання операцій, кількість підпослідовностей буде дорівнювати n - q = n - n + k = k. Також легко помітити, що будь-яке розбиття можна утворити за допомогою описаних вище операцій: для цього під час виконання чергової операції потрібно вибрати дві довільні підпослідовності, елементи яких належать одній у відповідному розбитті.
Лема 2.
Твердження. ans \geq n - 2q.
Доведення. Дійсно, в описаному вище процесі початково існувало дивних підпослідовностей, а кожна операція «об'єднання» зменшувала кількість дивних підпослідовностей не більше ніж на 2. Тому після виконання будь-яких операцій, все ще мало б залишитися хоча б (n - 2q) дивних підпослідовностей.
Блок 6 (2 k \geq n + 1).
Оскільки k = n - q, то 2 \cdot (n - q) \geq n + 1 \Rightarrow n - 2q \geq 1. В такому випадку завжди можна утворити відповідь рівно з (n - 2q) дивними підпослідовностями, що є оптимальною відповіддю згідно з другою лемою. А саме, під час виконання чергової операції «об'єднання», виберемо дві одноелементні підпослідовності з однаковою парністю елементів. Неважко помітити, що це завжди можна буде зробити:
для непарного , існує парна кількість або парних, або непарних елементів, а тому максимум один елемент може залишитися без пари, що відповідає умові (n - 2q) \geq 1.
для парного , максимум два елементи можуть залишитися без пари (один парний, інший непарний), що відповідає умові (n - 2q) \geq 2, яка виконується, оскільки (n - 2q) є парним числом та (n - 2q) \geq 1.
Оскільки сума двох чисел з однаковою парністю є парним числом більшим за два, то у результаті «об'єднання» замість двох дивних підпослідовностей утвориться одна недивна. Таким чином, кожна операція буде зменшувати кількість дивних підпослідовностей на 2, що в підсумку зробить ans = n - 2q.
Складність обробки всіх наборів вхідних даних — .
Блоки 2, 3, 7.
Перед обробкою всіх наборів вхідних даних підрахуємо допоміжний масив isPrime[1..2X] (isPrime[1..10X] у третьому блоці), де isPrime[i] позначає, чи є число простим. Це можна зробити за O(X \log X) за допомогою алгоритму «Решето Ератосфена».
Блок 2 (n \leq 4).
При наявності рішення на перший та шостий блоки, потрібно розглянути тільки випадок n = 4, k = 2, оскільки для всіх інших випадків виконується хоча б одна з умов 2k \geq n + 1, k = 1.
При n = 4, k = 2 достатньо розглянути лише випадки, де обидві підпослідовності складаються з двох елементів. Це можна зробити, перебравши один з трьох елементів, який буде в підпослідовності разом з . Якщо в якомусь з трьох випадків немає дивних підпослідовностей (це можна перевірити за допомогою масиву isPrime), то ans = 0. Інакше серед цих випадків треба знайти будь-який з однією дивною підпослідовністю. Такий завжди знайдеться, оскільки в масиві довжини 4 існує пара елементів однакової парності (а отже їхня сума не є простим числом). Саме тому не потрібно розглядати випадки, де одна підпослідовність складається з одного елементу, а інша — з трьох, оскільки в них гарантовано буде хоча б одна дивна підпослідовність (яка складається з одного елементу, що є простим числом).
Не маючи рішень на перший та шостий блоки, можна окремо розглянути усі можливі комбінації значень , , та вирішити задачу для кожної з них окремо, перебравши усі необхідні варіанти утворення підпослідовностей.
Складність обробки всіх наборів вхідних даних — O(X \log X + N).
Блок 3 (T \leq 20, n \leq 10).
У цьому блоці достатньо було перебрати всі можливі розбиття масиву на підпослідовностей. А саме, будь-яке розбиття можна задати за допомогою масиву довжини , де позначає номер підпослідовності, до якої належить .
Щоб розбиття однозначно задавалося масивом , достатньо розглядати лише такі , де ids[1] = 1 та 1 \leq ids[i] \leq (\max\limits_{j=1}^{i-1} ids[j] + 1) при i > 1. Дійсно, оскільки порядок підпослідовностей не має значення, без втрати загальності можна вважати ids[1] = 1, а для кожного наступного , -й елемент або буде входити до підпослідовності, в якій вже зустрічався якийсь попередній елемент масиву (тоді 1 \leq ids[i] \leq \max\limits_{j=1}^{i-1} ids[j]), або буде найлівішим елементом нової підпослідовності (тоді без втрати загальності можна вважати ids[i] = \max\limits_{j=1}^{i-1} ids[j] + 1).
Усі розбиття можна перебрати за допомогою рекурсивної генерації масиву . Наприклад, наступний код на Python3 перебирає та рахує кількість розбиттів масиву довжини 10:
def countPartitions(ids):
if len(ids) == 10:
return 1
return sum(countPartitions(ids + [id]) for id in range(1, max(ids) + 2))
print(countPartitions([1]))Експериментальним шляхом можна побачити, що при n = 10 кількість розбиттів C = 115975. Для кожного з них із загальною кількістю підпослідовностей у розбитті, можна підрахувати кількість дивних підпослідовностей за допомогою масиву isPrime, та вибрати розбиття з мінімальною кількістю.
Складність обробки всіх наборів вхідних даних — O(X \log X + C \cdot N).
Блоки 4, 5, 7, 8.
Для цих блоків буде наведено рішення для 1 < k, 5 \leq n та 2 k < n + 1 \Rightarrow 2 k \leq n \Rightarrow n \leq 2q. При невиконанні цих умов, дивіться рішення для блоків 1, 2 та 6.
Блок 4 ( — парне, a_i > 2).
Оскільки всі a_i > 2, то всі елементи масиву — непарні. Оскільки q \geq \frac{n}{2}, то спочатку розіб'ємо усі елементи по парам, тим самим виконавши \frac{n}{2} операцій «об'єднання», та зробивши всі підпослідвності недивними, оскільки суми їхніх елементів будуть парними числами більше за два. Після цього залишиться виконати (q - \frac{n}{2}) операцій «об'єднання», що можна зробити довільним чином, оскільки сума будь-яких двох парних чисел є парним числом. Кількість дивних підпослідовностей у результаті буде дорівнювати нулю, що очевидно є мінімально можливою кількістю.
Складність обробки всіх наборів вхідних даних — .
Блоки 5, 7, 8.
Для розв'язку наступних блоків доведемо допоміжну лему.
Лема 3.
Твердження. Серед п'яти простих чисел завжди можна знайти три числа, сума яких ділиться на 3 та не є простим числом.
Доведення. Помітимо, що сума будь-яких трьох простих чисел перевищує 3, а отже ця сума не є простим числом у випадку, якщо вона ділиться на 3. Тепер доведемо, що можна знайти три числа, сума яких ділиться на 3. Припустимо, що це не так. Розглянемо залишки від ділення на 3 всіх заданих чисел. Якщо якийсь залишок зустрічається хоча б 3 рази, то сума трьох відповідних чисел буде ділитися на 3, що по припущенню неможливо. Також якщо усі залишки (0, 1, 2) зустрічаються хоча б один раз, то сума трьох відповідних чисел буде ділитися на 3, що по припущенню неможливо. Це означає, що у масиві залишків зустрічається лише два різних числа, кожне з яких зустрічається максимум два рази, а тому загальна довжина масиву не перевищує 4. Отримали протиріччя, оскільки лема доводилася для п'яти чисел.
Блок 5 ( — непарне, a_i > 2).
Оскільки — ціле число, то для непарного нерівність q \geq \frac{n}{2} можна посилити: q \geq \frac{n + 1}{2}. Оскільки n \geq 5, то згідно з третьою лемою серед перших п'яти елементів масиву можна знайти трійку з сумою, що не ділиться на 3. Знайдемо таку трійку шляхом повного перебору всіх C_5^3 = 10 трійок, та об'єднаємо відповідні елементи в одну підпослідовність, виконавши дві операції «об'єднання». Інші (n - 3) елементи розіб'ємо по парам довільним чином, виконавши \frac{n - 3}{2} операції «об'єднання». Після цих (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки перша матиме непарну суму елементів.
Оскільки k>1, то маючи лише одну недивну підпослідовність з непарною сумою та решту недивних підпослідовністей з парною, фінальні c = (q - \frac{n+1}{2}) операцій «об'єднання» можна витратити на об'єднання (c+1) підпослідовностей з парною сумою в одну підпослідовність також з парною сумою. Кількість дивних підпослідовностей у результаті буде дорівнювати нулю, що очевидно є мінімально можливою кількістю.
Складність обробки всіх наборів вхідних даних — .
Блок 8 ( — непарне).
Аналогічно п'ятому блоку, тут буде виконуватися нерівність q \geq \frac{n+1}{2}.
Поступово розглянемо всі можливі «типи» масиву :
Кількість двійок в масиві — непарна.
Тоді кількість непарних елементів в масиві — парна. Залишимо одну двійку в окремій одноелементній підпослідовності та використаємо \frac{n-1}{2} операцій «об'єднання» для розбиття решти (n - 1) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Використаємо додаткову операцію «об'єднання», щоб об'єднати одноелементну підпослідовність з двійкою з будь-якою іншою підпослідовністю. Після цих (1 + \frac{n - 1}{2} = \frac{n + 1}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними та матимуть парну суму елементів. Фінальні (q - \frac{n+1}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Кількість двійок в масиві — парна.
Тоді кількість непарних елементів в масиві — непарна. Спробуємо знайти трійку непарних елементів з сумою, що ділиться на 3 (це можна зробити так само, як у блоці 5):
Якщо така трійка знайшлася, то об'єднаємо відповідні елементи в одну підпослідовність, виконавши дві операції «об'єднання». Виконаємо \frac{n - 3}{2} операцій «об'єднання» для розбиття решти (n - 3) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Після цих (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки перша матиме непарну суму елементів. Фінальні (q - \frac{n+1}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Якщо така трійка не знайшлася, то з третьої леми випливає, що кількість непарних елементів не перевищує 3, а отже кількість двійок хоча б 2. Розглянемо два випадки:
Серед непарних елементів існує якийсь елемент x \neq 3. Залишимо та дві двійки в окремих одноелементних підпослідовностях. Виконаємо \frac{n - 3}{2} операцій «об'єднання» для розбиття решти (n - 3) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Оскільки — просте число більше за три, може мати лише два можливих залишка при діленні на 3:
x \mod 3 = 2, тобто (x + 4) ділиться на 3. Виконаємо дві операції «об'єднання» одноелементних підпослідовностей в одну: [x, 2, 2].
x \mod 3 = 1, тобто (x + 2) ділиться на 3. Виконаємо одну операцію «об'єднання», щоб створити двоелементну підпослідовність: , а другу операцію, щоб об'єднати останню двійку з будь-якою іншою з перших \frac{n - 3}{2} пар.
Після цих (2 + \frac{n - 3}{2} = \frac{n + 1}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки одна матиме непарну суму елементів. Фінальні (q - \frac{n+1}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Всі непарні елементи дорівнюють трьом. Це означає, що в масиві існує лише один непарний елемент, оскільки інакше б на попередьному кроці знайшлася трійка з сумою, що ділиться на 3 ((3+3+3) \mod 3 = 0). Іншими словами, a = [2, 2, \ldots, 2, 2, 3]. Розглянемо два випадки:
q = \frac{n + 1}{2}. В такому випадку хоча б одна з утворених підпослідовностей буде дивною: або підпослідовність з трійкою (, , [3, 2, 2]), або одноелементна підпослідовність (така завжди знайдеться, якщо підпослідовність з трійкою складається хоча б з чотирьох елементів).
Виконаємо \frac{n - 1}{2} операцій «об'єднання» для розбиття всіх (n - 1) двійок на пари, та ще одну операцію, щоб об'єднати та . Отримаємо розбиття з однією дивною підпослідовністю.
q > \frac{n+1}{2} \Rightarrow q \geq \frac{n+3}{2}. В такому випадку n \geq 7, оскільки при n = 5 єдине можливе значення q = \frac{n+3}{2} + 1 = 4, що вже розглянуто окремо у випадку k = n - q = 5 - 4 = 1.
Об'єднаємо останні чотири елементи в підпослідовність [2, 2, 2, 3], виконавши три операції «об'єднання». Об'єднаємо три двійки в підпослідовність [2, 2, 2], виконавши дві операції «об'єднання». Виконаємо \frac{n - 7}{2} операцій «об'єднання» для розбиття решти (n - 7) двійок на пари. Після цих (5 + \frac{n - 7}{2} = \frac{n + 3}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки одна з них матиме непарну суму елементів. Фінальні (q - \frac{n+3}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Складність обробки всіх наборів вхідних даних — .
Блок 7 ( — парне).
Нагадаємо, що тут розглядається розв'язок для 1 < k, 5 \leq n, q \geq \frac{n}{2}. Оскільки — парне, нерівність n \geq 5 можна посилити: n \geq 6.
Поступово розглянемо всі можливі «типи» масиву :
Кількість двійок в масиві — парна.
Тоді кількість непарних елементів в масиві — парна. Використаємо \frac{n}{2} операцій «об'єднання» для розбиття усіх елементів масиву на пари: парні елементи з парними, непарні — з непарними. Після цих \frac{n}{2} операцій «об'єднання» усі підпослідовністі будуть недивними та матимуть парну суму елементів. Фінальні (q - \frac{n}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Кількість двійок в масиві — непарна.
Тоді кількість непарних елементів в масиві — непарна. Спробуємо знайти непарний елемент такий, що (x+2) не є простим числом (це можна перевірити за допомогою isPrime[x + 2]):
Якщо такий елемент знайшовся, то об'єднаємо його з двійкою в одну підпослідовність , виконавши одну операцію «об'єднання». Виконаємо \frac{n - 2}{2} операцій «об'єднання» для розбиття решти (n - 2) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Після цих (1 + \frac{n - 2}{2} = \frac{n}{2}) операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки перша матиме непарну суму елементів. Фінальні (q - \frac{n}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Якщо такого елементу не знайшлося, це означає, що для всіх непарних елементів виконується (x+2) \mod 3 \neq 0 \Rightarrow x \mod 3 \neq 1. Розглянемо два випадки:
q = \frac{n}{2}. В такому випадку хоча б одна з утворених підпослідовностей буде дивною: або одноелементна підпослідовність (яка зажди є дивною), або підпослідовність , де x \neq 2 (така завжди знайдеться, оскільки двійок непарна кількість, а тому хоча б одна двійка мала б об'єднатися з непарним елементом ).
Об'єднаємо двійку з будь-яким непарним елементом, та виконаємо ще \frac{n - 2}{2} операцій «об'єднання» для розбиття решти (n - 2) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Отримаємо розбиття з однією дивною підпослідовністю.
q > \frac{n}{2} \Rightarrow q \geq \frac{n+2}{2}. Спочатку виконаємо перші \frac{n+2}{2} операцій «об'єднання» в залежності від «типу» масиву :
В масиві існує хоча б три двійки та одна трійка. Об'єднаємо ці чотири елементи в підпослідовність [2, 2, 2, 3], виконавши три операції «об'єднання». Виконаємо \frac{n - 4}{2} операцій «об'єднання» для розбиття решти (n - 4) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Кількість виконаних операцій «об'єднання» — (3 + \frac{n - 4}{2} = \frac{n + 2}{2}).
В масиві існує хоча б п'ять двійок. В такому випадку для кожного непарного елементу виконується x \mod 3 = 2 (інакше б розглянувся попередній випадок).
Об'єднаємо дві двійки та будь-який непарний елемент в підпослідовність [2, 2, x], виконавши дві операції «об'єднання». Об'єднаємо три двійки в підпослідовність [2, 2, 2], виконавши дві операції «об'єднання». Виконаємо \frac{n - 6}{2} операцій «об'єднання» для розбиття решти (n - 6) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Кількість виконаних операцій «об'єднання» — (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
В масиві існує рівно три двійки. Оскільки n \geq 6, то в масиві існує хоча б три непарні елементи. Аналогічно попередньому випадку, для кожного непарного елементу виконується x \mod 3 = 2.
Об'єднаємо три двійки в підпослідовність [2, 2, 2], виконавши дві операції «об'єднання». Об'єднаємо три довільні непарні елементи , , в підпослідовність [x, y, z], виконавши дві операції «об'єднання» (їхня сума буде ділитися на 3, оскільки x \mod 3 = y \mod 3 = z \mod 3 = 2). Виконаємо \frac{n - 6}{2} операцій «об'єднання» для розбиття решти (n - 6) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Кількість виконаних операцій «об'єднання» — (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
В масиві існує рівно одна двійка. Оскільки n \geq 6, то в масиві існує хоча б п'ять непарних елементів. Згідно з третьою лемою, серед них можна знайти три елементи, сума яких ділиться на 3.
Знайдемо їх шляхом повного перебору всіх C_5^3 = 10 трійок, та об'єднаємо відповідні елементи в одну підпослідовність, виконавши дві операції «об'єднання». Об'єднаємо двійку з двома іншими непарними елементами , в підпослідовність [2, x, y], виконавши дві операції «об'єднання». Виконаємо \frac{n - 6}{2} операцій «об'єднання» для розбиття решти (n - 6) елементів масиву на пари: парні елементи з парними, непарні — з непарними. Кількість виконаних операцій «об'єднання» — (2 + 2 + \frac{n - 6}{2} = \frac{n + 2}{2}).
Після цих \frac{n + 2}{2} операцій «об'єднання» усі підпослідовністі будуть недивними, і тільки одна з них матиме непарну суму елементів. Фінальні (q - \frac{n+2}{2}) операцій «об'єднання» можна зробити аналогічно фінальній частині розв'язку п'ятого блоку, отримавши нульову кількість дивних підпослідовностей у результаті.
Складність обробки всіх наборів вхідних даних — O(X \log X + N).
Авторська реалізація
Для кращого розуміння описаного вище розв'язку, його авторську реалізацію на Python3 можна знайти за посиланням https://ideone.com/owiZT3.