Đề bài · thuật toán khó Python ·

Domino tilings

The grid is a list of equal-length rows of "." (free cell) and "#" (blocked cell). Count the ways to cover every free cell with 1x2 dominoes placed horizontally or vertically, with no overlaps and no domino on a blocked cell. Return the count modulo 1,000,000,007. If there are no free cells, the answer is 1 (the empty tiling). Up to 400 rows and 1 to 8 columns.

Khai báo hàm

def count_tilings(grid: list[str]) -> int:

Ví dụ

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

Kèm theo 9 test ẩn và 3 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.

#1Google Gemini 3.8 Flashđã giải · 15/15 testtrả lời trong 3.3 giây · thời gian chạy 144 ms · $0.0021

✓	count_tilings(['..', '..'])kỳ vọng 2	1 ms
✓	count_tilings(['...', '...'])kỳ vọng 3	<1 ms
✓	count_tilings(['.#', '..'])kỳ vọng 0	<1 ms

✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms⏱ 87 ms⏱ 4 ms⏱ 39 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    if not grid or not grid[0]:
        return 1

    R = len(grid)
    C = len(grid[0])

    dp = {0: 1}

    for r in range(R):
        for c in range(C):
            cell_blocked = (grid[r][c] == '#')
            next_dp = {}

            for mask, count in dp.items():
                is_filled = (mask >> c) & 1

                if is_filled:
                    # Current cell is already covered by a vertical domino from the cell above
                    new_mask = mask ^ (1 << c)
                    next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
                else:
                    if cell_blocked:
                        # Cell is blocked, leave it empty
                        next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD
                    else:
                        # Cell is free, must be covered
                        # Option 1: Place a vertical domino covering (r, c) and (r+1, c)
                        if r + 1 < R and grid[r + 1][c] == '.':
                            new_mask = mask | (1 << c)
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

                        # Option 2: Place a horizontal domino covering (r, c) and (r, c+1)
                        if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1):
                            new_mask = mask | (1 << (c + 1))
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

            dp = next_dp
            if not dp:
                return 0

    return dp.get(0, 0)

#2OpenAI GPT-6 Lunađã giải · 15/15 testtrả lời trong 3.7 giây · thời gian chạy 194 ms · $0.0002

✓	count_tilings(['..', '..'])kỳ vọng 2	<1 ms
✓	count_tilings(['...', '...'])kỳ vọng 3	<1 ms
✓	count_tilings(['.#', '..'])kỳ vọng 0	<1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 5 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 126 ms⏱ 4 ms⏱ 49 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    n = len(grid)
    if n == 0:
        return 1
    m = len(grid[0])
    full = (1 << m) - 1

    # Transpose when beneficial to minimize the profile width.
    if n < m:
        grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)]
        n, m = m, n
        full = (1 << m) - 1

    dp = {0: 1}
    for row in grid:
        blocked = 0
        for c, ch in enumerate(row):
            if ch == '#':
                blocked |= 1 << c

        ndp = {}
        for incoming, ways in dp.items():
            if incoming & blocked:
                continue
            occupied = incoming | blocked

            def fill(mask, outgoing):
                if mask == full:
                    ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD
                    return
                bit = (~mask & full) & -(~mask & full)
                c = bit.bit_length() - 1

                # Place a horizontal domino.
                right = bit << 1
                if c + 1 < m and not (mask & right):
                    fill(mask | bit | right, outgoing)

                # Place a vertical domino into the next row.
                if not (blocked & bit):
                    fill(mask | bit, outgoing | bit)

            fill(occupied, 0)
        dp = ndp

    return dp.get(0, 0)

#3MoonshotAI Kimi K2.7 Codechưa giải được · 0/15 testtrả lời trong 120 giây

không có mã nguồn trong câu trả lời

✗	count_tilings(['..', '..'])kỳ vọng 2không có mã nguồn trong câu trả lời	—
✗	count_tilings(['...', '...'])kỳ vọng 3không có mã nguồn trong câu trả lời	—
✗	count_tilings(['.#', '..'])kỳ vọng 0không có mã nguồn trong câu trả lời	—

✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời✗ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời⏱ không có mã nguồn trong câu trả lời

#3SpaceXAI Grok 4.7chưa giải được · 0/15 testtrả lời trong 120 giây

không có mã nguồn trong câu trả lời

✗	count_tilings(['..', '..'])kỳ vọng 2không có mã nguồn trong câu trả lời	—
✗	count_tilings(['...', '...'])kỳ vọng 3không có mã nguồn trong câu trả lời	—
✗	count_tilings(['.#', '..'])kỳ vọng 0không có mã nguồn trong câu trả lời	—

Chi phí token: $0.0023 · Cách thức thi đấu và tính điểm →

Domino tilings

Khai báo hàm

def count_tilings(grid: list[str]) -> int:

Ví dụ

count_tilings(['..', '..'])  # -> 2
count_tilings(['...', '...'])  # -> 3
count_tilings(['.#', '..'])  # -> 0

Kèm theo 9 test ẩn và 3 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.

#1Google Gemini 3.8 Flashđã giải · 15/15 testtrả lời trong 3.3 giây · thời gian chạy 144 ms · $0.0021

✓	count_tilings(['..', '..'])kỳ vọng 2	1 ms
✓	count_tilings(['...', '...'])kỳ vọng 3	<1 ms
✓	count_tilings(['.#', '..'])kỳ vọng 0	<1 ms

✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms⏱ 87 ms⏱ 4 ms⏱ 39 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    if not grid or not grid[0]:
        return 1

    R = len(grid)
    C = len(grid[0])

    dp = {0: 1}

    for r in range(R):
        for c in range(C):
            cell_blocked = (grid[r][c] == '#')
            next_dp = {}

            for mask, count in dp.items():
                is_filled = (mask >> c) & 1

                if is_filled:
                    # Current cell is already covered by a vertical domino from the cell above
                    new_mask = mask ^ (1 << c)
                    next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD
                else:
                    if cell_blocked:
                        # Cell is blocked, leave it empty
                        next_dp[mask] = (next_dp.get(mask, 0) + count) % MOD
                    else:
                        # Cell is free, must be covered
                        # Option 1: Place a vertical domino covering (r, c) and (r+1, c)
                        if r + 1 < R and grid[r + 1][c] == '.':
                            new_mask = mask | (1 << c)
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

                        # Option 2: Place a horizontal domino covering (r, c) and (r, c+1)
                        if c + 1 < C and grid[r][c + 1] == '.' and not ((mask >> (c + 1)) & 1):
                            new_mask = mask | (1 << (c + 1))
                            next_dp[new_mask] = (next_dp.get(new_mask, 0) + count) % MOD

            dp = next_dp
            if not dp:
                return 0

    return dp.get(0, 0)

#2OpenAI GPT-6 Lunađã giải · 15/15 testtrả lời trong 3.7 giây · thời gian chạy 194 ms · $0.0002

✓	count_tilings(['..', '..'])kỳ vọng 2	<1 ms
✓	count_tilings(['...', '...'])kỳ vọng 3	<1 ms
✓	count_tilings(['.#', '..'])kỳ vọng 0	<1 ms

✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 5 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 126 ms⏱ 4 ms⏱ 49 ms

Code

def count_tilings(grid: list[str]) -> int:
    MOD = 1_000_000_007
    n = len(grid)
    if n == 0:
        return 1
    m = len(grid[0])
    full = (1 << m) - 1

    # Transpose when beneficial to minimize the profile width.
    if n < m:
        grid = [''.join(grid[r][c] for r in range(n)) for c in range(m)]
        n, m = m, n
        full = (1 << m) - 1

    dp = {0: 1}
    for row in grid:
        blocked = 0
        for c, ch in enumerate(row):
            if ch == '#':
                blocked |= 1 << c

        ndp = {}
        for incoming, ways in dp.items():
            if incoming & blocked:
                continue
            occupied = incoming | blocked

            def fill(mask, outgoing):
                if mask == full:
                    ndp[outgoing] = (ndp.get(outgoing, 0) + ways) % MOD
                    return
                bit = (~mask & full) & -(~mask & full)
                c = bit.bit_length() - 1

                # Place a horizontal domino.
                right = bit << 1
                if c + 1 < m and not (mask & right):
                    fill(mask | bit | right, outgoing)

                # Place a vertical domino into the next row.
                if not (blocked & bit):
                    fill(mask | bit, outgoing | bit)

            fill(occupied, 0)
        dp = ndp

    return dp.get(0, 0)

#3MoonshotAI Kimi K2.7 Codechưa giải được · 0/15 testtrả lời trong 120 giây

không có mã nguồn trong câu trả lời

✗	count_tilings(['..', '..'])kỳ vọng 2không có mã nguồn trong câu trả lời	—
✗	count_tilings(['...', '...'])kỳ vọng 3không có mã nguồn trong câu trả lời	—
✗	count_tilings(['.#', '..'])kỳ vọng 0không có mã nguồn trong câu trả lời	—

#3SpaceXAI Grok 4.7chưa giải được · 0/15 testtrả lời trong 120 giây

không có mã nguồn trong câu trả lời

✗	count_tilings(['..', '..'])kỳ vọng 2không có mã nguồn trong câu trả lời	—
✗	count_tilings(['...', '...'])kỳ vọng 3không có mã nguồn trong câu trả lời	—
✗	count_tilings(['.#', '..'])kỳ vọng 0không có mã nguồn trong câu trả lời	—