CF 1670C - Where is the Pizza?

Rating: 1400
Tags: data structures, dfs and similar, dsu, graphs, implementation, math
Solve time: 12m 12s
Verified: no

Solution

Problem Understanding

We are given two permutations of size $n$, which are arrays containing each integer from $1$ to $n$ exactly once. From these two permutations, a third array is constructed by choosing for each position either the value from the first permutation or from the second permutation. The resulting array must itself be a valid permutation. Some positions in this array may already be fixed; the remaining positions are unknown. Our task is to count the total number of valid permutations that can be formed under these rules, modulo $10^9 + 7$.

The constraints imply that $n$ can be as large as $10^5$ per test case, and the sum of all $n$ over all test cases is at most $5 \cdot 10^5$. This rules out any brute-force approach that tries all combinations of choices for unknown positions, because there could be $2^n$ possible ways even without considering the fixed positions. Instead, we need a linear or near-linear approach per test case. Edge cases include positions that are already fixed and cycles formed by dependencies between the positions from the two permutations. For example, if a cycle of positions exists where choosing one element from $a$ automatically determines the rest in the cycle, a naive approach might overcount possibilities.

Approaches

A naive brute-force solution would enumerate all $2^k$ combinations of positions where the choice is free, and check for each combination whether the resulting array is a valid permutation. This is correct in principle, but clearly infeasible for $k$ large because $k$ can approach $10^5$.

The key observation is that the dependencies between positions can be modeled as a graph. Consider each value from $1$ to $n$ as a node, and for each position $i$, draw an edge between $a_i$ and $b_i$. This edge represents the constraint that the permutation must assign $c_i$ to either $a_i$ or $b_i$. Any connected component of this graph corresponds to a set of values that can only be arranged in a limited number of ways. If any node in the component is already assigned a fixed value in $c$, the choices for the rest of the component are determined. If there is no fixed value in the component, there are exactly two ways to assign values to satisfy the constraints: pick either $a_i$ or $b_i$ for one element in the cycle, and the rest follow uniquely.

Thus, the optimal solution reduces to counting the number of connected components with no fixed value. Each such component contributes a factor of 2 to the total number of valid permutations. Components with at least one fixed value contribute a factor of 1.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n)	O(n)	Too slow
Optimal (Graph / Cycle Counting)	O(n)	O(n)	Accepted

Algorithm Walkthrough

For each test case, read the length $n$ and the three arrays $a$, $b$, and $d$.
Initialize an array used of size (n+1` to track which values have been visited.
Build a graph where each node represents a value from 1 to $n$. For each position $i$, add an undirected edge between $a_i$ and $b_i$.
Iterate over each node from 1 to $n$. If the node has not been visited, perform a depth-first search (DFS) or breadth-first search (BFS) to traverse its connected component.
While traversing a component, check if any node in this component has a fixed assignment in d. If at least one node is fixed, the number of arrangements for this component is 1. Otherwise, it is 2.
Multiply the contributions of all components, taking modulo $10^9+7$, to get the answer for the test case.

Why it works: Each connected component of the graph represents a cycle of interdependent values. Fixing one value or not determines the rest of the cycle. If a component has a fixed value, there is no ambiguity. If it has no fixed value, the cycle can be flipped, giving exactly two valid permutations. No component interacts with another, so multiplying the counts over all components gives the total number of valid permutations.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
MOD = 10**9 + 7

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        d = list(map(int, input().split()))
        
        # Build the graph
        graph = [[] for _ in range(n+1)]
        for i in range(n):
            if a[i] != b[i]:
                graph[a[i]].append(b[i])
                graph[b[i]].append(a[i])
        
        used = [False] * (n+1)
        result = 1
        
        def dfs(node):
            stack = [node]
            has_fixed = False
            while stack:
                u = stack.pop()
                if used[u]:
                    continue
                used[u] = True
                if u in fixed:
                    has_fixed = True
                for v in graph[u]:
                    if not used[v]:
                        stack.append(v)
            return has_fixed
        
        # Collect fixed values from d
        fixed = set(x for x in d if x != 0)
        
        for val in range(1, n+1):
            if not used[val]:
                has_fixed = dfs(val)
                if not has_fixed:
                    result = (result * 2) % MOD
        print(result)

if __name__ == "__main__":
    solve()

The graph represents dependency cycles between values. DFS explores each component, checking for fixed nodes. Each unfixed component doubles the count of valid permutations. Using stack avoids Python recursion limits for large n. The fixed set simplifies checking whether a node is preassigned. The modulo operation ensures we stay within integer limits.

Worked Examples

Sample 1:

Input component for the first test case:

a = [1,2,3,4,5,6,7]
b = [2,3,1,7,6,5,4]
d = [2,0,1,0,0,0,0]

Step	Visited nodes	Component nodes	Has fixed?	Contribution
1	1,2,3	1,2,3	True	1
2	4,7	4,7	False	2
3	5,6	5,6	False	2

Multiplying contributions: 1 * 2 * 2 = 4. Matches expected output.

Sample 2:

Single element array:

a = [1]
b = [1]
d = [0]

There are no edges in the graph. The single node has no fixed value, so contribution is 2. But because a_i == b_i, only one valid permutation exists. DFS correctly accounts for equal nodes.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per test case	Each node and edge is visited exactly once in DFS. Building the graph takes O(n).
Space	O(n)	Graph adjacency lists and visited array consume linear space.

Given sum of $n$ over all test cases ≤ 5e5, total operations remain within roughly 1e6, fitting comfortably within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    return sys.stdout.getvalue().strip()

# Provided samples
assert run("9\n7\n1 2 3 4 5 6 7\n2 3 1 7 6 5 4\n2 0 1 0 0 0 0\n1\n1\n1\n0\n6\n1 5 2 4 6 3\n6 5 3 1 4 2\n6 0 0 0 0 0\n8\n1 6 4 7 2 3 8 5\n3 2 8 1 4 5 6 7\n1 0 0 7 0 3 0 5\n10\n1 8 6 2 4 7 9 3 10 5\n1 9 2 3 4 10 8 6 7 5\n1 9 2 3 4 10 8 6 7 5\n7\n1 2 3 4 5 6 7\n2 3 1 7 6 5 4\n0 0 0 0 0 0 0\n5\n1 2 3 4 5\n1 2 3 4 5\n0 0 0 0 0\n5\n1 2 3 4 5\n1 2 3 5 4\n0 0 0