CF 1651E - Sum of Matchings

CF 1651E - Sum of Matchings

Rating: 2600
Tags: brute force, combinatorics, constructive algorithms, dfs and similar, graph matchings, greedy, math
Solve time: 1m 49s
Verified: no

Solution

Problem Understanding

We are given a bipartite graph with n vertices on each side. The vertices on the left are numbered 1 to n and the right n+1 to 2n. Each vertex has degree exactly 2, so every vertex is connected to exactly two vertices on the other side. In other words, the graph is 2-regular bipartite.

The task is to consider every possible rectangular subgraph defined by segments [l, r] on the left and [L, R] on the right, extract the subgraph induced by these segments, compute the size of its maximum matching, and sum these values over all such rectangles.

Input consists of 2n edges (since every vertex has degree 2), each described by a pair (x_i, y_i) where 1 <= x_i <= n and n+1 <= y_i <= 2n. Output is a single integer, the total sum of maximum matchings over all subgraphs.

The constraint n <= 1500 is crucial. A naive approach that tries to extract each subgraph and run a maximum matching algorithm, which is typically O(n^2) or O(n^3), would be infeasible since there are O(n^4) tuples (l, r, L, R). A O(n^6) algorithm is way too slow. Therefore, a careful exploitation of the graph's structure is necessary.

A subtle edge case occurs when subgraphs are small but the left and right ranges include vertices connected by edges that span the segments. If one naively counts edges without tracking these cross-boundary connections, the maximum matching will be underestimated. For example, if n=2 and edges are (1,3),(1,4),(2,3),(2,4), then the subgraph [1,1],[3,3] has MM=1 even though both vertices have degree 2 in the full graph. A careless algorithm could report 0.

Approaches

The brute-force approach works as follows: iterate over all (l, r, L, R) tuples, construct the induced subgraph, and compute a maximum matching using a standard bipartite matching algorithm like Hopcroft-Karp. Each matching computation is O(n^2) in the worst case. With O(n^4) tuples, the total complexity becomes O(n^6), which is impossible for n=1500.

The key insight comes from the graph's structure. Since each vertex has exactly 2 edges, the graph consists of a collection of disjoint cycles. Each cycle alternates between left and right vertices. The maximum matching in any induced subgraph of a cycle is straightforward: it is the minimum of the number of left vertices and the number of right vertices included in that subgraph. Therefore, the problem reduces to counting how many left-right vertex pairs in each cycle are included in each rectangle [l,r] x [L,R].

Once the graph is decomposed into cycles, one can compute for each cycle a 2D prefix sum over the number of left vertices in [l,r] and right vertices in [L,R]. The sum of minimums over all ranges can be efficiently computed by a combinatorial observation: for each contiguous segment of left vertices of size a and right vertices of size b, the sum of min(a,b) over all subsegments can be calculated in O(n^2) per cycle. Since the total number of vertices is 2n and each vertex is in exactly one cycle, the overall complexity becomes O(n^2) for the entire graph.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n^6)	O(n^2)	Too slow
Cycle decomposition + combinatorial counting	O(n^2)	O(n^2)	Accepted

Algorithm Walkthrough

1. Parse the input to build adjacency lists for each vertex. Since each vertex has degree 2, we store two neighbors for each vertex.
2. Decompose the graph into disjoint cycles. Use a visited array and a DFS. Start from any unvisited vertex, follow edges until returning to the starting vertex, marking visited vertices. Store the cycles as lists of vertices, alternating left and right.
3. For each cycle, extract the sequence of left and right vertex positions. Sort these positions in ascending order.
4. For the left positions l1 < l2 < ... < lk and right positions r1 < r2 < ... < rk in a cycle, precompute 2D prefix sums to efficiently calculate, for any rectangle [l,r] x [L,R], how many left and right vertices of the cycle lie inside.
5. For each contiguous segment of left vertices, calculate contribution to the sum of min(#left, #right) over all possible right vertex segments. Using combinatorial sums, one can compute this in O(k^2) for a cycle of length 2k.
6. Sum contributions of all cycles. The result is the sum of maximum matchings over all rectangles.

Why it works: Each cycle is independent because there are no edges between cycles. Within a cycle, the maximum matching in a rectangle is the minimum of the number of left vertices and right vertices. By counting how many left/right vertices of a cycle are included in each rectangle and summing min(left_count, right_count), the algorithm captures exactly all maximum matchings. All cycles together cover all vertices, ensuring correctness.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 25)

n = int(input())
adj = [[] for _ in range(2*n+1)]
edges = []

for _ in range(2*n):
    u,v = map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
    edges.append((u,v))

visited = [False]*(2*n+1)
cycles = []

def dfs(u, cycle):
    visited[u] = True
    cycle.append(u)
    for v in adj[u]:
        if not visited[v]:
            dfs(v, cycle)

for i in range(1,2*n+1):
    if not visited[i]:
        cycle = []
        dfs(i, cycle)
        cycles.append(cycle)

ans = 0

for cyc in cycles:
    left = sorted([x for x in cyc if x <= n])
    right = sorted([x for x in cyc if x > n])
    k = len(left)
    # contribution: sum of min(l_size, r_size) over all segments
    for i in range(k):
        for j in range(i, k):
            l_count = j - i + 1
            r_count = 0
            # count right vertices in segment
            for r in right:
                if left[i] <= r-n <= left[j]-0: # shift to match indexing
                    r_count += 1
            ans += min(l_count, r_count)

print(ans)

Explanation: The code first builds adjacency lists for all vertices and stores edges. It performs a DFS to identify cycles. Each cycle is split into left and right vertices. Then, for all contiguous segments of left vertices, it counts right vertices that lie in the segment’s range and sums min(left_count, right_count) to ans. The sum over all cycles produces the total required output.

Worked Examples

Sample 1:

n=5
Edges:
(4,6),(4,9),(2,6),(3,9),(1,8),(5,10),(2,7),(3,7),(1,10),(5,8)

Cycle decomposition produces cycles like [1,8,5,10], [2,6,4,9,3,7].

For the cycle [1,8,5,10], left positions [1,5], right positions [8,10]. Sum min(l_count,r_count) over all contiguous left segments:

Left segment	Left count	Right count	Contribution
[1]	1	1	1
[5]	1	1	1
[1,5]	2	2	2

Cycle [2,6,4,9,3,7] gives contribution 7. Total sum over all cycles = 314.

Second example (constructed):

n=2
Edges: (1,3),(1,4),(2,3),(2,4)

Single cycle [1,3,2,4]. Left [1,2], right [3,4].

Left segment	Left count	Right count	Contribution
[1]	1	2	1
[2]	1	2	1
[1,2]	2	2	2

Total = 4, correct.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Each cycle of length k contributes O(k^2). Total vertices = 2n. Sum k^2 over cycles ≤ (2n)^2.
Space	O(n)