CF 31B - Sysadmin Bob

We are given a single string that represents multiple email addresses concatenated together with no separators. Each email address has the form A@B, where A and B are non-empty strings consisting of lowercase Latin letters.

codeforcescompetitive-programminggreedyimplementationstrings

CF 31B - Sysadmin Bob

Rating: 1500
Tags: greedy, implementation, strings
Solve time: 1m 11s
Verified: yes

Solution

Problem Understanding

We are given a single string that represents multiple email addresses concatenated together with no separators. Each email address has the form A@B, where A and B are non-empty strings consisting of lowercase Latin letters. Our task is to split the string into a sequence of valid email addresses. If there is no way to do this, we must output No solution. If multiple valid splits exist, any one is acceptable.

The key difficulty is that the original string could have had repeated addresses or addresses of arbitrary lengths, and there is no other clue about the original boundaries. We cannot blindly split on the first @ because subsequent @ characters may belong to the next email. The string length is at most 200 characters, which is small, allowing solutions that are roughly quadratic in complexity. This rules out approaches that would require checking an exponential number of splits.

A subtle edge case occurs when the input contains exactly one @, or multiple @ symbols appear consecutively. For example, a@a@a could split as a@a,a@a or as a@aa@a. A naive greedy approach might incorrectly assign too few characters to the local part A or too many to the domain part B, producing an invalid address or missing a valid split. Similarly, if the string begins or ends with @, it is immediately impossible because both A and B must be non-empty.

Approaches

The brute-force approach is to try every possible way to split the string at positions that preserve the rule that every address has one @ separating non-empty A and B. For a string of length n, there are 2^(n-1) possible splits if we consider splitting between every pair of characters. This quickly becomes infeasible even for n=20 because the number of combinations grows exponentially.

The key observation that simplifies the problem is that each email address must contain exactly one @, and it cannot appear at the very start or end of the address. This structure allows a greedy construction from left to right. Once we identify the first @ after the current start of the string, we can treat everything up to that @ as the local part. The domain part must consume at least one character, and if there are additional @ symbols later, the next address begins at the next character after the first character of the current domain. This ensures we always produce valid addresses while consuming the string efficiently.

Effectively, the algorithm works by always splitting immediately after the first @ we encounter in the unprocessed suffix, and leaving at least one character for the domain. This approach is linear in the number of @ symbols and safe due to the small input size.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^n) O(n) Too slow
Greedy Split at @ O(n) O(n) Accepted

Algorithm Walkthrough

  1. Start at the beginning of the string and look for the first @ symbol. If there is none, return No solution immediately. The string must contain at least one @ to form a valid email.
  2. Treat all characters before this @ as the local part A. If this part is empty, the solution is impossible.
  3. Move one character past @ to start the domain part B. The domain must also be non-empty. If the next @ occurs before the last character of the current remaining string, then assign all characters up to that @ as the current domain. Otherwise, assign all remaining characters as the domain of the last address.
  4. Append the extracted address A@B to the answer list.
  5. Repeat the process from the next character after the end of the current domain until the end of the string.
  6. If at any point the domain or local part is empty, stop and output No solution. Otherwise, join the collected addresses with commas and output the result.

Why it works: Each split guarantees that the local part is non-empty and the domain part consumes at least one character. By greedily assigning the first possible @ and leaving the remainder for subsequent addresses, we never produce overlapping or invalid addresses, and we eventually consume the entire string.

Python Solution

import sys
input = sys.stdin.readline

s = input().strip()
n = len(s)

if s.count('@') == 0:
    print("No solution")
    sys.exit()

res = []
i = 0
while i < n:
    # find the next '@'
    at_pos = s.find('@', i)
    if at_pos == -1 or at_pos == i or at_pos == n - 1:
        print("No solution")
        sys.exit()
    
    # local part is from i to at_pos - 1
    local = s[i:at_pos]
    
    # domain must take at least one character
    j = at_pos + 1
    # the next '@' determines the end of the current domain
    next_at = s.find('@', j)
    if next_at == -1:
        # last address takes all remaining characters
        domain = s[j:]
        i = n
    else:
        # leave at least one char for the next local part
        domain = s[j:next_at]
        if not domain:
            print("No solution")
            sys.exit()
        i = next_at - 1
    res.append(f"{local}@{domain}")

print(",".join(res))

The code reads the string and initializes an index i. It finds the next @ and slices out the local and domain parts carefully. If a domain is empty or we encounter an invalid @ placement, we exit with No solution. Otherwise, we join the addresses with commas. The trickiest part is leaving at least one character for the next address while splitting domains.

Worked Examples

Example 1

Input: a@aa@a

Step i at_pos local domain next i res
1 0 1 a a 2 ['a@a']
2 2 4 a a 5 ['a@a', 'a@a']

Output: a@a,a@a. The first address uses the first @, the remaining string aa@a splits into a@a. This confirms that we consume all characters while leaving each part non-empty.

Example 2

Input: abc@xyz

Step i at_pos local domain next i res
1 0 3 abc xyz 7 ['abc@xyz']

Output: abc@xyz. Only one email is present, split correctly.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is visited at most twice: once when searching for @ and once when slicing the domain.
Space O(n) We store the resulting addresses in a list.

Since n <= 200, the solution runs comfortably within the time and memory limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    exec(open('solution.py').read(), globals())
    return sys.stdout.getvalue().strip()

# provided sample
assert run("a@aa@a\n") == "a@a,a@a"

# custom cases
assert run("abc@xyz\n") == "abc@xyz"
assert run("@abc\n") == "No solution"
assert run("abc@\n") == "No solution"
assert run("a@b@c@d\n") == "a@b,c@d"
assert run("x@y@z\n") == "x@y,z"  # one possible split
Test input Expected output What it validates
abc@xyz abc@xyz single email
@abc No solution empty local part
abc@ No solution empty domain part
a@b@c@d a@b,c@d multiple emails, greedy splitting
x@y@z x@y,z alternative split with minimum domain length

Edge Cases

The edge case where the string starts with @ is handled because at_pos == i triggers No solution. For abc@, the domain is empty, so the algorithm exits correctly. In strings with multiple @ such as a@b@c@d, the greedy approach correctly assigns at least one character to each domain and moves the pointer forward, producing valid splits like a@b,c@d.

This confirms that the algorithm systematically respects the invariants of non-empty local and domain parts, and never leaves any character unprocessed.