Vertical Reading of a Memoir — Editorial

Problem Summary

We are given an \(H \times W\) grid of lowercase letters as \(H\) strings \(S_1, \ldots, S_H\). We must read the characters in the \(K\)-th column from top to bottom, i.e., output the length-\(H\) string formed by concatenating the \(K\)-th character (1-indexed) of every \(S_i\).

Algorithm

Since strings are indexed from 0 in most programming languages, the \(K\)-th character of \(S_i\) corresponds to S_i[K-1].

1. Read \(H, W, K\).
2. For \(i = 1, \ldots, H\), read \(S_i\) and append S_i[K-1] to the answer string.
3. Output the concatenated string.

Because each row can be processed as soon as it is read, there is no need to store the entire grid.

Correctness

By definition, the secret message is the string obtained by reading the characters in the \(K\)-th column from top to bottom. Since the \(j\)-th character of \(S_i\) is the character in row \(i\), column \(j\), the character to read on row \(i\) is the \(K\)-th character of \(S_i\), namely S_i[K-1]. The algorithm concatenates exactly these characters in order \(i = 1, \ldots, H\), so the output is exactly the required length-\(H\) string. The constraints \(1 \le K \le W\) and “each \(S_i\) has length \(W\)” guarantee that S_i[K-1] always exists, so no out-of-range access occurs. There are no ties or ambiguities in the problem, so no tie-breaking is needed.

Complexity

• Time: \(O(HW)\), including reading the input.
• Space: \(O(H + W)\) for C++ and \(O(HW)\) for Python, including stored input and output arrays or strings.