CF 88B - Keyboard

Rating: 1500
Tags: implementation
Solve time: 1m 13s
Verified: yes

Solution

Problem Understanding

We are given a keyboard laid out in an n by m grid. Each key contains either a lowercase Latin letter or a special "Shift" key represented by S. Vasya wants to type a string using one hand as much as possible, but he can press two keys at once only if the Euclidean distance between their centers does not exceed x. Each key is a square of side 1, so the distance between two keys at positions (i1, j1) and (i2, j2) is calculated as sqrt((i1-i2)^2 + (j1-j2)^2).

The task is to determine the minimum number of times Vasya must use his other hand to type the string. A lowercase letter is typeable if it exists on the keyboard. An uppercase letter is typeable with one hand only if a lowercase version of the letter exists on the keyboard and there is a shift key within distance x from at least one occurrence of that letter. Otherwise, he needs the other hand.

The constraints tell us that the keyboard is relatively small (n, m <= 30), so we can iterate over all keys when necessary. The string length q can be large (q <= 5 * 10^5), so checking typeability per character must be efficient. Edge cases include letters missing entirely from the keyboard or uppercase letters with no reachable shift key, both of which should yield -1.

A careless implementation might, for example, assume that any uppercase letter is typeable if a lowercase key exists, without checking the distance to a shift key. For example, if the keyboard has a but no nearby shift, the uppercase A cannot be typed with one hand.

Approaches

The naive approach is straightforward: for each character in the string, scan the keyboard to check if the character exists, and for uppercase letters, scan all shift keys to check if one is within distance x. For a keyboard of size up to 30*30 = 900 keys and a string length up to 5*10^5, this would require up to 900 * 5*10^5 = 4.5 * 10^8 operations in the worst case. This is too slow for a 1-second time limit.

The key insight is that we can preprocess the keyboard to determine typeability. First, create a set of all lowercase letters on the keyboard. Second, record all positions of shift keys. For each lowercase letter, precompute whether there exists a shift key within distance x for that letter. With this preprocessing, each character in the string can be evaluated in constant time. The preprocessing step is O(n*m*|shift_keys|), which is feasible because n*m <= 900 and |shift_keys| <= 900.

This reduces the per-character check to a simple set lookup and a boolean flag check for uppercase letters. If a character cannot be typed at all, we return -1; otherwise, we count how many times Vasya must use the other hand.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(q * n * m)	O(n*m)	Too slow
Optimal	O(n_m_	shift_keys	+ q)

Algorithm Walkthrough

Read the keyboard dimensions n, m and the maximum distance x.
Parse the keyboard into a grid of characters.
Create a set of all lowercase letters present on the keyboard.
Create a list of positions of all shift keys.
For each lowercase letter key, check if there exists a shift key within Euclidean distance x. Store the result as a boolean flag per letter.
Read the text length q and the string T.
Initialize a counter for the number of times Vasya must use the other hand.
Iterate over each character c in the string. If c is lowercase, check if it exists in the set of keys. If not, print -1 and exit. If c is uppercase, check if its lowercase version exists and if there is a nearby shift key. If the lowercase exists but no nearby shift key exists, increment the counter. If the lowercase does not exist, print -1 and exit.
After processing all characters, print the counter.

The correctness is guaranteed because preprocessing ensures that all distance checks for uppercase letters are done only once per keyboard configuration. Once a character is determined typeable with one hand, every occurrence in the string can be handled in constant time. Any untypeable character immediately results in -1.

Python Solution

import sys
import math
input = sys.stdin.readline

n, m, x = map(int, input().split())
keyboard = [input().strip() for _ in range(n)]

lower_keys = set()
shift_positions = []

for i in range(n):
    for j in range(m):
        if keyboard[i][j] == 'S':
            shift_positions.append((i, j))
        else:
            lower_keys.add(keyboard[i][j])

# Precompute which letters have shift key within distance x
can_upper = {}
for letter in lower_keys:
    can_upper[letter] = False
    for i in range(n):
        for j in range(m):
            if keyboard[i][j] == letter:
                for si, sj in shift_positions:
                    dist = math.hypot(si - i, sj - j)
                    if dist <= x:
                        can_upper[letter] = True
                        break
                if can_upper[letter]:
                    break

q = int(input())
T = input().strip()

other_hand = 0
for c in T:
    if c.islower():
        if c not in lower_keys:
            print(-1)
            sys.exit()
    else:
        lower_c = c.lower()
        if lower_c not in lower_keys:
            print(-1)
            sys.exit()
        if not can_upper.get(lower_c, False):
            other_hand += 1

print(other_hand)

The first block parses the keyboard and collects lowercase keys and shift key positions. The second block precomputes for each lowercase letter whether an uppercase version can be typed with one hand. The loop over the string applies these precomputed results to determine the number of times Vasya must use the other hand. Using math.hypot avoids manual squaring and square roots. Care is taken to break loops early once a shift key within distance x is found, avoiding unnecessary computation.

Worked Examples

Sample 1:

Input:

2 2 1
ab
cd
1
A

Processing: lowercase letters: {'a','b','c','d'}, shift_positions: []. For 'A', lowercase 'a' exists but no shift key, so output is -1.

Sample 2:

Input:

3 3 2
abc
Sde
fgh
2
Te

Lowercase keys: {'a','b','c','d','e','f','g','h'}. Shift positions: [(1,0)]. Uppercase 'T' corresponds to 't', which is missing, output -1. Letter 'e' is lowercase and exists, so one hand is sufficient. The overall output is -1.

This demonstrates that missing letters or unreachable shift keys are correctly detected.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n_m_	shift_keys
Space	O(n*m)	Store keyboard, sets of letters and shift positions

The precomputation step is feasible because n*m <= 900, and q up to 5*10^5 is handled in linear time.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import math
    n, m, x = map(int, input().split())
    keyboard = [input().strip() for _ in range(n)]
    lower_keys = set()
    shift_positions = []
    for i in range(n):
        for j in range(m):
            if keyboard[i][j] == 'S':
                shift_positions.append((i, j))
            else:
                lower_keys.add(keyboard[i][j])
    can_upper = {}
    for letter in lower_keys:
        can_upper[letter] = False
        for i in range(n):
            for j in range(m):
                if keyboard[i][j] == letter:
                    for si, sj in shift_positions:
                        if math.hypot(si - i, sj - j) <= x:
                            can_upper[letter] = True
                            break
                    if can_upper[letter]:
                        break
    q = int(input())
    T = input().strip()
    other_hand = 0
    for c in T:
        if c.islower():
            if c not in lower_keys:
                return "-1"
        else:
            lower_c = c.lower()
            if lower_c not in lower_keys:
                return "-1"
            if not can_upper.get(lower_c, False):
                other_hand += 1
    return str(other_hand)

# Provided samples
assert run("2 2 1\nab\ncd\n1\nA\n") == "-1"
assert run("2 2 1\nab\ncd\n1\na\n") == "0"

# Custom cases
assert run("1