94

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 #...


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

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

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 ...


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 depends on what you mean by "count to infinity". Specifically, how does the computer give output? consider the following quesitons: Can a computer show, on its screen, all the number from 1 till (infinity): increasing the number on screen by 1 every second? Can a computer send on the network line, a package that contains a number starting with 1, and ...


3

What you are trying to do is correct. However only number of rotations will not be able to tell you anything about the inversions. The whole procedure is as follows. You start with an empty red-black tree. Then you insert the elements in the given sequence one by one, in the order that they occur in the sequence. Whenever an element $x$ in the sequence ...


3

It's also easy to do with a Rabin-Karp-type hash: https://en.wikipedia.org/wiki/Rolling_hash, which you can use to check equality of any two substrings in $O(1)$ time, albeit with a probability of error. This probability can be made negligible and works very well in practice. I prefer the above-suggested "Z-Algorithm" solution because it's deterministic, ...


3

Total number of distinct transition functions from $Q \times \Sigma \rightarrow Q$ is $3^6 = 729$. This is because $Q \times \Sigma $ has $|Q| \times |\Sigma| = 3 \times 2 = 6$ elements, and $|Q| = 3$. Every one of $6$ elements has $3$ choice for transition. Even if there are 3 different choice of start state, that will not give us different automata, as ...


3

Your problem is equivalent to counting the number of satisfying assignments for a monotone Boolean circuit. The restricted version in which the circuit is of the form $(x_{i_1} \lor x_{j_1}) \land \cdots \land (x_{i_m} \lor x_{j_m})$ (where indices can repeat) is known as #Monotone-2SAT and is known to be #P-complete. This means that there is probably no ...


3

In simple words: Search for X gives you n answers. Search for Y gives you m answers. Search for X AND Y gives you p answers. In searching for X OR Y, the search breaks off as soon as it finds either X or Y. So if there's an X before a Y, that Y will not be counted in searching for X OR Y. Therefore your search for X OR Y will give you n + m - p answers. ...


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