Автор задачі: | Роман Білий |
Задачу підготував: | Роман Білий |
Розбір написали: | Роман Білий та Ігор Баренблат |
Блок 1
Проітеруємось по всім кулькам і виконуватимемо по запиту з кожною з нею. Рівно один раз як результат отримаємо значення . Це відбудеться при запиті з одною з кульок, що повторюється. Іншу можна знайти виконавши ще по одному запиту з кожною з кульок.
Блок 2
Не обмежуючи загальності вважатимемо, що перша кулька — кулька кольору . Далі проітеруємося по всім іншим кулькам та виконаємо запит з кожною з них. Якщо значення, яке отримали рівне (останньому відомому значенню кульок кольору ) + 1, то колір цієї кульки також , інакше . Для того, щоб однозначно визначати колір при черговому запиті, після кожного запиту виконуватимемо запит з кулькою номер .
Блок 5
Проітеруємось по всім кулькам та виконаємо запит з кожною з них. Відсортуємо отримані пари (значення результату запиту, номер кульки) по незростанню першого параметру. Тепер у порядку встановленому цим списком знову виконуватимемо по запиту з кожною кулькою — отримуючи результат запиту, можна однозначно визначити колір кульки.
Інший варіант розв'язати цей блок. Пройдемось двічі по всіх кульках зліва направо. Нехай a_i — значення, яке отримали при першому проході при запиті до -ої кульки, b_i — при другому проході. Тоді є рівно b_i-a_i кульок такого ж кольору, які такі ж, як і -та кулька. Враховуючи, що кількість кульок кожного кольору різна, ця інформація також дозволяє відновити всі кольори.
Всі інші блоки
Зробимо один прохід по кульках зліва направо та знайдемо всі позиції, де колір зустрічається вперше. Назвемо їх базовими кульками. Розставимо на ці позиції кольори від до . Надалі нас буде цікавити тільки парність результату, тому зробимо ще один запит до всіх кульок, чим фактично обнулимо всі значення.
Тепер зробимо log_2(k) ітерації, на -ій ітерації знайдемо, в кольорах яких кульок на місці -го біта стоїть 1. Зробимо по одному запиту до всіх базових кульок, в кольорах яких є -ий біт. Тобто зараз на кульки цих кольорів ми дивились непарну кількість разів, а на всі інші парну. Тепер будемо проходитися до всіх інших кульках. Робимо запит до кульки, якщо результат парний, то цей біт 1, інакше 0. Щоб зберегти інваріант з парністю, робимо ще один запит до цієї ж кульки та переходимо далі до наступної кульки. В кінці ітерації знову робимо запит до базових кульок з одиничним бітом, щоб зробити всі значення парними.
Такий розв'язок використовує 2n(log_2(k)+1) операцій.
https://ideone.com/MV6rw1
Альтернативне рішення
Реалізуємо функцію solve(a), що приймає масив індексів кульок та встановлює їх відносні кольори — іншими словами розв'язує поставлену задачу. Складність функції визначимо як T_1(n) запитів, де n=len(a).
Скористаємося методом «розділяй та володарюй». Розділимо на два менших масиви та . Виконаємо solve(L) та solve(R). Для множин кульок та можемо залишити в них до розгляду лише по одній кульці кожного кольору. Залишається встановити пари кульок однакового кольору з та . Знайдемо множини таких кульок з та : для прикладу, знайти множину кульок з що мають однаковий колір з кулькою з множини можна проітерувавшись по та виконавши по запиту з кожною кулькою (також запам'ятавши значення результатів запитів), після чого необхідно виконати по запиту з кожною кулькою множини , та знову виконати по запиту з кожною кулькою з множини — тепер легко відрізнити кульки, колір який зустрічається серед кольорів кульок з . Отримані множини назвемо LToMerge та RToMerge.
Реалізуємо функцію merge(L,R), що приймає два масиви однакової довжини індексів кульок, та визначає пари кульок однакового кольору, при цьому вважає що кольори кульок з попарно різні, кольори кульок з попарно різні та множини кольорів кульок з та рівні. Тоді для коректного виконання достатньо буде викликати merge(LToMerge,RToMerge). Складність функції визначимо як T_2(n) запитів, де n=len(L)+len(R).
Реалізуємо merge(L,R) за допомогою метода «розділяй та володарюй». Розділимо на 2 масиви L_1 та L_2. Розділимо на 2 масиви R_1 та R_2 такі, що кольори кульок з L_1 відповідатимуть кольорам кульок з R_1, а кольори кульок з L_2 відповідатимуть кольорам кульок з R_2. Для прикладу спочатку виконаємо по одному запиту з кожною з кульок з (також запам'ятавши значення результатів запитів), після чого виконаємо по запиту з кожною з кульок з L_1 та знову виконаємо по запиту з кожною з кульок з — тепер легко відрізнити кульки, колір який зустрічається серед кольорів кульок з L_1. Тоді для коректного виконання достатньо буде викликати merge(L_1,R_1) та merge(L_2,R_2).
Складність рішення визначимо як запитів.
Нехай T_1(n)=C_1 \cdot n+2 \cdot T_1(\frac{n}{2}), T_2(n)=C_2 \cdot n+2 \cdot T_2(\frac{n}{2}). Нескладно помітити, що сумарна довжина масивів що є вхідними параметрами функції не більша за 2 \cdot n. Іншими словами T(n) \leq T_1(n)+T_2(2 \cdot n) = (C_1+2 \cdot C_2) \cdot n \cdot log(n).
Найменші значення C_1 та C_2 які журі змогло отримати при реалізації такого рішення рівні та відповідно. Рішення з такими параметрами C_1 та C_2 можна реалізувати враховуючи при вході у рекурсивні виклики з якими кульками виконувались останні запити. Реальна кількість запитів такого рішення звісно менша ніж 3 \cdot n \cdot log(n).