# Tag Info

## New answers tagged sets

0

If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$. Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order. In that case you have just: $\begin{equation*} P = c \cdot \prod_{1 \le k \... 0 There is no general way to answer such a question other than to repeat the definition. So one might answer for example for$1$: The equivalence class that$1$belongs to is the set of all integers$n$such that$1 + n \equiv 0 \mod 2$. You might simplify this by noting that$1 + n \equiv 0$implies$n \equiv 2-1$or$n \equiv 1$modulo$2$, giving: ... 2 I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed. Indices You can build up an index for each word. Build a hash table. For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word. This ... 0 No, not$O(n)$. Suppose$0.9n$are nested and$0.1n$are not nested (and are unrelated). Then there can be at least$2^{0.1n}$different pieces, which is not$O(n)$. You can find the nesting structure in$O(n^2)$time by testing all pairs of sets to see which are subsets of the other. 1 The proof is by induction. The base case$t = k$is clear. Suppose that the claim is true at some time$t$. We will prove it for time$t+1$. Let the first$t+1$elements be$x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time$t$each of the$\binom{t}{k}$possible$k$-subsets of$x_1,\ldots,x_t\$ is found in the array with equal probability. The ...

Top 50 recent answers are included