93

The counting principle that applies here is inclusion-exclusion. $$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$ To make the numbers work out, $\left|X \cap Y \right|$ must be 10000. A Venn diagram may be more convincing to someone who may be intimidated by the notation.


62

Hint: The search x AND y will result in 10 000 hits.


15

The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard". A decision problem is hard if it's NP-complete under polynomial-time many-one reductions (a.k.a. Karp reductions, a.k.a. polynomial-time mapping reductions). A counting problem is hard if it's #P-...


13

Document 1: The cat is on the table Document 2: My cat is black Document 3: The dog is under the table Document 4: What's the name of your cat? Document 5: This is a black and white photo Search for cat: returned documents are 1,2,4 (3 documents returned) Search for black: returned documents are ... Search for cat OR black: returned documents are ... :-D :...


9

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.) Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #...


8

"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope. This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok &...


7

This can be solved in $\mathcal{O}(n \log n)$ by using the smaller-to-larger merging technique. Root the tree at an arbitrary vertex. We will calculate for every subtree an array where the $d$th position indicates the number of nodes at depth $d$ in the subtree. Of course, the total size of these arrays could be $\mathcal{O}(n^{2})$, so we will not store ...


6

For a grid in the range of $[n_1,n_2]$, according to the problem statment, the number of edges is: $$\#edges=\frac{8 \times (n_2-n_1+1)^2- 4\times 5-4\times3\times(n_2-n_1-1)}{2}$$ explanation: suppose every node has a degree of 8, then sum of the degrees is $8\times(n_2-n_1+1)^2$; For each corner we included 5 extra edges that must be removed (the term $4\...


6

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem. Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they ...


5

IEEE floating point format has a sign bit, an 11 bit exponent (ranging from -1022 to 1023) and a 52-bit mantissa with an implicit "1" in the 53rd bit. Thus, the largest integer that can be represented without rounding is the binary number with 53 "1"s, $2^{53}-1$ = 9,007,199,254,740,991 ~ 9e15 < 1e16. After that you start having to round off low order ...


5

As Yuval noted, you can count the number of acyclic orientations by evaluating the chromatic polynomial of a graph at negative unity. For computing chromatic polynomials, there are efficient algorithms known for some graph classes. There is also a recursive algorithm for generating all acyclic orientations of a graph given by Squire [1]. The algorithm ...


5

You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward. Let $S$ be the string. We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to count the number of substrings that start at position $i$. For each $i$, find the smallest $j_\text{min} \ge i$ such that $S[i..j_\text{min}]$ has exactly $k$ ...


5

There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those floor ((x-1) / p) are divisible by p, so exactly (x-1) - floor ((x-1) / p) are co-prime with p. For simplicity, let f(n) = floor ((x - 1) / n), then for a prime ...


5

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case). Consider ...


4

I assume that a binary tree is given by the following specification: a binary tree is either (a) empty or (b) is composed of a root and two (ordered) subtrees. I also assume that height is defined so that a complete binary tree of height $h$ has $2^{h+1}-1$ nodes (for example, a single node has height $0$). Let $A_h$ be the number of binary trees with ...


4

Assuming that you are trying to maximize the seating preferences, this problem is NP-Hard =(. NP-Hardness Specifically, consider the decision version of this problem: Given a matrix of preferences, is there some way to assign people to seats such that the total score (sum of resulting preferences of professors to their nearby neighbors) obtained is at or ...


4

Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will simply be the count of indices $i$ such that $Z[i] >= i$, assuming 0-indexing. Fortunately, such an algorithm exists and is quite elegant! It's (as always) a ...


4

Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory. The number of connected spanning subgraphs of a graph $G$ equals $T_G(1,2)$, where $T_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence ...


4

Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual complexity is $O(\min(m, n))$ memory. Processing time is $O(mn)$. Initialization. Scan over the first row and find all connected substrings of that row. Assign each ...


4

This is a textbook application of radix sort. Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$. The same approach works for numbers up to $n^...


4

Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode count = new int[C] (array of integers) for every a[i] in a count[a[i]]++ for i = 1, i < C, i++ count[i] += count[i-1] To Answer a query for a given k you just return count[k - 1]


4

Copied from here. The mathematics Consider the group $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices. Each matrix is a function ...


4

As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time and, thus, does not qualify as a polynomial-time reduction (which is the standard notion used to compare the classes in question). Exponential-time reductions ...


4

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite. You only need to find an injection from your set and $\mathbb{N}$, it means that you can identify each element of your set using a natural number (a code if you prefer). For instance you can code the set of functions from $\{a,b\}$ to $\mathbb{...


3

A recurring application for SAT model counting in the literature is extracting predictions from Bayesian networks. See "Algorithms and Complexity Results for #SAT and Bayesian Inference" and "On probabilistic inference by weighted model counting".


3

$\mathrm{W}[1]$-hardness implies that a problem has no eptas unless (at least) $\mathrm{W}[1] = \mathrm{FPT}$ (having an eptas implies parameterized tractability for the standard solution size parameterization), but there are problems with a ptas that are $\mathrm{W}[1]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$). Transferring ...


3

Adding another example I came across, with an even stronger result: A (deterministic) FPTAS exists for the problem of counting the number of matchings in a bounded-degree bipartite graph, while this is a $\#P$-complete problem.


3

Let's collect what facts we can determine: The sum of all counters $S$ will change by $T-P$ with each cycle of $T$ steps, where $P$ is the number of positive counters at the final step of the cycle. If you end a cycle with $P=T-1$, you have $S\le(T-1)(M-1)$. During the following cyle you can reach $S=(T-1)M$ after $T-1$ steps, but in the next step you will ...


3

Often, in order to improve a sorting-based algorithm from $O(n\log n)$ to $O(n)$, one can use hash tables. In this case, you would use a hash table of size $O(n)$. Each entry of the hash table would store an integer and its count. The entire algorithm would now run in expected time $O(n)$.


3

It all boils down to simulating a $\mathsf{\# P}$ oracle using a $\mathsf{PP}$ oracle. Consider a $\mathsf{\# P}$ oracle call: a polytime non-deterministic Turing machine $T$ and an input $x$. We want to know how many runs of $T$ result in the output $1$. Denote this number by $T_1(x)$, and denote the total number of runs of $T$ on $x$ by $T(x)$. First, let'...


Only top voted, non community-wiki answers of a minimum length are eligible