CF 1320D - Reachable Strings

We are given a fixed binary string, and we repeatedly consider two kinds of local transformations on any contiguous segment of length three: swapping 011 into 110, or the reverse swap 110 into 011.

codeforcescompetitive-programmingdata-structureshashingstrings

CF 1320D - Reachable Strings

Rating: 2500
Tags: data structures, hashing, strings
Solve time: 4m 29s
Verified: no

Solution

Problem Understanding

We are given a fixed binary string, and we repeatedly consider two kinds of local transformations on any contiguous segment of length three: swapping 011 into 110, or the reverse swap 110 into 011. Each operation only touches three consecutive characters and preserves the total number of ones, but it may move ones around inside the string.

The core question is not about applying operations directly. Instead, we are asked a reachability question on substrings: for two equal-length substrings of the original string, we must determine whether one can be transformed into the other using a sequence of these local swaps applied anywhere inside the substring.

A key observation already hidden in the statement is that operations never interact across substring boundaries in a way that changes global feasibility. Each query is therefore asking for a structural equivalence test between two binary strings under a constrained permutation system generated by these local 011 <-> 110 swaps.

The constraints are large: both the string length and number of queries are up to 200,000. Any solution that inspects substrings naively per query will immediately fail, since even reading all queried substrings would already be quadratic in the worst case. This forces a preprocessing approach with near constant or logarithmic query time.

A naive idea is to simulate all possible transformations or to BFS over strings. This is impossible because the state space of a length n binary string is 2^n, and even local transitions are too many.

There are also subtle pitfalls. One common mistake is to assume that only the number of ones determines reachability. That fails. For example, 0110 and 1010 have the same number of ones but are not always reachable under the allowed operations in a substring-restricted context. Another mistake is to treat the operation as arbitrary permutation of ones, which ignores parity-like constraints induced by adjacency structure.

The correct invariant turns out to be more refined than just counts.

Approaches

The brute-force interpretation is to treat each substring as a node in a huge implicit graph, where edges correspond to applying a 011 <-> 110 swap. We would run a BFS or DFS from one substring state to check if we can reach another. Even for a single query this is infeasible, since each state has O(n) possible moves and the number of states is exponential.

The crucial simplification comes from understanding what the operation actually does globally. The swap 110 -> 011 moves a 1 one position to the right across a 0, and 011 -> 110 moves a 1 one position to the left across a 0, but only in a very specific pattern involving two adjacent ones or zeros. This means ones are effectively allowed to “bubble” through zeros, but with a constraint: relative ordering among certain patterns is partially preserved.

A more useful perspective is to encode the string as positions of ones. The operations allow adjacent swaps of ones and zeros but only in configurations where a 1 passes over another 1 indirectly through a 0 gap. This leads to the key fact: within any substring, reachability depends only on the multiset of distances between consecutive ones, or equivalently on a prefix structure derived from the positions of ones.

The standard solution reframes the problem using prefix sums of ones and a transformed coordinate system. If we define a prefix array pref[i] as the number of ones up to position i, then each substring can be normalized by shifting indices so that comparisons become independent of absolute position. The remaining invariant that distinguishes reachable substrings is a hash-like encoding of the sequence of gaps between ones inside the substring.

To compute this efficiently, we precompute positions of ones and build prefix hashes over an array that represents distances between consecutive ones. Then each substring query is reduced to comparing two canonical representations computed in O(1) using hashing with prefix precomputation.

The brute-force works because it directly explores transformations, but fails because transformations are exponential in nature. The observation that the system preserves a structured invariant over ones’ relative spacing reduces the problem to interval comparison on a precomputed sequence, allowing O(1) queries after O(n) preprocessing.

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

Algorithm Walkthrough

We first extract structural information about the string that remains stable under allowed swaps.

  1. Build an array pos containing indices of all 1s in the string. This compresses the string into the structure that actually moves under operations.
  2. Construct a derived array g representing gaps between consecutive ones, defined as g[i] = pos[i+1] - pos[i]. This captures how ones are spaced.
  3. Precompute prefix hashes over g using a rolling hash. This allows any segment of gaps to be compared in O(1), since reachability depends on whether two substrings induce identical gap structures after normalization.
  4. Build an additional prefix array for counting ones, so each query can quickly determine how many ones lie in a substring. This is required because substrings with different numbers of ones are never reachable.
  5. For each query, extract the substring [l1, r1] and [l2, r2]. If the number of ones differs, immediately return NO.
  6. Otherwise, map both substrings into their induced gap-sequences using binary search on pos, and compare their hash values. If the hashes match, return YES; otherwise NO.

The reason this works is that the allowed operations only permute ones locally without changing the relative structure of gaps between them. Any sequence of valid swaps preserves the multiset of gap lengths between consecutive ones inside a substring, and the hashing step captures this invariant exactly.

Python Solution

import sys
input = sys.stdin.readline

MOD = (1 << 61) - 1
BASE = 91138233

def modmul(a, b):
    return (a * b) & MOD

def build_hash(arr):
    n = len(arr)
    h = [0] * (n + 1)
    p = [1] * (n + 1)
    for i in range(n):
        p[i + 1] = modmul(p[i], BASE)
        h[i + 1] = (modmul(h[i], BASE) + arr[i] + 1) & MOD
    return h, p

def get_hash(h, p, l, r):
    return (h[r] - modmul(h[l], p[r - l])) & MOD

def solve():
    n = int(input())
    s = input().strip()

    pos = []
    pref = [0] * (n + 1)

    for i, c in enumerate(s):
        pref[i + 1] = pref[i] + (c == '1')
        if c == '1':
            pos.append(i)

    g = []
    for i in range(len(pos) - 1):
        g.append(pos[i + 1] - pos[i])

    if g:
        h, p = build_hash(g)
    else:
        h, p = [0], [1]

    q = int(input())

    def get_sub_hash(l, r):
        # extract ones in range via two pointers
        import bisect
        L = bisect.bisect_left(pos, l)
        R = bisect.bisect_right(pos, r) - 1

        if L >= R:
            return 0

        return get_hash(h, p, L, R)

    for _ in range(q):
        l1, l2, ln = map(int, input().split())
        l1 -= 1
        l2 -= 1
        r1 = l1 + ln
        r2 = l2 + ln

        if pref[r1] - pref[l1] != pref[r2] - pref[l2]:
            print("No")
            continue

        if get_sub_hash(l1, r1) == get_sub_hash(l2, r2):
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    solve()

The implementation first compresses the string into positions of ones, since zeros only matter insofar as they separate ones. The prefix array pref allows constant-time counting of ones per substring, which is used as a quick rejection test.

The g array encodes spacing between consecutive ones globally. We then build a rolling hash over this array so that any interval of gaps can be compared efficiently. The helper function get_sub_hash maps a substring into the corresponding interval in pos using binary search, then converts that into a range over g.

A subtle point is the handling of substrings with zero or one one. In that case, there are no gaps, and the canonical representation is empty, so we return zero as the hash.

Worked Examples

Consider a simple string t = 11011.

We preprocess positions of ones:

index 0 1 2 3 4
char 1 1 0 1 1

So pos = [0, 1, 3, 4], and gaps g = [1, 2, 1].

For a query comparing [1, 3, 3] and [3, 5, 3]:

First substring 110 has ones at positions [0,1] so its gap signature is [1].

Second substring 011 also has two ones at positions [3,4], also gap [1].

Step Substring 1 Substring 2
L, R in pos [0,1] [2,3]
gap range g[0:1] g[2:3]
hash h(1) h(1)

Both match, so answer is YES.

This demonstrates that absolute location does not matter, only internal spacing.

Complexity Analysis

Measure Complexity Explanation
Time O(n + q log n) preprocessing builds prefix structures; each query uses binary search
Space O(n) stores positions, gaps, and hash arrays

The preprocessing is linear in the string size, and each query performs a constant number of binary searches and hash lookups. This fits comfortably within the constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import prod
    import builtins

    input = sys.stdin.readline

    MOD = (1 << 61) - 1
    BASE = 91138233

    def modmul(a, b):
        return (a * b) & MOD

    def build_hash(arr):
        n = len(arr)
        h = [0] * (n + 1)
        p = [1] * (n + 1)
        for i in range(n):
            p[i + 1] = modmul(p[i], BASE)
            h[i + 1] = (modmul(h[i], BASE) + arr[i] + 1) & MOD
        return h, p

    def get_hash(h, p, l, r):
        return (h[r] - modmul(h[l], p[r - l])) & MOD

    def solve():
        n = int(input())
        s = input().strip()

        pos = []
        pref = [0] * (n + 1)

        for i, c in enumerate(s):
            pref[i + 1] = pref[i] + (c == '1')
            if c == '1':
                pos.append(i)

        g = []
        for i in range(len(pos) - 1):
            g.append(pos[i + 1] - pos[i])

        if g:
            h, p = build_hash(g)
        else:
            h, p = [0], [1]

        q = int(input())

        import bisect

        def get_sub_hash(l, r):
            L = bisect.bisect_left(pos, l)
            R = bisect.bisect_right(pos, r) - 1
            if L >= R:
                return 0
            return get_hash(h, p, L, R)

        for _ in range(q):
            l1, l2, ln = map(int, input().split())
            l1 -= 1
            l2 -= 1
            r1 = l1 + ln
            r2 = l2 + ln

            if pref[r1] - pref[l1] != pref[r2] - pref[l2]:
                print("No")
                continue

            if get_sub_hash(l1, r1) == get_sub_hash(l2, r2):
                print("Yes")
            else:
                print("No")

    return run.__wrapped__() if hasattr(run, "__wrapped__") else None

# provided samples
assert run("""5
11011
3
1 3 3
1 4 2
1 2 3
""") == """Yes
Yes
No
"""

# custom cases
assert run("""1
0
1
1 1 1
""") == "Yes\n"

assert run("""3
111
2
1 1 3
1 1 1
""") == "Yes\nYes\n"

assert run("""5
10101
2
1 3 3
2 4 3
""") == "Yes\nYes\n"
Test input Expected output What it validates
single zero Yes trivial single-character reachability
all ones Yes/Yes uniform structure stability
alternating Yes/Yes symmetric substrings with identical structure

Edge Cases

A first edge case is when a substring contains zero or one 1. For example, in 10000, the substring [2,5] has no ones. The algorithm maps this to an empty gap sequence, so any other all-zero substring produces the same canonical hash, correctly returning YES.

Another case is when substrings have the same number of ones but different internal spacing. For example, 10100 versus 10010 both contain two ones, but their gap structures differ. The binary search extracts different intervals of pos, producing different gap arrays, so the hashes differ and the algorithm correctly returns NO.

A final subtle case is when substrings overlap differently with the global pos array boundaries. Because mapping is done via bisect_left and bisect_right, the extracted interval is always aligned to actual ones inside the substring, preventing off-by-one inclusion of boundary zeros, which would otherwise corrupt the gap structure.