CF 106500D - Combination Lock

The game does not actually depend on the exact digits written on the two locks. Charlie only records whether each pair of corresponding wheels is equal or different.

codeforcescompetitive-programming

CF 106500D - Combination Lock

Rating: -
Tags: -
Solve time: 44s
Verified: yes

Solution

Problem Understanding

The game does not actually depend on the exact digits written on the two locks. Charlie only records whether each pair of corresponding wheels is equal or different. We can represent a position by a string of length N containing two possible states for every wheel: equal or unequal.

Changing one digit on either lock affects exactly one position in this pattern. If two digits were equal, changing one of them makes them different. If they were different, we can choose the new digit to make them equal. Since there are ten possible digits, both transitions are always possible at the pattern level. A move is simply flipping one bit of the pattern.

Some patterns are forbidden from ever appearing, and a pattern that has already appeared cannot be visited again. Alice starts from the initial difference pattern. The player who cannot move loses.

The constraints are designed around the number of patterns, not the number of possible lock configurations. N is at most 10, so there are at most 2^10 = 1024 difference patterns. This rules out exponential search over game histories, because the number of possible visited sets is astronomically larger than the number of vertices. However, it allows graph algorithms on the state graph itself. The forbidden list can contain up to 1000 patterns, which is close to the entire graph size, so the solution must handle arbitrary removed vertices.

A tempting mistake is to treat the game as a simple shortest path or reachability problem. The order of moves matters because visiting a pattern removes it permanently. For example, with one wheel and no forbidden states, the patterns form a cycle of two vertices:

N = 1
Alice: 0
Bob:   0

The correct result is Bob, because Alice moves to the only other state and Bob returns to the start only if it were allowed, but it is already visited. Bob has no move after Alice's turn. A naive reachability approach would not capture the visited rule.

Another subtle case is when the starting pattern has no available moves because every neighbor is forbidden.

N = 1
start = =
forbidden:
.

The correct output is Bob. Alice loses immediately. Any solution that assumes the first player always has a legal flip will fail.

A final edge case appears when the starting vertex is the only unmatched vertex in a maximum matching of the state graph. This is the situation where Alice wins, so counting only connected components or checking the number of remaining states is not enough.

Approaches

The brute force idea is to simulate the game recursively. A state would contain the current pattern and the set of patterns already visited. For every possible move, we try the next state and mark the current player as winning if at least one move makes the opponent lose.

This is correct because the game is finite and every possible continuation is explored. The problem is the number of states. Even though there are only 1024 patterns, the visited set can contain any subset of them, leading to up to 1024 * 2^1024 theoretical states. This is far beyond what can be stored or explored.

The key observation is that the game graph is undirected. Every valid move can be undone by the opposite player, except the original vertex cannot be revisited. This is the classic undirected vertex geography game. For such games, the result can be determined by maximum matchings.

Consider a maximum matching of the remaining graph. If the starting vertex is not covered by some maximum matching, the second player can always answer the first player's move by taking the matched edge back. The matched pairs are consumed together, so the second player never gets stuck first.

If every maximum matching covers the starting vertex, the first player can force a win. The standard way to check which case applies is to compare the maximum matching size of the graph with the maximum matching size after removing the starting vertex. If removing the start reduces the maximum matching size, every maximum matching needed that vertex, so Alice wins. Otherwise Bob wins.

The state graph is a hypercube with some vertices removed. We build it explicitly, split vertices by parity, and run Hopcroft Karp twice.

Approach Time Complexity Space Complexity Verdict
Brute Force O(2^2^N) states in the worst case O(2^N) per state Too slow
Maximum Matching O(V^2 * E^0.5) with Hopcroft Karp O(V + E) Accepted

Algorithm Walkthrough

  1. Convert every pattern into a bitmask. A bit set to 1 means the corresponding digits are different. The starting pattern is converted in the same way, and forbidden patterns are marked as unavailable.
  2. Build the graph of all allowed patterns. Two vertices are connected when their masks differ by exactly one bit, because that represents changing one wheel's equality status.
  3. Split the graph into two parts using the parity of the number of set bits. Flipping one bit always changes parity, so every edge goes between the two parts.
  4. Find the size of a maximum matching in the complete allowed graph. This tells us the maximum number of disjoint pairs that can be formed.
  5. Remove the starting vertex temporarily and find the maximum matching size again. If the size becomes smaller, the start vertex was necessary in every maximum matching.
  6. Print Alice when removing the start decreases the matching size. Otherwise print Bob.

Why it works:

The game is an undirected vertex geography game on the pattern graph. A maximum matching that leaves the start uncovered gives Bob a pairing strategy: whenever Alice enters a matched vertex, Bob immediately moves to its partner. Those partner vertices are always unused because pairs are consumed together. If such a matching does not exist, every maximum matching must include the start, and the starting player has a winning strategy by the theorem for undirected vertex geography.

The matching comparison gives exactly this information. If the best matching without the start is smaller, the start is essential and Alice wins. If it is unchanged, there exists a maximum matching avoiding the start and Bob can use the pairing strategy.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

def hopcroft_karp(adj, left_nodes, right_nodes):
    pair_left = {x: -1 for x in left_nodes}
    pair_right = {x: -1 for x in right_nodes}
    dist = {}

    def bfs():
        q = deque()
        found = False
        for u in left_nodes:
            if pair_left[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1
        while q:
            u = q.popleft()
            for v in adj[u]:
                pu = pair_right[v]
                if pu == -1:
                    found = True
                elif dist[pu] == -1:
                    dist[pu] = dist[u] + 1
                    q.append(pu)
        return found

    def dfs(u):
        for v in adj[u]:
            pu = pair_right[v]
            if pu == -1 or (dist[pu] == dist[u] + 1 and dfs(pu)):
                pair_left[u] = v
                pair_right[v] = u
                return True
        dist[u] = -1
        return False

    result = 0
    while bfs():
        for u in left_nodes:
            if pair_left[u] == -1 and dfs(u):
                result += 1
    return result

def solve_case(n, c, a, b, forbidden):
    bad = [False] * (1 << n)

    start = 0
    for i in range(n):
        if a[i] != b[i]:
            start |= 1 << i

    for s in forbidden:
        mask = 0
        for i, ch in enumerate(s):
            if ch == '.':
                mask |= 1 << i
        bad[mask] = True

    vertices = [i for i in range(1 << n) if not bad[i]]

    color = {}
    for v in vertices:
        color[v] = v.bit_count() & 1

    def build(skip):
        left = []
        right = []
        alive = set(vertices)
        if skip in alive:
            alive.remove(skip)

        for v in alive:
            if color[v] == 0:
                left.append(v)
            else:
                right.append(v)

        adj = {v: [] for v in left}
        for v in left:
            for i in range(n):
                u = v ^ (1 << i)
                if u in alive:
                    adj[v].append(u)
        return hopcroft_karp(adj, left, right)

    full = build(-1)
    without_start = build(start)

    return "Alice" if without_start < full else "Bob"

def main():
    t = int(input())
    ans = []
    for _ in range(t):
        n, c = map(int, input().split())
        a = input().strip()
        b = input().strip()
        forbidden = [input().strip() for _ in range(c)]
        ans.append(solve_case(n, c, a, b, forbidden))
    print("\n".join(ans))

if __name__ == "__main__":
    main()

The input parser first reads the two lock configurations and converts the initial relation between them into a bitmask. The actual digits disappear after this step because only equality information matters.

The graph construction happens inside build. The function optionally removes one vertex, which is needed for the second matching computation. Vertices are split by parity because every hypercube edge changes exactly one bit. The adjacency list only stores edges from the left side, which is the format required by Hopcroft Karp.

The two matching calls are the heart of the solution. The first gives the best possible matching size in the original graph. The second asks whether the same matching size is still possible without the starting vertex. If it is not possible, the start must be included in every maximum matching.

The implementation uses dictionaries for matching pairs because the graph is sparse and the vertex count is small. There is no recursion depth issue because Hopcroft Karp only follows paths through at most 1024 vertices.

Worked Examples

For the first sample:

2
12
89

The starting pattern is .. because both positions differ.

Step Current value Action Matching result
1 .. Build graph 4 states
2 .. removed Compute matching without start Smaller matching
3 .. kept Compare sizes Alice wins

The starting vertex is required by every maximum matching, so Alice has a winning strategy.

For the second sample:

3
204
101

The starting pattern is .=..

Step Current value Action Matching result
1 =.= Build graph Full matching found
2 Start removed Matching size unchanged Bob wins

There exists a maximum matching that avoids the starting state. Bob can pair every Alice move with the matching partner.

Complexity Analysis

Measure Complexity Explanation
Time O(2^N * N * sqrt(2^N)) The graph has at most 1024 vertices and about N * 2^(N-1) edges. Two Hopcroft Karp runs are performed.
Space O(2^N * N) The adjacency list stores the hypercube edges.

With N <= 10, the graph has only 1024 vertices, so explicitly building it and running matching is easily within the limits.

Test Cases

import sys
import io

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)
    data = sys.stdin.readline
    t = int(data())
    out = []
    for _ in range(t):
        n, c = map(int, data().split())
        a = data().strip()
        b = data().strip()
        forbidden = [data().strip() for _ in range(c)]
        out.append(solve_case(n, c, a, b, forbidden))
    sys.stdin = old
    return "\n".join(out)

assert run("""3
2 2
12
89
=.
==
3 1
204
101
.==
3 2
000
000
...
==.
""") == """Alice
Bob
Bob"""

assert run("""1
1 0
0
0
""") == "Bob"

assert run("""1
1 1
0
0
.
""") == "Bob"

assert run("""1
2 0
00
00
""") == "Bob"

assert run("""1
10 0
0000000000
1111111111
""") == "Bob"
Test input Expected output What it validates
Sample cases Alice, Bob, Bob Standard examples
One bit, no forbidden states Bob Smallest graph
Only neighbor forbidden Bob Immediate losing move
All equal start Bob Correct handling of zero difference
Maximum N Bob Performance and large graph construction

Edge Cases

When the starting pattern has no legal moves, the graph contains the start vertex but none of its neighbors. The matching without the start has the same size as the full graph, so the algorithm returns Bob immediately.

For:

1
0
0
.

the start mask is 0, and the only neighbor is forbidden. Alice cannot move, so Bob wins.

When many patterns are forbidden, the algorithm does not assume the hypercube is complete. It removes those vertices before building edges. For example:

1
2 2
00
00
=.
.=

Only the states == and .. remain. The starting state has one move and then the opponent has none. The matching comparison still works because it is performed on the actual remaining graph.

When the starting pattern itself has a special role in the matching, the second matching calculation catches it. A common incorrect approach is to compare only the number of remaining states. The winner depends on whether the start vertex is necessary in a maximum matching, not on the total count of patterns.