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

Solution

Problem Understanding

The problem describes a binary array whose positions can be viewed as vertices of a graph. Each allowed operation is an edge: using that edge flips the two bits at its endpoints. Starting from an array of all zeroes, we need to decide whether a given target bit configuration can be produced.

The input gives the number of positions, the desired final bits, and the list of pairs of positions that can be flipped together. The output is whether some ordering and repetition of these pair flips can create exactly the target array.

The limits are large enough that simulating operations is not realistic. With up to $10^5$ positions and $10^5$ operations, even an approach that repeatedly tries available operations can reach around $10^{10}$ work in the worst case. The solution needs to be close to linear, which suggests looking for a structural property of the graph instead of constructing the sequence of operations.

The key edge cases come from graph components. Consider an isolated vertex:

n = 2
target = [1, 0]
m = 0

The answer is No. The first position has no edge connected to it, so there is no operation that can ever change it from zero.

A second case is a component where all vertices are connected but the target has odd parity:

n = 3
target = [1, 1, 1]
m = 2
edges:
1 2
2 3

The answer is No. Every operation flips exactly two bits, so the number of ones inside this component always changes by an even amount modulo two. The component starts with zero ones, so it can only finish with an even number of ones.

A careless implementation may only check whether the whole array has an even number of ones. That fails when the graph has multiple components:

n = 4
target = [1, 1, 1, 0]
m = 1
edge:
1 2

The answer is No. The first component has two ones and is possible, but vertex 3 is a separate component with one one, which cannot be changed.

Approaches

The brute-force idea is to try applying operations and track every reachable binary array. Since each bit has two states, there can be $2^n$ possible arrays. Even for $n=40$, this is already too large, and the given limit of $10^5$ makes state exploration impossible.

Another direct approach is to treat every operation as an equation over binary values. Each edge says that applying it toggles both endpoints, so the final state is the XOR combination of selected edges. Solving the full linear system with generic Gaussian elimination would work conceptually, but it is unnecessary and would be more complicated than the graph structure requires.

The important observation is that an operation never changes the parity of the number of ones inside a connected component. Both endpoints of an edge belong to the same component, and flipping both bits changes the count of ones by either plus two, minus two, or zero. In modulo two arithmetic, the component parity stays unchanged.

This condition is also sufficient. Inside one connected component, any pair of vertices can effectively be toggled together by walking along paths in the component. By combining such path operations, we can create any configuration that has even parity. A component with at least one edge can generate every even-parity assignment, while an isolated vertex can never be changed.

The problem reduces to finding connected components, counting the number of target ones in each component, and checking these parity conditions.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n)	O(2^n)	Too slow
Optimal	O(n + m)	O(n)	Accepted

Algorithm Walkthrough

Build an undirected graph where every allowed operation becomes an edge between its two positions. The operations only depend on which vertices are connected, so the exact order of edges does not matter.
Find every connected component using DFS or BFS. While visiting a component, count how many target bits are equal to one and count how many vertices belong to the component.
If a component contains only one vertex and its target bit is one, immediately reject it. There is no operation touching that vertex, so it must remain zero.
For every component with edges, check the number of ones inside it. If that count is odd, reject the target because component parity cannot change.
If every component passes these checks, accept the target.

Why it works: each operation flips two vertices from the same connected component, so the parity of ones in every component is an invariant. The invariant gives a necessary condition. For sufficiency, a connected component allows us to move a toggle through paths and combine edge operations, which means every even-sized set of vertices can be flipped. Since every valid component target has even parity, all such targets are reachable.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    b = list(map(int, input().split()))
    
    m = int(input())
    graph = [[] for _ in range(n)]
    
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n

    for start in range(n):
        if not visited[start]:
            stack = [start]
            visited[start] = True
            ones = 0
            size = 0

            while stack:
                u = stack.pop()
                size += 1
                ones += b[u]

                for v in graph[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)

            if size == 1:
                if ones == 1:
                    print("No")
                    return
            else:
                if ones % 2 == 1:
                    print("No")
                    return

    print("Yes")

if __name__ == "__main__":
    solve()

The graph construction directly represents the available operations. An edge is undirected because flipping positions $i$ and $j$ has the same effect regardless of how we describe the pair.

The DFS loop processes one connected component at a time. The variable ones stores the parity information that matters, while size distinguishes normal components from isolated vertices. The isolated vertex case needs separate handling because an even parity check would incorrectly accept a component containing a single zero bit and reject only after counting, but a single one can never be produced.

The traversal uses an explicit stack instead of recursion. Python recursion depth is too small for a graph containing a path of length $10^5$, so iterative DFS avoids stack overflow.

Worked Examples

Sample 1

Input:

The components are {1,3,4} and {2,5}.

Step	Component	Size	Ones in target	Decision
1	{1,3,4}	3	2	Valid, even parity
2	{2,5}	2	2	Valid, even parity

The algorithm accepts because every component satisfies the invariant.

Sample 2

Input:

Step	Component	Size	Ones in target	Decision
1	{1,2}	2	1	Invalid, odd parity

The only operation flips both bits together, so the two positions must always have equal parity. Producing [0,1] is impossible.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each vertex and edge is visited once during graph traversal
Space	O(n + m)	The graph and visited array store the input structure

The limits allow linear processing because the algorithm only scans the graph once. It avoids any dependence on the number of possible bit configurations.

Test Cases

import sys, io

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()

    out = sys.stdout.getvalue()
    sys.stdin = old_stdin
    sys.stdout = old_stdout
    return out

# sample 1
assert run("""5
1 1 0 1 1
3
1 3
3 4
2 5
""") == "Yes\n"

# sample 2
assert run("""2
0 1
1
1 2
""") == "No\n"

# isolated vertex cannot be changed
assert run("""3
0 1 0
1
1 3
""") == "No\n"

# disconnected components with correct parity
assert run("""4
1 1 1 1
2
1 2
3 4
""") == "Yes\n"

# all zero target is always possible
assert run("""5
0 0 0 0 0
1
1 2
""") == "Yes\n"

Test input	Expected output	What it validates
Single connected component with even ones	Yes	Basic reachable configuration
Connected component with odd ones	No	Parity invariant
Isolated vertex set to one	No	Unchangeable vertices
Multiple components with valid parity	Yes	Component-wise checking
All-zero target	Yes	Doing no operations

Edge Cases

For an isolated vertex, the algorithm creates a component with size one. For input:

the components are {1,3} and {2}. The second component has one vertex and one required one, so the algorithm returns No. It never tries to invent an operation for that vertex.

For an odd-parity connected component:

the traversal finds one component containing all three vertices. The count of target ones is three, which is odd, so the algorithm rejects it. Every available operation flips two positions, keeping the component parity unchanged.

For disconnected graphs, each component must be checked separately:

The first component {1,2} has two ones and is valid. The remaining vertices are isolated, and vertex three requires a one without any incident edge. The algorithm rejects at that component, avoiding the common mistake of checking only the total number of ones.

CF 102862K - Binary Sequence