← All solutions

Shortest judge solution: 1801 bytes. Shortest team solution (during contest): 1285 bytes.

This problem was one of the easiest (though sufficiently many of the judges goofed up in strange ways while solving this problem that we erronously thought it was harder than it was)

Consider the following directed graph G = (V, E). The nodes V are all triples (i, j, k), where (i, j) is a position on the virtual keyboard 1 ≤ i ≤ r, 1 ≤ j ≤ c, and k is a position in the text 1 ≤ k ≤ n + 1 (where n is the length of the text, in which we include the final ‘*’). The edges from a node (i, j, k) are as follows:

1. For each of the four direction buttons, there is an edge to (i₀, j₀, k) where (i₀, j₀) is the position on the virtual keyboard reached from (i, j) by pressing that direction button.
2. If the character at position (i, j) on the keyboard equals the k’th character in the text, there is an edge to (i, j, k + 1).

The number of keys required is now the minimum distance from (1, 1, 1) to any node of the form (i, j, n + 1). This can be computed with BFS – the number of nodes in the graph is |V| = r · c · n ≤ 50 · 50 · 10 000 = 25 000 000, and the number of edges is at most 5|V|, so this is feasible.