Здесь пара комментариев (для себя и других) касательно разбора задачи 1238E сделанного пользователями awoo и Roms. Я там не сразу понял — как получается конечная формула для перебора символа.
( заморочился и написал код с трассировкой (см. под катом) )
Давайте вначале придумаем общую суммарную формулу, которая отразит количество всех перемещений, и потом, используя нисходящий подход прийдем к решению.
Двигаясь вправо, для каждого символа $$$s$$$, имеющего на клавиатуре позицию $$$x$$$ будем учитывать все перемещения между ним и символами слева. Так, очевидно, мы в итоге учтем все перемещения. Этот подсчет можно выразить вот так:
$$$cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} (x - y)$$$
Здесь $$$x$$$ и $$$y$$$ — это координаты символов на клавиатуре. А $$$cnt_{xy}$$$ — это соответсвенно общее количество переходов между символами на клавиатуре $$$s_x$$$ и $$$s_y$$$ .
(да — обозначения немного отличаются, но зато формула получается более компактная).
Так как же получается то славное выражение, которое приведено awoo в конце разбора для задачи 1238E?
Надо немного поиграть с символами и попереставлять значки сумм.
Для начала раскроем скобки $$$x-y$$$:
$$$cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} x - \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} y$$$
Без знания предметной области формулу уже не упроситить. Но мы знаем, что:
- $$$cnt_{xy}=cnt_{yx}$$$
- Обозначения "x" и "y" — на самом деле локальные и фиксированы только внутри той или иной суммы.
- В выражении, состоящем только из сумм и разностей, идущие подряд значки сумм ($$$\sum$$$) мы можем менять местами (главное тут — не облажаться с теми самыми локальными переменными).
Поэтому, давайте внимательно взглянем на правую часть формулы:
$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} y$$$
Мы ее можем переписать вот так:
$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$
(просто поменяли названия переменных).
А теперь задумаемся о смысле левой и правой частей все той же формулы:
Вот это:
$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} x$$$
На самом деле перебирает все возможные символы $$$x$$$ и все возможные символы $$$y$$$, которые стоят слева от $$$x$$$.
А вот это:
$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$
На самом деле перебирает все возможные символы $$$x$$$ и все возможные символы $$$y$$$, которые стоят (!) справа от $$$x$$$.
Перегруппировав слагаемые (убрав старые операторы сумм и введя новые), получим вот такую формулу:
$$$cnt = \sum_x ( \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x ) $$$
Внезапно, все сказанное в legacy разборе обретает смысл. Для каждого отдельно взятого $$$x$$$ мы приходим к той самой, славной, формуле
$$$cnt_x = \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x $$$
(ну, только там $$$x$$$ обозначался как $$$pos_x$$$, $$$cnt_{xy}$$$ при переходе от координат к самим символам — не поменяет смысла).