title: "CF 54D - Writing a Song" description: "We are asked to construct a string of length N using only the first K letters of the alphabet, in such a way that a given "name" string P occurs exactly at certain starting positions and nowhere else."name" string P occurs exactly at certain starting positions and nowhere else." date: "2026-05-28T00:00:00+07:00" tags: ["codeforces", "competitive-programming", "brute-force", "dp", "strings"] categories: ["algorithms"] codeforces_contest: 54 codeforces_index: "D" codeforces_contest_name: "Codeforces Beta Round 50" rating: 2100 weight: 54 solve_time_s: 63 verified: true draft: false

CF 54D - Writing a Song

Rating: 2100
Tags: brute force, dp, strings
Solve time: 1m 3s
Verified: yes

Solution

Problem Understanding

We are asked to construct a string of length N using only the first K letters of the alphabet, in such a way that a given "name" string P occurs exactly at certain starting positions and nowhere else. The positions are given as a binary string, where a 1 indicates that P must start there, and a 0 indicates it must not. The positions of P can overlap, which is allowed and even necessary in some cases.

For example, if P = "aba" and the binary string is "101", it indicates that P must start at positions 1 and 3 of the resulting string. A correct output would be "ababa".

The constraints are small but non-trivial: N can be up to 100 and K up to 26. This means that any solution with roughly N^2 operations is acceptable, but brute-force checking of every possible string is not feasible, since the number of potential strings grows exponentially in N.

Non-obvious edge cases include overlapping occurrences of P that could conflict. For instance, if P = "aa" and the positions are "11", the first P starts at position 1 and the second at position 2. A naive approach might just place P blindly at each start, producing "aaa", which works here, but if P = "ab" it is impossible because placing the second occurrence of "ab" would require the first character to be 'b' and 'a' at the same position, which is a conflict.

Another subtle point is that positions with 0 cannot start P, but characters outside of positions of P can be any valid letter from the first K letters. This gives us flexibility in filling the rest of the string.

Approaches

A brute-force solution would generate every string of length N using the first K letters and check if it matches all required occurrences. This is correct in principle, but its complexity is O(K^N), which is astronomically large for N = 100.

The key observation that enables a practical solution is that each position in the final string is constrained only by overlapping occurrences of P. If we iterate over the starting positions in order and attempt to "paint" P onto the string, any conflict (two overlapping letters that differ) immediately makes the solution impossible. Once all mandatory occurrences are placed without conflict, all remaining positions can be filled with any letter from the alphabet.

This reduces the problem to a single pass over the string where we enforce constraints, then a fill-in for unconstrained positions. This is efficient because each character is processed at most twice: once during constraint placement, once during filling.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(K^N)	O(N)	Too slow
Constraint Propagation + Fill	O(N *	P	)

Algorithm Walkthrough

1. Initialize an array S of length N with None values to represent empty positions.
2. Iterate over the positions in the binary string representing where P must start. For each i with a 1, attempt to copy P into S starting at position i. For each character in P, check if S already has a value at that position. If it does, it must match the character from P; otherwise, the solution is impossible.
3. After placing all mandatory occurrences of P, iterate over S again. Wherever there is a None, replace it with any valid letter from the first K letters. For simplicity, choose the first letter 'a'.
4. Convert S to a string and print it.

Why it works: every 1 in the binary mask is enforced, so P occurs exactly at the required positions. Conflicts between overlapping occurrences are detected in step 2, which guarantees correctness. Unspecified positions are free to be filled arbitrarily from the alphabet.

Python Solution

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = input().strip()
mask = input().strip()

S = [None] * N
lenP = len(P)

for i, c in enumerate(mask):
    if c == '1':
        start = i
        for j in range(lenP):
            pos = start + j
            if pos >= N:
                print("No solution")
                sys.exit()
            if S[pos] is not None and S[pos] != P[j]:
                print("No solution")
                sys.exit()
            S[pos] = P[j]

alphabet = [chr(ord('a') + i) for i in range(K)]
for i in range(N):
    if S[i] is None:
        S[i] = alphabet[0]

print("".join(S))

The code follows the algorithm directly. We carefully handle out-of-bounds errors when a 1 would force P to exceed N. Conflicts are checked character by character. The remaining free positions are filled with 'a', the first letter of the allowed alphabet, which satisfies the problem's "any answer is acceptable" condition.

Worked Examples

Sample 1:

Input:

5 2
aba
101

Step	i	Mask[i]	Action	S state
1	0	1	Place 'aba' at 0	['a','b','a',None,None]
2	1	0	Skip	['a','b','a',None,None]
3	2	1	Place 'aba' at 2, overlap check	['a','b','a','b','a']

Fill remaining None → none left. Output: "ababa".

This demonstrates handling of overlapping occurrences correctly.

Custom Input:

4 2
ab
11

Step	i	Mask[i]	Action	S state
1	0	1	Place 'ab' at 0	['a','b',None,None]
2	1	1	Place 'ab' at 1, conflict?	['a','b','b',None]

No conflict, fill remaining None → 'a'. Output: "abba".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N *	P
Space	O(N)	Store string array of length N

With N ≤ 100, this solution runs comfortably in under 2 seconds. Memory usage is trivial.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    N, K = map(int, input().split())
    P = input().strip()
    mask = input().strip()
    S = [None] * N
    lenP = len(P)
    for i, c in enumerate(mask):
        if c == '1':
            start = i
            for j in range(lenP):
                pos = start + j
                if pos >= N:
                    return "No solution"
                if S[pos] is not None and S[pos] != P[j]:
                    return "No solution"
                S[pos] = P[j]
    alphabet = [chr(ord('a') + i) for i in range(K)]
    for i in range(N):
        if S[i] is None:
            S[i] = alphabet[0]
    return "".join(S)

# Provided sample
assert run("5 2\naba\n101\n") == "ababa", "sample 1"

# Custom tests
assert run("4 2\nab\n11\n") == "abba", "overlap allowed"
assert run("3 2\naa\n11\n") == "aaa", "simple overlap"
assert run("5 3\nabc\n1001\n") == "abcaa", "non-overlapping, fill with 'a'"
assert run("2 2\nab\n11\n") == "No solution", "too short to place both occurrences"

Test input	Expected output	What it validates
4 2, ab, 11	abba	overlapping occurrences
3 2, aa, 11	aaa	identical letters, overlap
5 3, abc, 1001	abcaa	free positions filled correctly
2 2, ab, 11	No solution	impossible placement

Edge Cases

If P is longer than the space left from a 1 in the mask, the algorithm immediately detects it and returns "No solution". For overlapping occurrences, the algorithm enforces character equality, which prevents invalid overlaps. Free positions are filled with the first allowed letter, ensuring the string is valid without introducing accidental occurrences of P elsewhere. For example, with N = 5, P = "aa", mask = "101", the algorithm produces "aaaaa", which satisfies