Detailed mathematical approach

Problem Summary

As in Connections I, an array of \(2n\) elements in which every value occurs exactly twice defines \(n\) chords, one per value, joining its two positions. Now each chord may be drawn either above or below the row, and the array is bipartite-connectable when the chords can be split between the two sides so that no two chords on the same side cross.

Two chords that cross must go on opposite sides; two that do not cross may share a side. The input is guaranteed to be bipartite-connectable, and the task is to find the maximum number of chords that can be placed above the row in a valid drawing. The target instance has \(160\,000\) elements, i.e. \(n=80\,000\) chords.

For example \([0,1,2,1,0,2]\) is bipartite-connectable, and the maximum number of above-connections for it is \(2\).

Mathematical Approach

The crossing graph and two-colourability

Chords and the crossing relation are exactly as in Connections I: a value at positions \(p \lt q\) gives the interval \([p,q]\), and \([a,b]\), \([c,d]\) with \(a \lt c\) cross when they interleave, \(a \lt c \lt b \lt d\). Form the crossing graph \(G\): its vertices are the chords and its edges join crossing pairs.

Assigning every chord to "above" or "below" so that crossing chords land on opposite sides is exactly a proper \(2\)-colouring of \(G\) (above \(=\) colour \(0\), below \(=\) colour \(1\)). Such a colouring exists if and only if \(G\) is bipartite, i.e. contains no odd cycle. Three mutually crossing chords, for instance \([0,3],[1,4],[2,5]\) from \([0,1,2,0,1,2]\), form a triangle and make the array not bipartite-connectable.

Maximising the number of chords above

When \(G\) is bipartite, each connected component admits exactly one \(2\)-colouring up to swapping its two colour classes. Since the components are independent, the number of chords sent above can be maximised component by component: for a component with colour classes of sizes \(c_0\) and \(c_1\), placing the larger class above contributes \(\max(c_0,c_1)\). Summing over components,

$$\text{maximum above}=\sum_{\text{components}}\max\bigl(c_0,c_1\bigr).$$

This is why the answer is a sum of per-component maxima rather than a global optimisation: cross-side constraints only couple chords inside the same connected component of \(G\).

Why the local choice is globally optimal

Inside one connected component, a valid \(2\)-colouring has only two orientations: the first colour class above and the second below, or the reverse. There is no edge between different connected components, so choosing the orientation of one component cannot invalidate the orientation of another. Therefore each component contributes independently, and taking the larger colour class above in every component is both locally and globally optimal.

A parity union-find

Bipartiteness and the colour-class sizes are computed together with a weighted (parity) disjoint-set structure. Every chord carries a parity equal to its colour relative to its component root; find returns the root together with that accumulated parity. Uniting two crossing chords imposes that their colours differ: if they already lie in the same component, the stored parities must disagree — if instead they agree, an odd cycle has been found and the array is not bipartite-connectable. Each root keeps a pair of counters \((c_0,c_1)\), the sizes of its two colour classes; merging two components combines these counters according to the linking parity, and the final answer sums \(\max(c_0,c_1)\) over the roots.

How the parity counters merge

Suppose a crossing edge asks chords \(a\) and \(b\) to have opposite colours. If their roots are different, the union operation chooses a link parity \(t=p_a\oplus p_b\oplus 1\), where \(p_a\) and \(p_b\) are the parities returned by find. When one root is attached under the other, vertices whose old parity is \(t\) join colour class \(0\) of the new root, and vertices whose old parity is \(t\oplus1\) join colour class \(1\). This is the reason the size counters can be maintained without ever assigning absolute colours to all chords.

Enumerating crossing pairs with a sweep

To find the edges of \(G\) without testing all \(\binom{n}{2}\) pairs, the chords are swept in order of left endpoint while an ordered set holds the currently open chords keyed by right endpoint. When chord \([\ell,r]\) opens, the chords that cross it are exactly the open ones whose right endpoint lies in the interval \((\ell,r)\): they began before \(\ell\) and end strictly between \(\ell\) and \(r\). An ordered-set range query returns them, and each is united with the current chord in the parity structure before \([\ell,r]\) itself is inserted. The sweep therefore enumerates precisely the crossing pairs.

Endpoint cases in the sweep

The strict interval \((\ell,r)\) is important. A previous chord with right endpoint \(\le \ell\) is already disjoint from the current chord, so the range query skips it. A previous chord with right endpoint \(\ge r\) contains the current chord, so it is nested rather than crossing. Since every array position is a distinct endpoint, the only crossing case left is exactly \(\ell \lt \text{right} \lt r\), which is the range enumerated by the ordered set.

Worked example: \([0,1,2,1,0,2]\)

Value \(0\) is at positions \(0,4\); value \(1\) at \(1,3\); value \(2\) at \(2,5\). The chords are \([0,4]\), \([1,3]\), \([2,5]\). Here \([1,3]\) is nested inside \([0,4]\) (no crossing), while \([2,5]\) crosses both \([0,4]\) and \([1,3]\). The crossing graph is a single path on three vertices, with colour classes \(\{[2,5]\}\) and \(\{[0,4],[1,3]\}\). Placing the larger class above gives \(\max(1,2)=2\) above-connections, the stated answer.

How the Code Works

The C++, Python, and Java implementations share the same pipeline. build_intervals records the first and second occurrence of each value, forms the chords, and sorts them by left endpoint. crosses tests the interleaving condition.

The ParityDsu structure implements the weighted union-find: find performs path compression while folding the parity to the root, unite merges by size and reports a conflict (odd cycle) when a crossing edge would join two equally coloured chords, best_sum returns \(\sum\max(c_0,c_1)\), and component_count counts the roots. solve_array runs the ordered-set sweep, uniting every crossing pair and bailing out the moment the graph proves non-bipartite.

The validation path is exhaustive on small inputs: brute_force_array lists the crossing edges and tries all \(2^n\) above/below assignments, keeping the largest valid above-count, and validate_all_words generates every array of length \(2n\) for \(n\le 4\) and checks that the fast solver agrees with the brute force on bipartiteness, the optimum, and the crossing count. run_checkpoints additionally pins the small cases \([0,1,2,1,0,2]\mapsto 2\), \([0,0,1,1,2,2]\mapsto 3\), and the non-bipartite \([0,1,2,0,1,2]\); main then solves the full instance.

Complexity Analysis

Let \(C\) be the number of crossing pairs actually present. Building and sorting the chords costs \(O(n\log n)\); the sweep performs \(O(n+C)\) ordered-set operations at \(O(\log n)\) each and \(O(n+C)\) near-constant union-find operations, for an overall

$$O\bigl((n+C)\log n\bigr)$$

time and \(O(n)\) memory. On a bipartite-connectable input the sweep visits exactly the crossing edges rather than all \(\binom{n}{2}\) pairs. The brute-force checker is exponential, \(O(2^n)\), and runs only on the tiny validation arrays.

Footnotes and References

1. Problem page: Project Euler 1002
2. Bipartite graph: Wikipedia - Bipartite graph
3. Circle graph (chord intersection graph): Wikipedia - Circle graph
4. Graph two-colouring: Wikipedia - Graph coloring
5. Disjoint-set (union-find) data structure: Wikipedia - Disjoint-set data structure
6. Connected component: Wikipedia - Component (graph theory)