Автор, розробник, автор розбору: Ілля Пермяков
Спочатку помітимо, що числа, які не є префіксом жодного іншого числа, не можуть бути у одній підмножині. Тобто найкраща можлива відповідь це , де — кількість таких чисел. Виявляється, що завжди можна побудувати підмножини саме з такою відповіддю.
Для розв'язання цієї задачі існує багато жадібних алгоритмів, розглянемо один з них:
Виділимо усі такі числа, що не є префіксом жодного іншого числа. Занесемо ці числа у різні підмножини розміру 1. На початку, вважатимемо, що усі інші числа не належать жодній підмножині.
Переберемо ці числа, нехай зараз розглядаємо число .
Далі дивимось на кожне таке , що є в масиві , а також є префіксом . Якщо не належить жодній підмножині, то додаємо його до підмножини .
Таким чином, можна побачити, що усі числа, які ми не виділили, будуть належати одному з підмножин.
Сумарний час роботи рішення: O(n \cdot 19 \cdot log(n)) або O(n \cdot 19) в залежності від реалізації.