Не могу придумать логику для решения задачи
Не приходит идея для решения задачи, подскажите пожалуйста какую логику можно придумать для задачи ниже
На вход подается строка String, строка считается красивой, если ее подстроки имеют одинаковую длину, а также одинаковый набор символов, который одинаков. Пример красивых строк: 011011011; 101101101; 1010; 1; 0000; 111 Некрасивые строки: 000101; 10101; 0001001 Цель задачи: вывести минимальное количество шагов, за которое можно исправить некрасивую строку.
ПРИМЕР: 000101 - 1 так как мы можем изменить 0 на второй позиции на 1 и получим 010101 0001001 - 2 мы можем заменить все единицы на нули.
Идея считать нули и единицы, а потом из большего вычитать меньшее не подходит так как на первом примере получится что 4(нуля) вычесть 2(единицы) будет ответ 2 но как можно увидеть исправить можно за 1 шаг. Я думал что может создать заготовки (скажем там "красивые" заготовки, например 11; 00 И так далее), но по факту можно иногда просто поменять все цифры на противоположные и получится короче. Заранее благодарю за ответ.
Ответы (1 шт):
Пусть n - длина строки s. Переберём все её собственные делители d: d|n, 1 ≤ d < n.
Для каждого делителя вычислим число изменений строки чтобы сделать её красивой с периодом подстроки d. Для этого будем перебирать позиции в периоде k, 0 ≤ k < d.
Рассмотрим символы с индексами sk, sd+k, s2d+k, .... Если среди них больше нулей, то выгоднее заменять единицы нулями. Если наоборот, то заменим нули на единицы. Так или иначе мы отыскали минимальное число замен чтобы сделать разряд k периода d красивым. Чтобы сделать весь период красивым надо сложить число замен для всех разрядов.
За линейное время вычислено число замен до красивого периода d. Чтобы решить задачу в целом надо найти минимум числа замен по всем периодам. Сложность решения O(nσ0(n)), где σ0 - число делителей.
Искать делители n можно линейным поиском. Это не самый эффективный способ сам по себе, но в случае этой задачи линейный поиск мажорируется рассчётом расстояния до красивого периода.
ESkri в комментарии предложил "разбивать строку только на простое кол-во подстрок". Рассмотрим d1, d2: d1|d2|n. Тогда строка красивая по периоду d1 оказывается также красивой по периоду d2. То есть при поиске минимального количества замен период d1 можно не рассматривать: минимум замен по d1 не меньше чем минимум замен по d2.
Если количество периодов m = d/n - составное число, его можно разложить в произведение m = m1m2, 1 < m1, m2. А тогда dm1 - делитель n больший d. Следовательно рассматривать составные количества периодов не имеет смысла.
Новый алгоритм: переберём все p - простые делители n. Для каждого p вычислим d = n / p, для которого вычислим число замен. По всем p выберем минимум числа замен. Задача решена. Сложность O(nω(n)), где ω(n) - число простых делителей n. Она растёт медленнее σ0(n) (и медленнее log(n)), что даёт заметный выигрыш по времени.