Множини#476

Множини (Editorial)

Автор, розробник, автор розбору: Ілля Пермяков

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

Для розв'язання цієї задачі існує багато жадібних алгоритмів, розглянемо один з них:

  1. Виділимо усі такі числа, що не є префіксом жодного іншого числа. Занесемо ці числа у різні підмножини розміру 1. На початку, вважатимемо, що усі інші числа не належать жодній підмножині.

  2. Переберемо ці числа, нехай зараз розглядаємо число .

  3. Далі дивимось на кожне таке , що є в масиві , а також є префіксом . Якщо не належить жодній підмножині, то додаємо його до підмножини .

Таким чином, можна побачити, що усі числа, які ми не виділили, будуть належати одному з підмножин.

Сумарний час роботи рішення: O(n \cdot 19 \cdot log(n)) або O(n \cdot 19) в залежності від реалізації.