Here are some additional notes for 1238E's tutorial, which is kindly made by awoo и Roms. I got stuck there for a while with final expression.

( I even wrote solution with traces, haha (see after cut) )

First, let's think about base expression for total moves amount. And then in top-down way try to come to solution.

Moving rightward, for each symbol $$$s$$$, with keyboard position $$$x$$$ we will accumulate all moves between that symbol and all symbols at left. Obviously this is how we finally count all the moves. So here is a base expression:

$$$cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} (x - y)$$$

Where $$$x$$$ и $$$y$$$ are symbol coordinates on keyboard. And $$$cnt_{xy}$$$ is amount of moves between those symbols, namely $$$s_x$$$ и $$$s_y$$$ .

(well, names are a bit different, but it allows to use shorter expressions)

So, how to come to that nice expression which we can see (but perhaps can't parse) at the end of awoo's tutorial for 1238E?

We've got to play with symbols and sums a little bit!

At first, expand $$$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$$$

The game would over if we wouldn't know the context. But we do! At least following things:

• $$$cnt_{xy}=cnt_{yx}$$$
• Names "x" и "y" are merely local variables and fixed only within respective "$$$\sum$$$".
• As long as base expression consists of addition and substration operations we are in right to swap "$$$\sum$$$" symbols. But watch signs and local var names (watch or lay an egg!).

So, take a look at the right side of expanded base expression:

$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} y$$$

We can rewrite it as follows:

$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$

(see? we just swapped the var names).

And now, let's think a bit more about right and left parts of that expanded base expression:

This:

$$$\sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} x$$$

instead enumerates all possible $$$x$$$ values in combination with possible $$$y$$$ values which are at the left side from the $$$x$$$.

And this:

$$$\sum_{y=1}^{n} \sum_{x=1}^{y-1} cnt_{xy} x$$$

instead enumerates all possible $$$x$$$ values in combination with possible $$$y$$$ values which are at the (!) right side from $$$x$$$.

Savvy?

Now regroup expression components. Remove old sum operators, and introduce new ones instead:

$$$cnt = \sum_x ( \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x ) $$$

Suddenly, everything begins to make sence! For each $$$x$$$ we got that very expression (nice expression) from legacy tutorial!

$$$cnt_x = \sum_{y \in mask} cnt_{xy} x - \sum_{y \notin mask} cnt_{xy} x $$$

(well, in original article guys use $$$pos_x$$$ instead of $$$x$$$, as for $$$cnt_{xy}$$$ it means the same when you replace keyboard indices with respective alphabetical symbol values).

#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;
}