Перетасуй#515

Перетасуй (Editorial)

Автор: Костянтин Денисов

Розробник: Ілля Пермяков

Розбір підготовано: Костянтин Денисов

Нехай індекси утворюють небезпечну пару, якщо i<j та gcd(i,j)>1. Ціна масиву — це максимум b_i+b_j по всіх небезпечних парах (або , якщо їх немає).

Є позиції, які не входять у жодну небезпечну пару: це та всі прості p>n/2. На них жадібно вигідно ставити найбільші числа, бо вони ніяк не впливають на максимум.

Після цього візьмемо найбільше число, яке ще не поставили, і позначимо його . Будь-яка позиція, що лишилась, має хоча б одну небезпечну пару, тому значення гарантовано входить у якийсь вираз b_i+b_j. Отже відповідь не менша за . Далі розглянемо випадки mx=0,1,2,3 (бо a_i\le 3).

1. mx=0. Усі числа нулі, відповідь тривіальна.

2. mx=1. Єдина причина отримати ціну — це наявність небезпечної пари 1+1. Тому ціну можна зробити тоді і тільки тоді, коли всі одиниці стоять на попарно взаємно простих позиціях. Найпростіша конструкція: ставити одиниці на прості індекси (вони попарно взаємно прості). Якщо простих позицій (разом з , якщо потрібно) вистачає, відповідь , інакше відповідь .

3. mx=2. Можливі відповіді .

Щоб не отримати небезпечну пару 2+2=4, усі двійки мають стояти на попарно взаємно простих позиціях. Якщо це неможливо, відповідь .

Якщо двійки можна так розставити, лишається відрізнити від . Ціну можна зробити лише якщо немає небезпечної пари 2+1=3, тобто всі одиниці стоять на позиціях, взаємно простих з усіма позиціями двійок.

Конструкція для перевірки така: ставимо всі на найбільші прості позиції (позначимо ці прості через множину ), а одиниці ставимо лише в позиції, які не діляться на жоден простий із . Якщо таких позицій вистачає для всіх одиниць, відповідь , інакше відповідь .

4. mx=3. Можливі відповіді 3,4,5,6.

Щоб не отримати 3+3=6, трійки мають стояти на попарно взаємно простих позиціях. Якщо це неможливо, відповідь .

Далі, щоб мати ціну не більшу за , потрібно заборонити пари 3+2=5 та 2+2=4, тобто всі позиції з числами або разом мають бути попарно взаємно прості. Якщо це неможливо, але трійки окремо розставити можна, відповідь .

Тепер перевіримо, чи можна зробити відповідь . Для цього треба заборонити всі суми, більші за , а саме пари 2+2, 3+1, 3+2, 3+3. Умови набувають вигляду:

  • усі двійки стоять на попарно взаємно простих позиціях;

  • усі трійки стоять на попарно взаємно простих позиціях;

  • кожна позиція з взаємно проста з кожною позицією з (тобто двійки й трійки можна розглядати як один спільний набір на попарно взаємно простих позиціях);

  • кожна одиниця стоїть на позиції, взаємно простій з кожною позицією трійки (щоб не було 3+1).

Конструкція така: ставимо на найбільші прості позиції (позначимо ці прості через S_3), ставимо на інші прості позиції, а ставимо лише в позиції, які не діляться на жоден простий із S_3. Якщо позицій для одиниць вистачає, відповідь , інакше відповідь .

Реалізаційно. Потрібні прості числа до і можливість швидко рахувати позиції, що діляться на задану множину простих. Це робиться решетом Ератосфена та проходом по кратних.

Складність. Решето O(n\log\log n), усі маркування та побудова перестановки , пам'ять .