Detailed mathematical approach

Problem Summary

We are given an array of \(2n\) elements in which every value occurs exactly twice. The two positions of a value form a chord (an interval) over the row. The array is called connectable when all its chords can be drawn above the row without any two of them crossing.

From one array we may form \(2^n\) new arrays by independently keeping or deleting both occurrences of each value. The connectivity number is the number of those \(2^n\) sub-arrays that are connectable. Equivalently, it counts the subsets of the \(n\) chords that are pairwise non-crossing. The required answer is this count modulo

$$M=1\,003\,443\,221.$$

For example \([0,1,0,1]\) has connectivity number \(3\), and the \(20\)-element array \([0,1,2,3,1,4,0,5,4,2,6,7,3,8,6,5,9,8,9,7]\) has connectivity number \(86\). The target instance is a \(40\,000\)-element array, i.e. \(n=20\,000\) chords.

The number of non-crossing subsets is astronomically large (up to \(2^n\)), so it is accumulated modulo \(M\); brute force over all \(2^n\) subsets is only used to validate the fast method on tiny inputs.

Mathematical Approach

Chords, crossings, and what is being counted

If a value sits at positions \(p \lt q\), its chord is the interval \([p,q]\). Two chords \([a,b]\) and \([c,d]\) with \(a \lt c\) cross exactly when they interleave,

$$a \lt c \lt b \lt d.$$

If they do not interleave they are either nested (one interval contains the other) or disjoint. A set of chords is drawable above the line without crossings precisely when no two of them cross, so the connectivity number equals the number of crossing-free subsets, including the empty subset. In graph terms, build the crossing graph whose vertices are the chords and whose edges join crossing pairs; the connectivity number is the number of independent sets of that graph.

Non-crossing families are laminar

Any pairwise non-crossing collection of chords is a laminar family: any two members are nested or disjoint, never interleaved. Laminar families are exactly the forests of the containment order, and it is this nesting structure — absent in a general graph — that turns the count into a polynomial-time dynamic program rather than an intractable independent-set count.

Why closing order is enough

The fast method does not explicitly build the whole crossing graph. A chord that opens inside \([\ell_i,r_i]\) and closes after \(r_i\) crosses chord \(i\), so it cannot appear in a subset that also contains \(i\). At the instant chord \(i\) closes, every chord fully nested inside it has already closed, while every chord that crosses it is still open. Thus the value already accumulated at slot \(i+1\) is exactly the count of admissible inner choices that can be combined with chord \(i\).

A dynamic program over the nesting structure

Sort the chords by left endpoint, \(\ell_0 \lt \ell_1 \lt \dots \lt \ell_{n-1}\) (all endpoints are distinct), and write \(r_i\) for the right endpoint of chord \(i\). For each chord define

$$\operatorname{next}(i)=\min\{\,j : \ell_j \gt r_i\,\},$$

the first chord lying entirely to the right of chord \(i\). The chords with index in \((i,\operatorname{next}(i))\) are precisely those that open inside chord \(i\); among them the nested ones close before \(r_i\) while the crossing ones close after \(r_i\).

The algorithm processes chords in order of increasing right endpoint and maintains an array \(\textit{ways}\) (initialised to all ones) together with a companion array \(\textit{delta}\). When chord \(i\) closes, every chord nested inside it has already closed, so the value

$$\textit{inside}(i)=\textit{ways}[i+1]$$

is the number of non-crossing subsets that live strictly inside chord \(i\). The subsets that include chord \(i\) are then obtained by freely combining one such inner configuration with any non-crossing configuration drawn from the chords entirely to its right:

$$\textit{inc}=\textit{inside}(i)\cdot \textit{ways}[\operatorname{next}(i)].$$

This increment is recorded in \(\textit{delta}[i]\) and added into \(\textit{ways}[i]\). It must also reach every earlier chord \(p \lt i\) that is still open and whose nested region has already been passed (\(\operatorname{next}(p)\le i\)): for such a \(p\), the freshly closed chord \(i\) extends the subsets that include \(p\) through the term \(\textit{inside}(p)\cdot \textit{delta}[\operatorname{next}(p)]\). Propagating this contribution down to all earlier slots takes \(O(n)\) work per closing chord, and after the last chord closes the accumulated total is

$$\text{connectivity number}=\textit{ways}[0]\bmod M.$$

The two array entries \(\textit{ways}[i]\) and \(\textit{delta}[i]\) thus encode, respectively, the running count of valid subsets anchored at slot \(i\) and the most recent increment to be forwarded — the bookkeeping that lets a single linear sweep per chord account for both the "nested inside" and "continues to the right" choices.

The invariant behind ways and delta

Think of slot \(s\) as the boundary just before chord \(s\) in left-endpoint order. After each closing event, \(\textit{ways}[s]\) contains all valid selections whose next available left endpoint is at or after slot \(s\), restricted to chords already closed by the sweep. The companion value \(\textit{delta}[s]\) stores only the newest contribution that still has to be forwarded to earlier open ancestors. This separation prevents double-counting: older contributions have already been absorbed into \(\textit{ways}\), while the loop over \(p=i-1,\dots,0\) propagates only the fresh \(\textit{delta}\) term created by the chord that just closed.

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

Value \(0\) sits at positions \(0,2\) and value \(1\) at positions \(1,3\), giving chords \([0,2]\) and \([1,3]\). Since \(0 \lt 1 \lt 2 \lt 3\) they interleave, so they cross. The crossing-free subsets are therefore \(\varnothing\), \(\{[0,2]\}\) and \(\{[1,3]\}\) — the full pair is excluded — for a connectivity number of \(3\), matching the stated value.

How the Code Works

The C++, Python, and Java implementations share the same pipeline. load_csv reads the comma-separated array. build_intervals records the two positions of each value, forms the chords \([p,q]\), sorts them by left endpoint, and asserts that the left endpoints are strictly increasing.

connectivity_number builds \(\operatorname{next}(i)\) with a binary search (upper_bound over the sorted left endpoints), orders the chords by right endpoint, and runs the sweep above using the \(\textit{ways}\), \(\textit{delta}\), \(\textit{inside}\), and \(\textit{active}\) arrays, with all arithmetic carried out modulo \(M\) through add_mod and mul_mod (the latter widening to \(128\) bits in C++; \(64\) bits already suffice in Java and Python since the factors are below \(M\)).

crosses and brute_connectivity form the validation path: the latter simply enumerates all \(2^n\) subsets and counts those with no crossing pair. run_checkpoints checks the published values \(3,8,5,8,86\) on five small arrays and confirms that the fast result equals the brute-force count reduced modulo \(M\); main then evaluates the \(40\,000\)-element instance.

Complexity Analysis

Building the chords costs \(O(n)\) plus \(O(n\log n)\) for the two sorts and the binary searches. The closing sweep performs an \(O(n)\) propagation for each of the \(n\) chords, so the dominant cost is

$$O(n^2)$$

time with \(O(n)\) memory. For \(n=20\,000\) this is a few hundred million constant-time modular operations, comfortably fast in C++. The brute-force checker is exponential, \(O(2^n\cdot n^2)\), and is restricted to the small checkpoint arrays only.

Footnotes and References

1. Problem page: Project Euler 1001
2. Circle graph (chord intersection graph): Wikipedia - Circle graph
3. Laminar set family: Wikipedia - Laminar set family
4. Independent set (graph theory): Wikipedia - Independent set
5. Dynamic programming: Wikipedia - Dynamic programming
6. Modular arithmetic: Wikipedia - Modular arithmetic