ICPC 2015 - F. Keyboarding
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
Source-first archive entry
This page is built from the copied files in competitive_programming/icpc/2015/F-keyboarding. Edit
competitive_programming/icpc/2015/F-keyboarding/solution.tex to update the written solution and
competitive_programming/icpc/2015/F-keyboarding/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem Statement
Copied statement text kept beside the solution archive for direct reference.
Problem F
Keyboarding
Time limit: 4 seconds
How many keystrokes are necessary to type a text message? You may think that it is equal to the number
of characters in the text, but this is correct only if one keystroke generates one character. With pocket-
size devices, the possibilities for typing text are often limited. Some devices provide only a few buttons,
significantly fewer than the number of letters in the alphabet. For such devices, several strokes may be
needed to type a single character. One mechanism to deal with these limitations is a virtual keyboard
displayed on a screen, with a cursor that can be moved from key to key to select characters. Four
arrow buttons control the movement of the cursor, and when the cursor is positioned over an appropriate
key, pressing the fifth button selects the corresponding character and appends it to the end of the text.
To terminate the text, the user must navigate to and select the Enter key. This provides users with an
arbitrary set of characters and enables them to type text of any length with only five hardware buttons.
In this problem, you are given a virtual keyboard layout and your task is to determine the minimal
number of strokes needed to type a given text, where pressing any of the five hardware buttons constitutes
a stroke. The keys are arranged in a rectangular grid, such that each virtual key occupies one or more
connected unit squares of the grid. The cursor starts in the upper left corner of the keyboard and moves
in the four cardinal directions, in such a way that it always skips to the next unit square in that direction
that belongs to a different key. If there is no such unit square, the cursor does not move.
A B C D E F G
↑
H I J K L M N
← SEL →
O P Q R S T U
↓
V W X Y Z Enter
Figure F.1: Sample Input 1. An example virtual keyboard and hardware buttons.
Figure F.1, illustrating Sample Input 1, shows a possible way to type CONTEST using 30 strokes on an
example virtual keyboard. The red dots represent the virtual keys where the select button was pressed.
Input
The first line of the input contains two integers r and c (1 ≤ r, c ≤ 50), giving the number of rows and
columns of the virtual keyboard grid. The virtual keyboard is specified in the next r lines, each of which
contains c characters. The possible values of these characters are uppercase letters, digits, a dash, and
an asterisk (representing Enter). There is only one key corresponding to any given character. Each key
is made up of one or more grid squares, which will always form a connected region. The last line of
the input contains the text to be typed. This text is a non-empty string of at most 10 000 of the available
characters other than the asterisk.
Output
Display the minimal number of strokes necessary to type the whole text, including the Enter key at the
end. It is guaranteed that the text can be typed.
Sample Input 1 Sample Output 1
4 7 30
ABCDEFG
HIJKLMN
OPQRSTU
VWXYZ**
CONTEST
Sample Input 2 Sample Output 2
5 20 160
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**
--------------------
ACM-ICPC-WORLD-FINALS-2015
Sample Input 3 Sample Output 3
2 19 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ
Sample Input 4 Sample Output 4
6 4 7
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}
\title{ICPC World Finals 2015\\F. Keyboarding}
\author{}
\date{}
\begin{document}
\maketitle
\section*{Problem Summary}
State the problem in your own words. Focus on the mathematical or algorithmic core rather than repeating the full statement.
\section*{Key Observations}
\begin{itemize}[leftmargin=*]
\item Write the structural observations that make the problem tractable.
\item State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
\item If the constraints matter, explain exactly which part of the solution they enable.
\end{itemize}
\section*{Algorithm}
\begin{enumerate}[leftmargin=*]
\item Describe the data structures and the state maintained by the algorithm.
\item Explain the processing order and why it is sufficient.
\item Mention corner cases explicitly if they affect the implementation.
\end{enumerate}
\section*{Correctness Proof}
We prove that the algorithm returns the correct answer.
\paragraph{Lemma 1.}
State the first key claim.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Lemma 2.}
State the next claim if needed.
\paragraph{Proof.}
Provide a concise proof.
\paragraph{Theorem.}
The algorithm outputs the correct answer for every valid input.
\paragraph{Proof.}
Combine the lemmas and finish the argument.
\section*{Complexity Analysis}
State the running time and memory usage in terms of the input size.
\section*{Implementation Notes}
\begin{itemize}[leftmargin=*]
\item Mention any non-obvious implementation detail that is easy to get wrong.
\item Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}