CF 1048563 - Телефонный справочник
We are working with a simple phone directory that stores associations between a person’s name and their phone number. The system receives a sequence of operations that either update the stored number for a name or ask for the current number associated with a given name.
Rating: -
Tags: -
Solve time: 45s
Verified: yes
Solution
Problem Understanding
We are working with a simple phone directory that stores associations between a person’s name and their phone number. The system receives a sequence of operations that either update the stored number for a name or ask for the current number associated with a given name. The task is to simulate these operations and return the correct result for each query.
Each input operation is either an insertion or update of a mapping from a string key to a numeric value, or a request to retrieve the value for a given key. If a name has not been added before, a query for it should return that it does not exist, typically represented by a special value such as “not found”.
The constraints imply that the number of operations can be large enough that any solution that scans through all previously stored entries for each query would be too slow. A naive list-based approach that searches linearly for every lookup would degrade to quadratic time in the worst case, which would not scale.
The main edge cases appear when the same name is updated multiple times, when queries refer to names that have never been inserted, and when there are many repeated queries for the same name. For example, if the operations are insert “alice 123”, insert “alice 456”, then query “alice”, the correct answer is “456”, since later updates overwrite earlier values. A naive approach that appends entries without replacing old ones would incorrectly return the first value or require searching all occurrences.
Another edge case is querying missing keys such as querying “bob” when no insertion has been performed. The correct output must explicitly reflect absence rather than returning a default numeric value like 0, which could be misleading if 0 is also a valid phone number.
Approaches
A brute-force solution would store all operations in a list of pairs and, for every query, scan backward through the list to find the most recent assignment for that name. This works because the most recent update determines the current value. However, in the worst case where there are n operations and every operation is a query, each query may scan O(n) entries, leading to O(n^2) time overall. With large input sizes, this becomes impractical.
The key observation is that the structure of the problem does not require historical reconstruction. At any point, only the latest value for each name matters. This allows us to compress all prior updates into a single current state. A hash table (dictionary) naturally supports this by mapping each name directly to its latest phone number. Insertions and updates become simple overwrites, and queries become direct lookups.
This reduces the entire problem to maintaining a mutable key-value store with efficient average O(1) operations.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force (scan history per query) | O(n^2) | O(n) | Too slow |
| Hash Map (dictionary) | O(n) average | O(n) | Accepted |
Algorithm Walkthrough
- Initialize an empty hash map to store name to phone number mappings. This structure represents the current state of the phone directory at any moment.
- Read each operation from the input sequentially. Each operation is either an update or a query, and we process them in the order they appear because later operations depend on earlier updates.
- If the operation is an insertion or update, store or overwrite the mapping in the hash map. Overwriting is essential because only the most recent number for a name is valid.
- If the operation is a query, check whether the name exists in the hash map. If it does, output the stored number; otherwise output a sentinel value such as “not found”.
- Continue until all operations are processed, ensuring that every query reflects the state of all updates that occurred before it.
Why it works
At every point in time, the hash map contains exactly one entry per name, corresponding to the latest update seen so far. This forms an invariant: after processing the first k operations, the map represents the correct phone directory state for those operations. Updates maintain the invariant by overwriting outdated values, and queries do not modify the structure, preserving correctness. Since every operation is handled exactly once and no historical information is needed beyond the latest value, the final answers must match the required behavior.
Python Solution
import sys
input = sys.stdin.readline
def solve():
phone = {}
q = int(input().strip())
for _ in range(q):
parts = input().split()
if not parts:
continue
if parts[0] == "add":
name = parts[1]
number = parts[2]
phone[name] = number
elif parts[0] == "find":
name = parts[1]
if name in phone:
print(phone[name])
else:
print("not found")
if __name__ == "__main__":
solve()
The solution maintains a dictionary called phone that stores the latest number for each name. For every add operation, it directly assigns the value, overwriting any previous entry. For every find operation, it performs a constant-time lookup in the dictionary and prints either the stored number or "not found".
The critical implementation detail is the overwrite behavior of Python dictionaries, which naturally matches the requirement that newer updates replace older ones. Another subtle point is handling missing keys explicitly instead of assuming a default value.
Worked Examples
Example 1
Input:
5
add alice 123
add bob 555
find alice
add alice 999
find alice
State evolution:
| Step | Operation | Dictionary state | Output |
|---|---|---|---|
| 1 | add alice 123 | {alice: 123} | - |
| 2 | add bob 555 | {alice: 123, bob: 555} | - |
| 3 | find alice | unchanged | 123 |
| 4 | add alice 999 | {alice: 999, bob: 555} | - |
| 5 | find alice | unchanged | 999 |
This trace shows how later updates overwrite earlier values and how queries always reflect the latest state.
Example 2
Input:
4
find tom
add tom 42
find tom
find jerry
| Step | Operation | Dictionary state | Output |
|---|---|---|---|
| 1 | find tom | {} | not found |
| 2 | add tom 42 | {tom: 42} | - |
| 3 | find tom | {tom: 42} | 42 |
| 4 | find jerry | {tom: 42} | not found |
This demonstrates correct handling of missing keys and confirms that the dictionary does not assume default values for unknown names.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) average | Each insert and lookup in a hash map is O(1) on average, and each operation is processed once |
| Space | O(n) | In the worst case, all names are distinct and stored in the dictionary |
The solution comfortably fits typical constraints for online query processing, where operations can reach up to hundreds of thousands or more, since it avoids any nested scanning.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
from collections import defaultdict
phone = {}
out = []
q = int(sys.stdin.readline().strip())
for _ in range(q):
parts = sys.stdin.readline().split()
if parts[0] == "add":
phone[parts[1]] = parts[2]
else:
name = parts[1]
out.append(phone.get(name, "not found"))
return "\n".join(out)
# basic
assert run("""5
add alice 1
find alice
add alice 2
find alice
find bob
""") == """1
2
not found"""
# overwrite test
assert run("""3
add x 10
add x 20
find x
""") == "20"
# missing keys
assert run("""2
find a
find b
""") == "not found\nnot found"
# multiple keys
assert run("""4
add a 1
add b 2
find b
find a
""") == """2
1"""
| Test input | Expected output | What it validates |
|---|---|---|
| overwrite | 20 | latest update wins |
| missing queries | not found | correct handling of absent keys |
| multiple keys | 2 / 1 | independent storage per name |
Edge Cases
For repeated updates to the same name, the algorithm always replaces the previous value in the dictionary. For example, inserting “alice 1”, then “alice 2” results in a final state of alice → 2, and any query returns 2. The overwrite behavior is direct and does not require any extra logic.
For queries before any insertion, the dictionary is empty, so every lookup fails the membership check. A query like find unknown correctly returns "not found" because the algorithm explicitly checks existence instead of assuming a default numeric value.
For mixed sequences of updates and queries, the invariant that the dictionary represents the state after processing all previous operations ensures correctness at every step.