New answers tagged

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