Мы используем выбор наиболее частого, когда пытаемся за наименьшее число действий превратить подстроку фиксированной длины в нечётный палиндром, то есть решаем тут более ограниченную подзадачу. Далее мы используем это для проверки «можем ли за K операций сделать подстроку нечетным палиндромом», при этом мы уже пробуем двигать указатели и найти оптимум. В примере с ZYXAWA и K=1 будет происходить следующее:
когда указатель на левый элемент стоит на первом символе, то правый сможет уйти только до 3-го элемента (ZYZawa)
далее левый съезжает на Y, правый — на 4-й элемент (zYXYwa)
левый уходи на X, правый сможет отойти на последнего элемента. При этом тут мы заменим в подстроке XAWA символы на нечетных позициях на X или A — все равно, на четных самым частым является A, ничего не надо менять.
я не говорю про начертательную геометрию и все другие практически применимые виды геометрии, скажем так. Графика та же, рендереры. Я, скорее, про список n примечательных фактов и приёмов, которые могут пригодиться «когда-нибудь в какой-нибудь задаче». Вот это вообще моя любимое — энциклопедия замечательных точек треугольника faculty.evansville.edu/ck6/encyclopedia/ETC.html
интересная параллель с гаммами. Примерно то же самое, наверное, с геометрией, которая не вычислительная, а которой больше в школе и на математических кружках развлекаются. Сейчас уже практической пользы сравнительно мало, но вот сам процесс решения очень может завлечь (ну у меня по крайней мере так было, за всех не говорю).
Где нужны сами палиндромы — сложно сказать. Возможно, при анализе каких-то паттернов в последовательности ДНК может пригодиться (или это моя фантазия). А два указателя — достаточно популярная техника. Можно считать скользящее среднее в окне, да почти любые статистики в окне, если мы говорим об анализе временных рядов. Тут надо задачи конкретные смотреть, чтобы дальше разбираться. Например, можно вот это почитать algorithmica.org/tg/mergesort
Спасибо, что обратили внимание на крайний случай! Если все батчи заполненные, то в каждом будет по одному элементу, так как батчей всего N (последний элемент в отдельном батче и N-1 нормальных). Это в некотором смысле вырожденный случай, внутри одного батча не может образоваться пара — элементов не хватает.
Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов.
В этом предложении мы вводим интересующий нас объект. У этого объекта есть какое-то свойство — максимальная разница между соседними элементами. И найти её мы стремимся без использования сортировок (что и происходит далее), то есть без построения самого объекта.
Если речь отдельно про сортировку — то да, в общем случае можем упереться в n log n, но если у нас есть знание о равномерном распределении элементов, то смысл есть. Аналогично сортировку подсчётом выгоднее использовать, когда разброс значений относительно небольшой.
Это условное название задачи, а не точная формулировка. Сама формулировка приведена сразу ниже
Дан массив из N целых чисел. Он никак не упорядочен, а числа могут повторяться. Предположим, что мы отсортировали его и вычислили разницу между каждой парой последовательных элементов. Необходимо найти максимальную такую разницу и сделать это наиболее оптимальным способом.
Допустим, есть 100 элементов. Самый маленький равен 1, самый большой 10'000, а все остальные как-то расположены на отрезке от 5001 до 5100. Тогда все элементы, кроме двух крайний попадут в один батч. Иными словами, есть батч, в котором находится O(n) элементов. В этом случае общее время исполнения будет зависеть от того, какая сортировка используется уже внутри батчей. Если это квадратичная сортировка, то итоговая сложность O(n^2), когда в одном батче оказывается O(n) элементов. Если же использовать что-то побыстрее (например, сортировку слиянием), то получим O(n log n). Мы могли бы в таком случае сразу использовать более стандартную сортировку (можно опять сортировку слиянием взять) и получить те же O(n log n).
когда указатель на левый элемент стоит на первом символе, то правый сможет уйти только до 3-го элемента (ZYZawa)
далее левый съезжает на Y, правый — на 4-й элемент (zYXYwa)
левый уходи на X, правый сможет отойти на последнего элемента. При этом тут мы заменим в подстроке XAWA символы на нечетных позициях на X или A — все равно, на четных самым частым является A, ничего не надо менять.
В формулировке говорится про максимальную разницу между элементами упорядоченного массива, а изначально элементы стоят в произвольном порядке.
В этом предложении мы вводим интересующий нас объект. У этого объекта есть какое-то свойство — максимальная разница между соседними элементами. И найти её мы стремимся без использования сортировок (что и происходит далее), то есть без построения самого объекта.
Мы задали длину интервала таким образом, чтобы всего интервалов вышло примерно N штук. То есть U/(N-1) это длина интервала, а не их количество