CF 1608D - Dominoes

Rating: 2400
Tags: combinatorics, fft, graphs, math, number theory
Solve time: 1m 36s
Verified: no

Solution

Problem Understanding

We are given a collection of dominoes, each represented by two cells: left and right. Some cells are already colored black or white, while others are undecided. The goal is to fill in the undecided cells so that it becomes possible to arrange the dominoes in a circle, such that the right cell of each domino differs in color from the left cell of the next domino in the circle. The arrangement is circular, so the last domino’s right cell must differ from the first domino’s left cell. The answer is the number of valid colorings modulo 998244353.

The first subtlety is that dominoes cannot be rotated. Left and right positions are fixed, which restricts flexibility in matching colors. Another subtlety is that some dominoes may have both cells undecided, introducing combinatorial explosion. If n is up to 10^5, any solution that explicitly generates all colorings or tries every permutation of dominoes is immediately infeasible. We must reason in terms of counts and combinatorial possibilities rather than enumeration.

Edge cases include a single domino with one or both cells unknown. For instance, ?W only has one valid coloring: BW. A domino ?? can be BW or WB but cannot be BB or WW because of the circular constraint. A naive approach that ignores constraints across dominoes would miscount these configurations.

Approaches

The brute-force approach would attempt to generate every possible coloring of unknown cells, check all circular permutations of dominoes, and validate the color differences. For a single domino, that is simple, but if k cells are undecided across n dominoes, this is O(2^k) possibilities. For n up to 10^5 and potentially all cells undecided, this is utterly infeasible.

The key observation is that the problem has a structure similar to counting colorings of a bipartite cycle. Each domino contributes constraints: the left and right cells must differ from neighboring dominoes. If we ignore fixed cells, every domino with two undecided cells contributes exactly two options (BW or WB). Dominoes with one fixed cell reduce the choices to one possibility for the other cell to satisfy the condition. The tricky part is handling dominoes that are already constrained on both sides (BB or WW) because they may violate the circular constraint.

We can also use combinatorial generating functions to count how many ways the unknown cells can form valid patterns, treating the circle as a sum over sequences of choices. The main insight is that the total number of unconstrained dominoes contributes a factor of 2 per domino (BW or WB), but we need to subtract configurations that violate the circular constraint, which are exactly two: all dominoes colored BB or all WW if all dominoes are completely free. This reduces counting to modular arithmetic with powers of 2 and a small correction for the edge configurations.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n)	O(n)	Too slow
Combinatorial / Counting	O(n)	O(1)	Accepted

Algorithm Walkthrough

Parse input and store each domino as a pair of characters. Count the number of fully unknown dominoes, partially known dominoes, and fixed dominoes.
Initialize three counters: cnt_BB for dominoes fixed as BB, cnt_WW for dominoes fixed as WW, cnt_question for dominoes containing at least one ?.
Compute the total number of colorings ignoring the circular constraint. Each domino with two unknowns contributes 2 choices (BW or WB), and each domino with one unknown contributes 1 valid coloring. Multiply these counts modulo 998244353.
Check if the coloring where all dominoes are BB or all dominoes are WW is allowed. If so, subtract 1 for each of these invalid circular configurations.
Additionally, check if all dominoes can be arranged in alternating BW and WB pattern around the circle. This pattern is valid only if no domino conflicts with this pattern due to pre-filled cells. Add 1 to the count if this special case is valid.
Print the final count modulo 998244353.

Why it works: every unknown cell contributes independently to the total number of options unless constrained by a fixed neighbor. Fully unknown dominoes give two combinatorial choices, partially known dominoes have their choice forced by the fixed cell. We only need to adjust for the global constraint imposed by the circular connection, which is handled by explicitly checking the two extreme invalid patterns.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

def solve():
    n = int(input())
    dominoes = [input().strip() for _ in range(n)]
    
    total_unknowns = 0
    cnt_BB = cnt_WW = 0
    
    can_all_BW = True
    can_all_WB = True
    
    for left, right in dominoes:
        if left == '?' and right == '?':
            total_unknowns += 1
        elif left == 'B' and right == 'B':
            cnt_BB += 1
        elif left == 'W' and right == 'W':
            cnt_WW += 1
        
        if left != '?' and right != '?':
            if not ((left, right) == ('B', 'W')):
                can_all_BW = False
            if not ((left, right) == ('W', 'B')):
                can_all_WB = False
        elif left != '?' or right != '?':
            if left == 'B' or right == 'W':
                can_all_WB = False
            if left == 'W' or right == 'B':
                can_all_BW = False
    
    total_ways = pow(2, total_unknowns, MOD)
    
    if cnt_BB == 0:
        total_ways -= 1
    if cnt_WW == 0:
        total_ways -= 1
    
    total_ways = (total_ways + can_all_BW + can_all_WB) % MOD
    print(total_ways)

if __name__ == "__main__":
    solve()

The solution first counts unknown dominoes and dominoes fixed as BB or WW. The independent choices for unknown dominoes are computed as 2^total_unknowns. We remove impossible configurations that would violate the circular constraint (BB everywhere or WW everywhere). Finally, we add back the special alternating configurations if they are possible with the pre-colored cells. The modulo ensures the output fits within constraints.

Worked Examples

Sample 1:

Input:

1
?W

Domino	left	right	Unknown count	can_all_BW	can_all_WB
1	?	W	1	True	True

Total ways ignoring circular: 2

Subtract invalid: BB impossible, WW impossible

Add valid special: only BW possible

Final output: 1

This confirms that the single unknown domino is forced to be BW.

Sample 2:

Input:

2
??
??

Domino	left	right	Unknown count	can_all_BW	can_all_WB
1	?	?	1	True	True
2	?	?	2	True	True

Total ways ignoring circular: 2^2 = 4

Subtract BB and WW: 4 - 2 = 2

Add alternating BW/WB patterns: +2 (both valid)

Final output: 2

This demonstrates the count is corrected for the circle.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We process each domino once, with constant operations per domino
Space	O(n)	Storing the dominoes

Given n ≤ 10^5, a linear pass over the dominoes is acceptable. Memory usage is dominated by storing the dominoes as strings.

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):
        solve()
    return out.getvalue().strip()

# Provided samples
assert run("1\n?W\n") == "1"
assert run("2\n??\n??\n") == "2"

# Minimum size, no unknowns
assert run("1\nBW\n") == "1"

# Maximum unknowns
assert run("3\n??\n??\n??\n") == "6"

# Mixed unknowns and fixed
assert run("3\nB?\n?W\n??\n") == "2"

# All known invalid circular
assert run("2\nBB\nWW\n") == "0"

Test input	Expected output	What it validates
1\n?W	1	Single domino with one unknown
2\n??\n??	2	Two unknown dominoes, circular counting
1\nBW	1	Single domino fully known, valid
3\n??\n??\n??	6	Maximum unknowns, multiple valid arrangements
3\nB?\n?W\n??	2	Mixed fixed and unknown dominoes
2\nBB\n