CF 292C - Beautiful IP Addresses

We are asked to generate "beautiful" IP addresses under a very specific definition. Each IP address consists of four decimal numbers between 0 and 255, written without leading zeroes, separated by periods.

codeforcescompetitive-programmingbrute-force

CF 292C - Beautiful IP Addresses

Rating: 2000
Tags: brute force
Solve time: 1m 33s
Verified: yes

Solution

Problem Understanding

We are asked to generate "beautiful" IP addresses under a very specific definition. Each IP address consists of four decimal numbers between 0 and 255, written without leading zeroes, separated by periods. For the purpose of this problem, we transform an IP address into a single string by concatenating these four numbers and check whether this string is a palindrome. Additionally, the digits used in the IP must come exclusively from a given set, and each digit in the set must appear at least once. The output is all IP addresses satisfying these constraints.

The first input line gives the number of digits in the set, and the second line lists the digits themselves. Since n is at most 10, the set can contain all decimal digits. This is small enough that we can consider generating candidates by combinatorial exploration without immediately hitting performance limits. However, each of the four parts of the IP can range from 0 to 255, so a naïve approach that checks every 256⁴ ≈ 4.3 billion addresses is infeasible in 2 seconds. We need a strategy to prune the search space drastically.

Edge cases include the smallest and largest allowed digits. If the set has only one digit, the resulting IP must consist entirely of repetitions of that digit. We must be careful with leading zeros: parts like 01 or 001 are invalid, so any combinatorial generation must exclude them.

Another subtlety is that the concatenation of the four numbers may result in strings of different lengths. For example, 0.0.0.0 becomes "0000" and 12.34.5.6 becomes "123456". We cannot assume all strings have the same length, so palindrome checking must work with variable-length strings.

Approaches

The brute-force approach would attempt to generate all four-part numbers from 0 to 255, convert them to strings, concatenate them, and check both the palindrome property and whether the string uses only the given digits with no omissions. While this is correct, it requires 256⁴ iterations, which is far too large.

The key insight for a feasible solution is to treat the problem as generating palindromes directly rather than generating IPs and testing them. Any palindrome of length L has the property that the first half determines the second half. The total length of a concatenated IP string cannot exceed 12 characters because the largest IP part 255 is three digits and there are four parts. Therefore, the concatenated string is at most 12 digits long.

We can systematically generate palindromes up to length 12 using only the allowed digits. Once we have a candidate palindrome string, we attempt all ways of splitting it into four valid IP parts, each in 0..255 and without leading zeros. This drastically reduces the number of strings we need to examine, making the problem tractable.

Approach Time Complexity Space Complexity Verdict
Brute Force O(256⁴) O(1) Too slow
Palindrome Generation + Split Check O(allowed_digits^6) O(number of valid IPs) Accepted

Algorithm Walkthrough

  1. Construct all palindromes using the given set of digits. We only need to generate palindromes with lengths from 4 to 12 because the shortest valid IP string is "0.0.0.0" → "0000". To generate palindromes, choose the first half of the string freely and mirror it to form the second half. Include both even and odd-length palindromes.
  2. For each generated palindrome string, check all possible splits into four numbers. Each number may have 1 to 3 digits. Generate splits such that the sum of their lengths equals the length of the palindrome string.
  3. For each split, verify that each part is a valid 8-bit integer (0-255) and has no leading zeros. Discard splits that violate these constraints.
  4. Ensure that the concatenated digits used in this split cover all digits from the input set. Any missing digit invalidates the candidate.
  5. Collect all valid IP addresses as strings with periods between the four numbers. Keep track of the count.
  6. Output the total count and then each IP address.

The invariant here is that every candidate generated is guaranteed to be a palindrome and composed solely of allowed digits. The validity check on each split guarantees that the resulting four numbers form a legitimate IP address. By combining these two constraints, no invalid IP or non-palindromic string can appear in the output.

Python Solution

import sys
input = sys.stdin.readline

from itertools import product

def generate_palindromes(digits, max_len=12):
    digits = list(map(str, digits))
    results = []
    for length in range(4, max_len + 1):
        half = (length + 1) // 2
        for first_half in product(digits, repeat=half):
            first_half_str = ''.join(first_half)
            if length % 2 == 0:
                palindrome = first_half_str + first_half_str[::-1]
            else:
                palindrome = first_half_str + first_half_str[:-1][::-1]
            results.append(palindrome)
    return results

def valid_ip_parts(s):
    parts = []
    n = len(s)
    for i in range(1, 4):
        for j in range(i+1, i+4):
            for k in range(j+1, j+4):
                if k < n:
                    a, b, c, d = s[:i], s[i:j], s[j:k], s[k:]
                    if all(0 <= int(x) <= 255 and (x == "0" or x[0] != "0") for x in [a, b, c, d]):
                        parts.append(f"{a}.{b}.{c}.{d}")
    return parts

def main():
    n = int(input())
    digits = list(map(int, input().split()))
    digit_set = set(map(str, digits))
    
    beautiful_ips = []
    palindromes = generate_palindromes(digits)
    
    for p in palindromes:
        if set(p) != digit_set and not set(p).issuperset(digit_set):
            continue
        ips = valid_ip_parts(p)
        for ip in ips:
            ip_digits = set(ip.replace(".", ""))
            if ip_digits == digit_set:
                beautiful_ips.append(ip)
    
    print(len(beautiful_ips))
    print("\n".join(beautiful_ips))

if __name__ == "__main__":
    main()

The code first generates all palindromes of length 4 to 12 using the allowed digits. The valid_ip_parts function considers all ways to split a string into four parts with 1 to 3 digits each, verifying that each part is within 0-255 and has no leading zeros. When checking the palindrome string, we discard any string that does not include all digits from the input set. Finally, we collect and print all valid IP addresses.

Subtle points include handling strings like "0" correctly to avoid leading-zero errors and ensuring that the palindrome generation covers both even and odd lengths properly. Another trap is checking for digit coverage: using issuperset avoids rejecting palindromes that include extra digits outside the input set, which the problem forbids.

Worked Examples

Example 1

Input:

6
0 1 2 9 8 7

Steps:

Step Variable Value
Generate palindromes first_half='78' palindrome='787'
Split check 7.8.7. invalid
Split check 78.1.90. invalid
Valid split 78.190.209.187 valid

The trace confirms that the algorithm correctly generates candidate palindromes, attempts valid splits, and keeps only the ones that satisfy all constraints.

Example 2

Input:

2
1 0

Algorithm would generate palindromes like "1001", "110011". Splitting "1001" yields 1.0.0.1, which is valid. "110011" can yield 11.0.0.11, which is also valid. The algorithm correctly filters splits and ensures digit coverage.

Complexity Analysis

Measure Complexity Explanation
Time O(allowed_digits^6) Generating palindromes uses up to half the length in exponent. For length ≤12 and n≤10, this is tractable. Split checking has constant work per palindrome.
Space O(number of valid IPs) Store the output list. Palindrome generation uses negligible additional memory compared to output.

Given n ≤ 10 and string length ≤12, even the exponent 6 is acceptable. The number of palindromes remains small, and split checking is very fast.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        main()
    return out.getvalue().strip()

# Provided sample
assert run("6\n0 1 2 9 8 7\n") == "6\n78.190.209.187\n79.180.208.197\n87.190.209.178\n89.170.207.198\n97.180.208.179\n98