Editorial

Блок 1

Проітеруємось по всім кулькам і виконуватимемо по запиту з кожною з нею. Рівно один раз як результат отримаємо значення $2$. Це відбудеться при запиті з одною з кульок, що повторюється. Іншу можна знайти виконавши ще по одному запиту з кожною з кульок.

Блок 2

Не обмежуючи загальності вважатимемо, що перша кулька — кулька кольору $1$. Далі проітеруємося по всім іншим кулькам та виконаємо запит з кожною з них. Якщо значення, яке отримали рівне (останньому відомому значенню кульок кольору $1$) + 1, то колір цієї кульки також $1$, інакше $2$. Для того, щоб однозначно визначати колір при черговому запиті, після кожного запиту виконуватимемо запит з кулькою номер $1$.

Блок 5

Проітеруємось по всім кулькам та виконаємо запит з кожною з них. Відсортуємо отримані пари (значення результату запиту, номер кульки) по незростанню першого параметру. Тепер у порядку встановленому цим списком знову виконуватимемо по запиту з кожною кулькою — отримуючи результат запиту, можна однозначно визначити колір кульки.

Інший варіант розв'язати цей блок. Пройдемось двічі по всіх кульках зліва направо. Нехай $a_i$ — значення, яке отримали при першому проході при запиті до $i$-ої кульки, $b_i$ — при другому проході. Тоді є рівно $b_i-a_i$ кульок такого ж кольору, які такі ж, як і $i$-та кулька. Враховуючи, що кількість кульок кожного кольору різна, ця інформація також дозволяє відновити всі кольори.

Всі інші блоки

Зробимо один прохід по кульках зліва направо та знайдемо всі позиції, де колір зустрічається вперше. Назвемо їх базовими кульками. Розставимо на ці позиції кольори від $1$ до $k$. Надалі нас буде цікавити тільки парність результату, тому зробимо ще один запит до всіх кульок, чим фактично обнулимо всі значення.

Тепер зробимо $lo{g}_2(k)$ ітерації, на $i$-ій ітерації знайдемо, в кольорах яких кульок на місці $i$-го біта стоїть 1. Зробимо по одному запиту до всіх базових кульок, в кольорах яких є $i$-ий біт. Тобто зараз на кульки цих кольорів ми дивились непарну кількість разів, а на всі інші парну. Тепер будемо проходитися до всіх інших кульках. Робимо запит до кульки, якщо результат парний, то цей біт 1, інакше 0. Щоб зберегти інваріант з парністю, робимо ще один запит до цієї ж кульки та переходимо далі до наступної кульки. В кінці ітерації знову робимо запит до базових кульок з одиничним бітом, щоб зробити всі значення парними.

Такий розв'язок використовує $2n(lo{g}_2(k)+1)$ операцій.

https://ideone.com/MV6rw1

Альтернативне рішення

Реалізуємо функцію $solve(a)$, що приймає масив індексів кульок та встановлює їх відносні кольори — іншими словами розв'язує поставлену задачу. Складність функції $solve$ визначимо як $T_1(n)$ запитів, де $n=len(a)$.

Скористаємося методом «розділяй та володарюй». Розділимо $a$ на два менших масиви $L$ та $R$. Виконаємо $solve(L)$ та $solve(R)$. Для множин кульок $L$ та $R$ можемо залишити в них до розгляду лише по одній кульці кожного кольору. Залишається встановити пари кульок однакового кольору з $L$ та $R$. Знайдемо множини таких кульок з $L$ та $R$: для прикладу, знайти множину кульок з $L$ що мають однаковий колір з кулькою з множини $R$ можна проітерувавшись по $L$ та виконавши по запиту з кожною кулькою (також запам'ятавши значення результатів запитів), після чого необхідно виконати по запиту з кожною кулькою множини $R$, та знову виконати по запиту з кожною кулькою з множини $L$ — тепер легко відрізнити кульки, колір який зустрічається серед кольорів кульок з $R$. Отримані множини назвемо $LToMerge$ та $RToMerge$.

Реалізуємо функцію $merge(L,R)$, що приймає два масиви однакової довжини індексів кульок, та визначає пари кульок однакового кольору, при цьому вважає що кольори кульок з $L$ попарно різні, кольори кульок з $R$ попарно різні та множини кольорів кульок з $L$ та $R$ рівні. Тоді для коректного виконання $solve$ достатньо буде викликати $merge(LToMerge,RToMerge)$. Складність функції $merge$ визначимо як $T_2(n)$ запитів, де $n=len(L)+len(R)$.

Реалізуємо $merge(L,R)$ за допомогою метода «розділяй та володарюй». Розділимо $L$ на 2 масиви $L_1$ та $L_2$. Розділимо $R$ на 2 масиви $R_1$ та $R_2$ такі, що кольори кульок з $L_1$ відповідатимуть кольорам кульок з $R_1$, а кольори кульок з $L_2$ відповідатимуть кольорам кульок з $R_2$. Для прикладу спочатку виконаємо по одному запиту з кожною з кульок з $R$ (також запам'ятавши значення результатів запитів), після чого виконаємо по запиту з кожною з кульок з $L_1$ та знову виконаємо по запиту з кожною з кульок з $R$ — тепер легко відрізнити кульки, колір який зустрічається серед кольорів кульок з $L_1$. Тоді для коректного виконання $merge$ достатньо буде викликати $merge(L_1,R_1)$ та $merge(L_2,R_2)$.

Складність рішення визначимо як $T(n)$ запитів.

Нехай $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})$. Нескладно помітити, що сумарна довжина масивів що є вхідними параметрами функції $merge$ не більша за $2\cdot n$. Іншими словами $T(n)\le T_1(n)+T_2(2\cdot n)=(C_1+2\cdot C_2)\cdot n\cdot log(n)$.

Найменші значення $C_1$ та $C_2$ які журі змогло отримати при реалізації такого рішення рівні $1.5$ та $0.75$ відповідно. Рішення з такими параметрами $C_1$ та $C_2$ можна реалізувати враховуючи при вході у рекурсивні виклики з якими кульками виконувались останні запити. Реальна кількість запитів такого рішення звісно менша ніж $3\cdot n\cdot log(n)$.