CF 106026A - 备用账号

Rating: -
Tags: -
Solve time: 52s
Verified: yes

Solution

Problem Understanding

We are given a list of usernames, and we want to count how many unordered pairs of usernames can be considered “account variants” of each other.

Two usernames are considered compatible if they have the same length and, position by position, every character can be treated as the same under a fixed equivalence rule. The rule defines that all letters are case-insensitive, and in addition a few special substitutions are allowed: the characters a, A, and @ are interchangeable, and the characters o, O, and 0 are interchangeable. Everything else behaves normally under case-insensitive matching for letters, while digits remain themselves except for the special case of 0.

So the core task is to decide, among all usernames, how many pairs become identical after converting every string into its canonical normalized form.

The input size pushes us away from any quadratic comparison between usernames. With up to 100,000 names and a total length of 500,000 characters, even comparing every pair would require around 10^10 character checks in the worst case, which is far beyond a 2-second limit. This immediately suggests that each username must be processed independently in linear time, and then aggregated using a frequency structure.

A subtle edge case appears when different raw strings become identical after normalization. For example, c@t and cat should be treated as identical, so they contribute one valid pair, even though the raw strings differ. Another pitfall is forgetting the special mapping of 0 to o and @ to a, which breaks equivalence if only case folding is applied.

Approaches

The straightforward approach is to compare every pair of usernames and check whether they are equivalent character by character under the given mapping. For each pair, we would scan the strings, normalize each position on the fly, and compare. This works logically because it directly encodes the definition of similarity.

However, if there are n usernames, this leads to roughly n²/2 comparisons. Each comparison may take O(L) time where L is average string length, giving an overall worst case of O(n²L), which is far too slow when n is 10^5.

The key observation is that equivalence defines a partition over all possible strings: every username belongs to exactly one normalized form, and two usernames are valid pairs if and only if they share that form. This reduces the problem from pairwise comparison to counting frequencies. Once every string is converted into its canonical representation, we only need to count how many times each canonical string appears, and then sum combinations inside each frequency group.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Pair Checking	O(n² · L)	O(1)	Too slow
Normalize + Frequency Count	O(total length)	O(n)	Accepted

Algorithm Walkthrough

For each username, construct its normalized version character by character. This step is necessary because equivalence depends only on position-wise transformation, and normalization makes equivalent strings identical.
For each character in a username, convert it into a canonical symbol. Letters are mapped to lowercase. The character @ is mapped to a, and 0 is mapped to o. All other characters remain unchanged after lowercase conversion if applicable. This guarantees that any two equivalent characters become identical after transformation.
Store each normalized username in a hash map that counts how many times it appears. This groups all equivalent usernames together without explicit pairwise comparison.
After processing all usernames, iterate through the frequency map. For each group of size f, add f · (f − 1) / 2 to the answer. This counts all unordered pairs inside the group.
Output the final accumulated sum.

Why it works

The normalization function defines an equivalence relation over characters, and therefore extends to strings position-wise. Two strings are equivalent under the problem definition if and only if their normalized forms are identical. This means every valid pair must lie inside a single frequency bucket of identical normalized strings, and every pair inside such a bucket is valid. The counting formula f · (f − 1) / 2 exactly enumerates all unordered pairs inside each bucket, ensuring completeness without double counting.

Python Solution

import sys
input = sys.stdin.readline

def normalize(s: str) -> str:
    res = []
    for ch in s.strip():
        if ch.isalpha():
            res.append(ch.lower())
        elif ch == '@':
            res.append('a')
        elif ch == '0':
            res.append('o')
        else:
            res.append(ch)
    return ''.join(res)

def solve():
    n = int(input())
    freq = {}

    for _ in range(n):
        s = input().strip()
        ns = normalize(s)
        freq[ns] = freq.get(ns, 0) + 1

    ans = 0
    for v in freq.values():
        ans += v * (v - 1) // 2

    print(ans)

if __name__ == "__main__":
    solve()

The core of the implementation is the normalization function. It enforces all equivalences directly so that the main logic never has to reason about special cases again. This separation prevents subtle mistakes like mixing case folding with digit substitutions in inconsistent ways.

The dictionary accumulates frequencies of fully normalized usernames. Since Python strings are hashable, this step is efficient and fits comfortably within the memory limit.

Finally, the combination formula is applied to each group independently, which avoids double counting and ensures unordered pairs are counted exactly once.

Worked Examples

Consider the input:

3
coder
c0der
cOdeR

After normalization:

coder -> coder
c0der -> coder
cOdeR -> coder

Username	Normalized
coder	coder
c0der	coder
cOdeR	coder

All three collapse into one group of size 3, contributing 3 · 2 / 2 = 3 pairs.

This shows how multiple syntactically different usernames become identical after applying both case folding and digit-symbol equivalence.

Now consider:

4
cat
atc
c@t
at

Normalization gives:

cat -> cat
atc -> atc
c@t -> cat
at -> at

Username	Normalized
cat	cat
atc	atc
c@t	cat
at	at

We have groups of sizes 2 (cat), 1 (atc), and 1 (at). Only the cat group contributes a pair, giving exactly 1 valid pair.

This demonstrates that grouping is purely local per normalized string and no cross-group pairing is possible.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(total length of all strings)	Each character is processed once during normalization and dictionary insertion
Space	O(n)	Each username contributes one normalized key in the hash map

The total length constraint of 5 × 10^5 ensures that linear processing over characters is sufficient. The hash map only stores at most n keys, which fits easily within memory limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import defaultdict

    def normalize(s: str) -> str:
        res = []
        for ch in s.strip():
            if ch.isalpha():
                res.append(ch.lower())
            elif ch == '@':
                res.append('a')
            elif ch == '0':
                res.append('o')
            else:
                res.append(ch)
        return ''.join(res)

    n = int(sys.stdin.readline())
    freq = {}

    for _ in range(n):
        s = sys.stdin.readline().strip()
        ns = normalize(s)
        freq[ns] = freq.get(ns, 0) + 1

    ans = 0
    for v in freq.values():
        ans += v * (v - 1) // 2

    return str(ans)

# provided samples
assert run("3\ncoder\nc0der\ncOdeR\n") == "3"
assert run("4\ncat\natc\nc@t\nat\n") == "1"

# custom cases
assert run("2\na@\naa\n") == "1"
assert run("3\no0O\noo\no\n") == "3"
assert run("1\nabc\n") == "0"
assert run("5\nA@a\naAa\na@\n0o\nOO\n") == "10"

Test input	Expected output	What it validates
`a@, aa`	1	@ and a equivalence collapsing
mixed o/O/0 strings	3	digit-letter equivalence consistency
single string	0	minimum edge case
multiple heavy collisions	10	large grouping and combinatorics

Edge Cases

One important case is when usernames differ only by special characters that map into letters. For example:

Input:

2
a@
aa

Normalization turns both into aa, so they form a single group of size 2. The algorithm correctly counts one pair via 2 · 1 / 2.

Another case involves the 0 to o mapping combined with uppercase letters:

Input:

3
o0O
oo
o

After normalization:

o0O -> ooo
oo  -> oo
o   -> o

Here we get groups of sizes 1, 1, and 1, so no pairs are formed. This confirms that normalization is strict and only identical full-length matches contribute.

A final edge case is when all usernames are identical after normalization but different in raw form. The frequency-based method correctly aggregates them into a single group, ensuring all valid combinations are counted without missing cross-variant pairs.