Здесь пара комментариев (для себя и других) касательно разбора задачи 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$$$.

Savvy?

Перегруппировав слагаемые (убрав старые операторы сумм и введя новые), получим вот такую формулу:

$$$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}$$$ при переходе от координат к самим символам — не поменяет смысла).

#include <iostream>
#include <string>

const int M = 20;

int cnt[M][M];
int m;

#define LOG 0
#define INFO 1
#define TRACE 2

void dumpMask(unsigned mask) {
  std::cout << "{";
  bool first = true;
  for (unsigned c = 0; c != m; ++c) {
    if ( (1 << c) & mask) {
      if (!first)
        std::cout << ", ";
      std::cout << (char) (c + 'a');
      first = false;  
    }
  }
  std::cout << "}";
}

int besties[1 << M];
unsigned bitscnt[1 << M];

int solve() {

  unsigned emask = 1 << m;
  unsigned fullmask = emask - 1;
  unsigned totalcnt = 0;
  
  bitscnt[0] = 0;
  
  for (unsigned curmask = 0; curmask != emask; curmask++) {
  
    unsigned bestx = 0;
    unsigned bestxmask = 0;
    int bestres = 0;
    unsigned posx = 0; // will be initialized during first for(x) iteration

#if LOG >= INFO
    std::cout << "mask "; dumpMask(curmask); std::cout << "\n";    
#endif 

    // x and y are alphabetical symbol numbers
    // posx - is x symbol index in keyboard, it matches number of bits in curmask.
    for (unsigned x = 0, xmask = 1; x != m; ++x, xmask = xmask << 1) {
      if (!(xmask & curmask)) continue;
      
      unsigned prevmask = curmask ^ xmask;      
      int res = besties[prevmask];
                  
      if (!posx) posx = bitscnt[prevmask]+1;
      
#if LOG >= TRACE
      std::cout << " x " << (char)(x + 'a') << "\n";
      std::cout << " prevr " << res << "\n";
      std::cout << " posx " << posx << "\n";      
#endif
  
      for (unsigned y = 0, ymask = 1; y != m; ++y, ymask = ymask << 1) {
        if (y == x)
          continue;

        // If y belong to curmask, add posx, otherwise substract it.          
        res += curmask & ymask ? cnt[y][x] * posx : -cnt[y][x] * posx;
      }
      
#if LOG >= TRACE      
      std::cout << " res " << res << "\n";      
#endif
      
      if (!bestxmask || res < bestres) {
        bestx = x;
        bestxmask = xmask;
        bestres = res; 
      }
    }
    
#if LOG >= INFO    
    std::cout << "  bestx ";
    bestxmask ? std::cout << (char)(bestx + 'a') : std::cout << "n/a";
    std::cout << "\n";
    std::cout << "  bestres " << bestres << "\n";    
#endif
    
    besties[curmask] = bestres;
    bitscnt[curmask] = posx;    
  }
  
  return besties[fullmask];
}

int main() {
  std::string str;
  int n;
  std::cin >> n >> m >> str;
  
  unsigned prevc = str[0] - 'a';
  for (unsigned i = 1; i != n; ++i) {
    unsigned c = str[i] - 'a';
    ++cnt[prevc][c];
    ++cnt[c][prevc];
    prevc = c;
  }
  
  std::cout << solve();
  
  return 0;
}