10.41

Idea.
Cutting at position p removes the two characters that lie back-to-back in the sheet; let the helper
  rev(p) → (q , ch[q])
return the opposite position q and the character printed there. Thus every feasible cut corresponds to one unordered pair
  P = { (p , ch[p]) , (q , ch[q]) }
containing one or two symbols of the alphabet. The task is to decide whether a multiset of such pairs can supply all letters of the wanted string T.

Flow formulation.
Build a bipartite flow network that “buys” complete pairs and routes the symbols they provide to the demanded letters:

SOURCE ──► pair-node P (capacity 2) ──► letter-node σ (capacity 1) . . letter-node σ ──► SINK (demand = #σ in T)

• One pair-node for each physical pair of positions (constructed by scanning the magazine once and calling rev). • Edge SOURCE → P has capacity 2 (because at most the two printed symbols can flow out of the sheet). • From P add one edge of capacity 1 to the letter-node of every symbol that appears in the pair   (if both sides print the same symbol, give that edge capacity 2). • For every alphabet symbol σ add an edge σ → SINK whose capacity equals the number of times σ occurs in T.

Algorithm. buildGraph(magazine, T): seen = set() for position p in 0..N-1: if p in seen: continue q , b = rev(p) # opposite position and its character a = ch[p] seen.add(p); seen.add(q) addPairNode({a,b}) for σ in alphabet: addEdge(letterNode(σ), SINK, need[σ]) # need[σ] = count in T run any max-flow (Dinic/Edmonds-Karp) return totalFlow == |T|
Correctness.
• Capacity on SOURCE → P forces the flow to “pay” one unit for each character extracted from a physical pair, so the algorithm never uses more letters than the pair holds.
• Conversely, taking at least one unit of flow through P implies the whole pair is cut, exactly mirroring a real magazine cut-out. Therefore a feasible flow corresponds one-to-one with a valid sequence of cuts that delivers the transported letters. If and only if all |T| units reach the sink, every character of T can be pasted.

Complexity.
Magazine length = N, number of pairs = N / 2. Nodes: ≤ N / 2 + 26, Edges: ≤ N + 52. Using Dinic, time O(E √V) ≈ O(N√N) in the worst case, and O(N) memory. This easily handles typical page sizes.

Result.
Run the max-flow; if its value equals the length of the desired string, the cut-and-paste is possible, otherwise it is not.

Back to Chapter 10