Editorial for Baltic OI '13 P6 - Vim - DMOJ: Modern Online Judge

Editorial for Baltic OI '13 P6 - Vim

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

For any string $s$ ~s~, let $f(s)$ ~f(s)~ denote the minimum number of key presses Victor needs to do to remove all es from $s$ ~s~.

For any string $s$ ~s~ with some letters underlined, let $g(s)$ ~g(s)~ denote the minimum number of key presses Victor needs to do so that the cursor is at every underlined letter at least once.

Lemma 1. $f(l_1 s_1 \underbrace{e \dots e}_{n_2} l_2 s_2 \dots \underbrace{e \dots e}_{n_k} l_k s_k) = 2(n_2 + \dots + n_k) + g(\underline{l_1} s_1 \dots \underline{l_k} s_k)$ if $l_1, \dots, l_k$ ~l_1, \dots, l_k~ are letters different from e and $n_2, \dots, n_k \ge 1$ ~n_2, \dots, n_k \ge 1~.

Proof. Let $t = l_1 s_1 \underbrace{e \dots e}_{n_2} l_2 s_2 \dots \underbrace{e \dots e}_{n_k} l_k s_k$ and $s = \underline{l_1} s_1 \dots \underline{l_k} s_k$ .

" $\le$ ~\le~" Let $o_1, \dots, o_p$ ~o_1, \dots, o_p~ be some operations on $s$ ~s~ that visit each letter at least once. At the first point, when the cursor is at the letter $\underline l_i$ ~\underline l_i~ (for $2 \le i \le k$ ~2 \le i \le k~), insert $n_i$ ~n_i~ times the operations hx. This yields a sequence of $2(n_2 + \dots + n_k) + p$ ~2(n_2 + \dots + n_k) + p~ operations on $t$ ~t~ that delete all the es.

" $\ge$ ~\ge~" Victor has to do the operation x exactly $n_2 + \dots + n_k$ ~n_2 + \dots + n_k~ times (once for each e). To move the cursor to some letter e, he has to move it to the following letter and then issue h. Therefore, the cursor visits the letters $l_1, \dots, l_k$ ~l_1, \dots, l_k~ at least once. $\square$ ~\square~

Using Lemmas 1 and 2, it only remains to find $g(s)$ ~g(s)~ for strings $s$ ~s~ not containing the letter e (with some letters underlined). This is an instance of the travelling salesman problem, but the corresponding graph has some additional structure described by the following two lemmas.

Lemma 2. If the cursor is at some position $p$ ~p~ and Victor does some sequence of operations h, $o_1, \dots, o_k$ ~o_1, \dots, o_k~ with $o_1 \ne h$ ~o_1 \ne h~ (or $k = 0$ ~k = 0~), then Victor can instead do a shorter sequence of operations which visit the same letters, apart from at most the letter at position $p-1$ ~p-1~.

Proof. Let $l$ ~l~ be the letter at position $p$ ~p~. If $o_1 \ne$ ~o_1 \ne~ f $l$ ~l~ (or $k = 0$ ~k = 0~), then Victor can do the operations $o_1, \dots, o_k$ ~o_1, \dots, o_k~. Otherwise, he can do the operations $o_2, \dots, o_k$ ~o_2, \dots, o_k~. $\square$ ~\square~

Lemma 3. Assume Victor does the minimum number of key presses to visit each underlined letter in $s$ ~s~ at least once. Then Victor will not do operation h more than once with the cursor at the same position.

Proof. Otherwise, Victor does the operation h two times with the cursor at the same position and such that one of the following operations is different from h. Therefore, Victor could shorten his sequence of operations according to Lemma 3. $\square$ ~\square~

It follows, that Victor gets the minimum number of key presses like in the following picture where each underlined character (represented by a dot in the picture) is contained in one of the intervals spanned by the horizontal arrows from right to left (which can have length $0$ ~0~) and each such arrow ends at an underlined letter.

This observation yields an $\mathcal O(N^2 S)$ ~\mathcal O(N^2 S)~ solution: It is easy to find a suitable recurrence relation for the minimum number $r(a, b)$ ~r(a, b)~ of key presses to visit all underlined letters up to position $a$ ~a~ with the cursor ending up at position $b$ ~b~.

An $\mathcal O(N S^2)$ ~\mathcal O(N S^2)~ solution works roughly as follows:

For simplicity, assume that operation f $c$ ~c~ moves the cursor infinitely far away to the right if the character $c$ ~c~ does not appear anywhere to the right of the current cursor position. Apparently, this does not change the answer.

Let $p(a, c)$ ~p(a, c)~ be the minimum number of key presses before or after which the cursor is to the left of $a$ ~a~ such that the cursor lands on or passes position $a$ ~a~ exactly once and with operation f $c$ ~c~.

Let $q(a, c, d)$ ~q(a, c, d)~ be the minimum number of key presses before or after which the cursor is to the left of $a$ ~a~ such that the cursor lands on or passes position $a$ ~a~ exactly three times: the first time with operation f $c$ ~c~, the second time with operation h and the third time with operation f $d$ ~d~.

Let $s_i$ ~s_i~ be the $i^\text{th}$ ~i^\text{th}~ character of the string, let

$\displaystyle u_i = \begin{cases} \infty, & \text{if the }i^\text{th}\text{ character is underlined} \\ 0, & \text{otherwise} \end{cases}$

and let

$\displaystyle \kappa_{c,d} = \begin{cases} \infty, & c = d \\ 0, & c \ne d \end{cases}$

Then the following recurrence relations hold:

$\displaystyle p(a+1, c) = \min\begin{cases} p(a, c) + \kappa_{c,s_a} + u_a \\ p(a, s_a) + 2 \\ q(a, s_a, c) + \kappa_{c,s_a} \\ q(a, s_a, s_a) + 2 \end{cases}$

$\displaystyle q(a+1, c, d) = \min\begin{cases} p(a, c) + 3 + \kappa_{c,s_a} \\ p(a, s_a) + 5 \\ q(a, c, d) + 1 + \kappa_{c,s_a} + \kappa_{d,s_a} \\ q(a, c, s_a) + 3 + \kappa_{c,s_a} \\ q(a, s_a, d) + 3 + \kappa_{d,s_a} \\ q(a, s_a, s_a) + 5 \end{cases}$

Then, we have $g(s) = p(N, k)-2$ ~g(s) = p(N, k)-2~ where $N$ ~N~ is an (imaginary) position directly to the right of the last character of $s$ ~s~ and $k$ ~k~ is some (imaginary) letter not contained in $s$ ~s~.

Remark. The condition that the first character of Victor's document is not an e is in fact not necessary due to the following lemma.

Lemma 4. $f(\underbrace{e \dots e}_{n\text{ times}} s) = n+f(s)$ for any $n \ge 0$ ~n \ge 0~.

Comments

There are no comments at the moment.