У цій задачі потрібно було порахувати, скільки голосів було за кожен з варіантів та обрати, який з них більший.
Спробуємо вибрати такі карточки, щоб суми мали спiльний дільник 2. Оскільки карточок щонайменше 4, то хоча б одне з наступних тверджень правдиве:
є хоча б дві карточки з парним числом
є хоча б одна карточка з парним числом і дві з непарним
є хоча б чотири карточки з непарним числом
Поділимо всі числа на парні та непарні та виберемо карточки так, щоб обидві суми були парними.
Можливі 3 різні відповіді: 2, 3, 4. Розберемо випадки, коли яка відповідь є правильною.
Якщо всі числа в послідовності \(a\)
рівні (всі 4 або всі 7), то достатньо 2 кафе,
як це показано в першому прикладі умови.
Розберемо випадок, коли є 3 кафе. В такому випадку дороги мають
позначки 4, 4, 7 або
4, 7, 7, як показано на
зображенні нижче. Розберемо випадок, коли дороги мають позначки
4, 4, 7. Помітимо, що якщо ми
знаходимось в вершині 2, то з неї можна перейти тільки за позначкою
4, а також в вершину 2 можна перейти тільки за позначкою
4. Тому, якщо відповідь 3, між будь-якими послідовними
7 має бути парна кількість 4. Зауважте, що
якщо шлях починається (чи закінчується) в вершині 2, то на початку (чи в
кінці) буде непарна кількість 4. Випадок з позначками
4, 7, 7 розбирається по
аналогії.
Інакше, відповідь дорівнює 4. Це показано на зображенні нижче.
Зверніть увагу, що в такому випадку кожне кафе має суміжні дороги і з
міткою 4 і з міткою 7.
Будемо будувати табличку так, щоб в перших \(a_1\) рядках було найбільше значень 1, далі в наступних \(a_2\) рядках було найбільше значень 2 і так далі. Аналогічно зі стовпцями. Нехай \(r_i\) – значення, якого повинно бути найбільше в \(i\)-му рядку, а \(c_j\) в \(j\)-му стовпці.
Зробимо шахове розфарбування таблички. Якщо клітинка \((i, j)\) чорна, поставимо в неї \(r_i\), інакше \(c_j\).
Покажемо, чому така табличка підходить під потрібну умову. Подивімося, що буде в \(i\)-му рядку: \(c_1 r_i c_3 r_i \dots r_i c_m\) – порядок може трішки відрізнятись залежно від парностей номера рядка та \(m\), але ми поставимо як мінімум \(\lfloor \frac{m}{2} \rfloor\) значень \(r_i\). Тепер ще згадаємо, що як мінімум 2 значення серед \(c_j\) повинні бути рівними \(r_i\), а отже хоча б одне зі значень \(c_1, c_3, \dots, c_m\). Це означає, що в \(i\)-му рядку значень \(r_i\) буде понад половину, а отже і більше ніж будь-яких інших значень. Аналогічно для стовпців.
Розглянемо деякі властивості фінального заповнення. Якщо є трійка \(i < j < k\) така, що \(d_i > d_j\) та \(d_k > d_j\), то заповнити неможливо, адже клітинку в \(j\)-му стовпці над заповненими нижніми \(d_j\) клітинками неможливо заповнити ні зліва, ні справа. Отже, масив \(d\) повинен спершу зростати, а потім спадати. Нехай \(h=max(d_i)\). Відповідно, останні \(h\) елементів масиву \(l\) повинні спадати і останні \(h\) елементів масиву \(r\) також повинні спадати. Тут під словами спадати та зростати насправді мається на увазіне зростатии та не спадати, оскільки можуть бути однакові значення, але для простоти розуміння вибрано не зовсім правильні терміни. Для перших \(n-h\) елементів масивів \(l\) та \(r\) повинно виконувати \(l_i+r_i=m\).
Тепер покажемо, що якщо існує пара елементів \(a \in l\), \(b \in r\) така, що \(a+b=m\), то ця пара повинна бути серед перших \(n-h\) рядків. Очевидно, що якщо один з них серед перших \(n-h\) рядків, то й інший теж, тому припустимо від супротивного, що обидва ці значення знаходяться серед останніх \(h\) рядків. Оскільки останні рядки в масивах \(l\) та \(r\) не зростають, то повинно виконуватись \(a \le l_{n-h+1}\) та \(b \le r_{n-h+1}\). Але \(l_{n-h+1} + r_{n-h+1} < m\), оскільки в цьому рядку хоча б 1 клітинка заповнюється знизу. Вийшла суперечність. Отже, ми можемо жадібно обирати пари з сумою \(m\) на перші \(n-h\) рядків, а далі посортувати всі значення в \(l\), всі значення в \(r\) та подивитись, чи масив \(d\) підходить.
Тепер потрібно порахувати кількість способів. Останні \(n-h\) рядків масивів \(l\), \(r\) та масив \(d\) визначаються однозначно. Різниця лише в перших \(n-h\) рядках, які можна довільно переставляти (однаково в обох масивах \(l\) та \(r\)). Тож кількість способів буде рівна \(\frac{(n-h)!}{cnt_0! cnt_1! \dots cnt_m!}\), де \(cnt_i\) – скільки разів зустрічається \(i\) серед перших \(n-h\) елементів масиву \(l\).
Складність розв’язку \(O((n + m) log n)\) або \(O(n+m)\), якщо робити сортування підрахунком.
Для кожного запиту другого типу достатньо, щоб було хоча б одне потрібне значення і не було більших значень, а отже щоб виконати запит другого типу немає сенсу робити більше ніж 1 запит першого типу. Також якщо для якогось запиту другого типу уже стоять правильні значення, то немає сенсу робити жодного запиту першого типу. Фактично, якщо якийсь запит першого типу можна зробити і пізніше, то будемо робити його пізніше.
Будемо симулювати запити від початку. Нехай, зараз запит \(p\), \(v\) і нехай \(q\) – максимальний префікс запиту, який буде пізніше зі значенням меншим за \(v\). Якщо \(q \ge v\), то це неможливо, адже виходить, що нам потрібно пізніше на довшому префіксі отримати менше значення максимуму. Також значення \(v\) не можна ставити в перші \(q\) клітинок. Тепер розглянемо клітинки від \(q+1\) до \(p\) та чи може на цих клітинках зберігатись якісь потрібні в майбутньому значення. Будь-яких значень більших за \(v\) там бути не може, оскільки теперішній запит був би поганий. А будь-які значення менші за \(v\) уже неважливі, оскільки ми знаємо, що в майбутньому усі запити зі значеннями меншими за \(v\) будуть максимум до \(q\). Отже, ми можемо в будь-яку з цих клітинок ставити значення \(v\). Поставимо в клітинку \(q+1\), адже так нам можливо вийде зекономити запит першого типу, якщо буде коротший запит зі значенням \(v\).
Залишилось питання, як знайти \(q\) для кожного запиту. Це можна зробити, якщо спершу пройтись по всіх запитах з кінця і використати дерево Фенвіка чи іншу структуру даних для знаходження максимуму на проміжку. Ми можемо зберігати найдовший префікс для конкретного значення в цій структурі даних.
Складність розв’язку \(O(n log n)\).
Оберемо випадковий порядок символів, надалі ми можемо вважати загаданий порядок символів випадковим. Знайдемо перший символ – запитаємо кількість інверсій в даному порядку і якщо перший символ перенести в кінець. Якщо стало менше, то перший символ 7, якщо більше, то 4.
Тепер за одну операцію можна взнати кількість 4 і 7 на певному префіксі. Для цього перенесемо перший символ на позицію \(p\) та залежно від першого символу абсолютне значення на скільки змінилась кількість інверсій буде рівною кількості 4 чи 7 відповідно.
Будемо будувати потрібно порядок одночасно і з початку і з кінця. Нехай \(l\) – різниця між кількість 4 і кількість 7 на побудованому префіксі, \(r\) – різниця між кількістю 7 і кількістю 4 на суфіксі. Візьмемо шматок з \(2 min(l, r) + 1\) елементів та порахуємо скільки серед них 4 і 7. Якщо більше четвірок, то додамо його до префікса, інакше до суфікса. Зауважимо, що таким чином баланс ніколи не стане від’ємним, а \(l\) чи \(r\) після такої операції збільшаться. Скільки ж операцій використає такий метод. Якщо \(l < r\), то це означає, що серед невідомих елементів понад 4, а отже оскільки порядок випадковий, то з імовірністю більше 0.5 ми будемо додавати саме префікс. Відповідно кількість операцій можна оцінити як \(O(\sqrt n)\). На практиці, такий розв’язок для \(n=10^4\) в середньому виконує близько 80 операцій та на великій кількості запусків не зробив більше ніж 130 операцій.