Distinct Values Subarrays

\(I\) is an index set: \(I=[0,n) = \{0, 1, \dots, n - 1 \}\)

\([i,j] = \{i,i+1,\dots,j\}\), \(|[i,j]| = j - i + 1\)

\((I, F)\) is a set family: \((I, F)\), \(F = \{[i,j] \mid i,j \in I, i \leq j \} = \cup_{j \in I} \{[i,j] \mid i \in I, i \leq j\}\)

\(|F|=|\cup_{j \in I} \{[i,j] \mid i \in I, i \leq j\}|=\sum_{j \in I}|\{[i,j] \mid i \in I, i \leq j\}|=\sum_{j=0}^{n-1}j+1\)

\(|F|=\binom{n + 1}{2}\)

\(A\) is some finite set: \(A = \{\text{a}, \text{b}, \dots\}\). \(s\) is a sequence over \(A\): \(s \in A^{I}\)

\(F_s\) is the family of index sets corresponding to all subarrays of \(s\) that have distinct elements: \(F_s=\{[i,j] \mid i,j \in I, i \leq j, \land_{i,j \in I, i \neq j} s(i) \neq s(j)\}\).

\(F_s\) is a finite, hereditary (downward-closed) set family, so it equals the union of the ideals of its maximal elements. It's not an independence system though because the empty set is not in \(F_s\) The maximal elements of \(F_s\) are index sets corresponding to distinct subarrays, that are not included in any other index set: these subarrays can't be extended without repeating an element. For example, consider this sequence: \(s\equiv\langle \text{abcbd}\rangle\). The maximal distinct subarrays are \(\langle \text{abc}\rangle\) and \(\langle \text{cbd}\rangle\). The corresponding index sets are \(\{0,1,2\}\) and \(\{2,3,4\}\). \(F_s = I(\{0,1,2\}) \cup I(\{2,3,4\})\).

\(I(X)=\{Y \mid Y \in F_s, Y \subseteq X\}\) is the ideal of \(X\). A "sliding window" algorithm for computing \(|F_s|\) follows from this observation: expand a subarray to find the maximal distinct subarrays and use the inclusion-exclusion principle to count their union: \(|F_s|=|I(J_1)| + |I(J_2)| - |I(J_1) \cap I(J_2)|\). This is easy to implement because only adjacent maximal distinct subarrays overlap.

Distinct Values Subarrays problem on CSES: https://cses.fi/problemset/task/3420/

My solution program: https://cses.fi/paste/10b865ef59bbe20ef6257a/

Here's another solution program that is only different in the way it computes the combinations: https://cses.fi/paste/10b865ef59bbe20ef6257a/

Distinct Values Subsequences

problem

observations

The number of non-empty subsequences of an array of length n is 2ⁿ - 1. If each number in the array appears once, then this is the answer.

The order of the numbers in the array does not affect the count, just the number frequencies.

Why is observation one true: each number can either appear or not appear, and the empty set is not counted, so (1 + 1)...(1 + 1) - 1 = 2ⁿ - 1. Each number contributes a term of (1 + 1): the first one is absence, while the second one is incidence.

But what if a number occurs more than once? A subsequence can either not have a number or have just one instance of it. That "choice" is easily expressed as a trivial combination: (frequency of number choose 1) = frequency of number. The expression for the general answer is (1 + frequency of first number)(1 + frequency of second number)...(1 + frequency of last number) - 1.

You could feasibly compute this expression directly mod 1e⁹+7, but there is a cooler incremental, indirect computation.

solution

#include<iostream>

#include<unordered_map>

using namespace std;

long long binpow(long long a, long long b, long long m) {

    a %= m;

    long long res = 1;

    while (b > 0) {

        if (b & 1)

            res = res * a % m;

        a = a * a % m;

        b >>= 1;

    }

    return res;

}

int main() {

        const long long MOD = 1000000007;

        int n;

        cin >> n;

        unordered_map<int, int> freq;

        long long count = 1;

        for (int i = 0;i < n;++i) {

                int x; 

                cin >> x;

                count = count + (count * binpow(freq[x] + 1, MOD - 2, MOD) % MOD) % MOD;

                ++freq[x];

        }

        count = count - 1 % MOD;

        cout << count << endl;

}

Distinct Values Subarrays

problem

observations

1. The number of subarrays of an array of length n is n(n + 1)/2. If each number in the array appears once, then this is the answer.

2. What if you find a covering of the array into disjoint segments each with distinct numbers, e.g. [1, 2, 3, 1] becomes [1, 2, 3], [1]. Can you apply the formula independently to the segments and sum the results? No, this fails to count segments that cross the split and would underestimate the correct answer. Also, such a covering might not be unique.

3. What if you forego disjoint-ness and expand the segments as much as possible while keeping the numbers distinct: [1, 2, 3, 1] becomes [1, 2, 3], [2, 3, 1]. This covering is unique, but now you overestimate the correct answer because the segments overlap. , that the amount of overshoot is equal to the number of subarrays of [2, 3]. A nice expression for the correct number of subarrays follows from this observation resembling the inclusion-exclusion principle formula.

4. If x₁, ..., x_k are distinct, but x₁, ..., x_k, x_k+1 are not distinct, then one of the numbers in x₁, ..., x_k is x_k+1. If x_j = x_k+1 with 1 ≤ j ≤ k, then x_j+1, ..., x_k+1 is distinct. This means that storing the index of incidence for each number in x₁, ..., x_k is enough to find out the start of the second segment in the construction from observation three.

solution

You can compute the expression from observation three in a sliding window fashion by exploiting the structure from observation four.

two problems

Codeforces Round 1011 (Div. 2) Problem C

Solution: x + y = x xor y as long as the addition involves no carries, i.e. the bits that are set in a should be disjoint from the ones in b. Multiples of powers of two are always disjoint from numbers less than that power of two. if x ≠ y, then without loss of generality, one of x and y will be bigger than the other, so choose the k that makes the the bigger one a power of two. If the numbers x and y given are equal to each other, then (x + k) + (y + k) ≠ (x + k) xor (y + k) for all non-negative numbers k (unless x = y = 0).

Building Roads

Solution: This is basically just a connected components problem. Once you identify the connected components, connect them minimally with # components - 1 edges: connect one vertex in each connected component to one vertex in a single chosen component of your choice. Here's my union find solution. You could also identify and connect the components using a depth first search and no union find structure, but then you need to store the adjacency matrix.