Slow man's solutions. 1238, E. Покупка клавиатуры — некоторые пояснения к legacy разбору

Revision en4, by dyatkovskiy, 2019-10-13 20:20:22

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 all 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 all 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).

My solution
Tags #1238e, #editorial, #round #74

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English dyatkovskiy 2019-10-13 20:20:22 8
en3 English dyatkovskiy 2019-10-13 20:19:35 14 Tiny change: '\n(see? we've basically swapped t' -> '\n(see? we just swapped t'
en2 English dyatkovskiy 2019-10-13 20:18:29 23 Tiny change: 'Here's few comments for [123' -> 'Here are some additional notes for [123'
ru6 Russian dyatkovskiy 2019-10-13 20:15:53 22
en1 English dyatkovskiy 2019-10-13 20:14:55 5970 Initial revision for English translation
ru5 Russian dyatkovskiy 2019-10-12 18:24:27 11
ru4 Russian dyatkovskiy 2019-10-12 18:23:52 2804
ru3 Russian dyatkovskiy 2019-10-12 16:42:07 43
ru2 Russian dyatkovskiy 2019-10-12 16:26:33 63 Мелкая правка: 'решению.\n[cut]\n\' -> 'решению.\n\n[cut]\n\'
ru1 Russian dyatkovskiy 2019-10-12 15:06:15 3153 Первая редакция (опубликовано)