Questions tagged [counting]
The term Counting in Computer Science is usually used to refer counting objects in certain arrangements or with certain properties.
132
questions
3
votes
1answer
18 views
Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.
I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]...
0
votes
0answers
45 views
Counting number of apples in an apple tree with given number of layers
This problem comes from a competitive programming question, and it seems to require dynamic programming.
There are several layers of apples arranged in a formation with each apple having a value ...
0
votes
0answers
14 views
Calculating Time Complexity of Algorithm Using Incrementor Variable [duplicate]
I am trying to calculate the time complexity of an algorithm using n in the code below.
I have a working solution to a coding challenge to sort a stack using only ...
2
votes
1answer
54 views
Number of ways painting graph in two colors, such that two nodes of same color are linked by edge
We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
1
vote
2answers
88 views
Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems
I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an ...
2
votes
1answer
38 views
Estimation of the number of solutions by Counting
This is a question from a quantum computation textbook.
Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
1
vote
1answer
68 views
How to find the Big-O for finding combinations of balanced parentheses?
Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be:
...
2
votes
2answers
58 views
Prove that this language is NP-Hard
Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$
prove that $\mathrm{\#3SAT}$ is NP-Hard.
I am currently stuck with ...
3
votes
1answer
43 views
Why does not valiant's reduction show NP=RP?
Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$.
We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in ...
1
vote
1answer
333 views
How many ways to express N as sum of 2, 3 and 5?
I've learnt about problems about express N as sum of 2, 3, 5. For examples, if N = 7:
N = 5 + 2
N = 2 + 5
N = 2 + 2 + 3
N = 2 + 3 + 2
N = 3 + 2 + 2
But most of I found on the Internet that the ...
3
votes
1answer
43 views
The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$
where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
1answer
218 views
Limitations of DFA [duplicate]
In this link it is mentioned:
A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.
But counting is not enough -- consider a language of ...
0
votes
1answer
53 views
Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
0
votes
0answers
11 views
List maximum number of three-sets
Suppose i'm given with pairs component-quantity. I need to list maximum number of possible three-sets.
{AA}, {BB}, {C}, {D} => {ABC},{ABD}.
To list two-sets ...
0
votes
1answer
25 views
Can someone give me the definition of #Monotone-2SAT?
In the decision problem, I set all variables to true and see if the formula is satisfiable.
My question is because I do not understand how there can be multiple solutions, though all variables are ...
1
vote
1answer
91 views
Find total count of all paths starting from a fixed vertex to all other vertexes of the graph
Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.
$$
\text{#(paths from 1 to 2)}+\text{#(...
2
votes
0answers
105 views
Min no.of operations required to convert an array to which it should contain elements of equal frequency
I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
1
vote
1answer
23 views
Is there an FPRAS for the number of min st cuts in general graphs?
Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get ...
1
vote
0answers
33 views
Count paths in matrix that visit each number exactly once [duplicate]
Let's say we are given matrix of size $N \leq 21 \text{ by } M \leq 21$ each element of the matrix is either $-1$ or number in the interval $[0, 20]$.
We want to count the number of paths that start ...
2
votes
2answers
247 views
Count-min sketch
I don't understand the use case of count min sketch.
Based on Count–min sketch, it says "serves as a frequency table of events in a stream of data.".
If I know there are N types of events, why can't ...
0
votes
0answers
25 views
Find xor sum of all pairs raised to power of 3
We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
3
votes
0answers
36 views
Does $P=PP$ or $P=PSPACE$ have consequences for algebraic class problem $VP=VNP$?
Deciding majority of counting problem is $PP$ class.
Is there any relation between $PP$ and $VNP$ and is there consequence of $P=PP$ or $P=PSPACE$ to $VP=VNP$?
Is there a way to show $\#P$ is in $FP^...
1
vote
0answers
33 views
Counting on a matrix
I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.
If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
1
vote
1answer
37 views
Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it
Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the ...
0
votes
0answers
39 views
Count submatrices with only zeros for each element of the matrix
Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...
4
votes
3answers
153 views
Sum of unique elements in all sub-arrays of an array
Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.
Subarrays:
...
3
votes
2answers
73 views
Count numbers less than $x$ co-prime to $p$
We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.
I know that we can solve the problem in $O(x\log x)$ with iterating over all ...
2
votes
1answer
283 views
How to find all topological sortings of a special DAG in O(N^2)
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.
https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum
...
2
votes
1answer
35 views
Count number of the ways to fill a N-lengthed binary string
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
0answers
71 views
Counting subarrays where each number either doesn't occur or occurs odd number of times
We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times.
...
0
votes
2answers
65 views
Why it is not $O(m)$ but $O(\log m)$?
I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.
Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.
...
0
votes
2answers
99 views
Defining decision-problem complexity classes by counting branches of a polynomial-time NTM
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) ...
0
votes
1answer
147 views
Can I make last part of counting sort become to be starting from lowest index?
Counting sort is originally like below code.
...
0
votes
1answer
97 views
How to count number of 1s of the first k positions in a bitset (bitmap)?
Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.
Output: the total number of 1s in the first $k$ position of $b$.
Obviously it can be done in $...
-1
votes
1answer
71 views
Counting (enumerating) minimal solutions of a dual horn formula
Is there an efficient algorithm ("does not necessarily have to be a polynomial time algorithm") to compute all "minimal" solutions for a Dual Horn formula (conjunction of clauses where each clause ...
0
votes
1answer
53 views
On FPTAS and many one parsimonious reductions
We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.
If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an ...
1
vote
1answer
144 views
Counting solutions of a particular type in HORN SAT
I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same.
Suppose we have a HORN SAT -: $(x_1) \land (x_2 \implies x_1)$, ...
0
votes
1answer
69 views
Modified Counting Inversions problem using divide and conquer
Given an array $A$, find the number of pairs $(i, j)$, such that $ i > j$ and $A[i] \ge A[j]$.
This is a modified version of the famous problem of Counting Inversions, only in this version it ...
3
votes
0answers
86 views
How hard is APPROXIMATE-#SAT? [closed]
It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete.
It is also suspected (somewhat less widely) that even deciding SAT should ...
3
votes
1answer
288 views
Find smallest enclosing circle
On a 2d plane, there is a large circle centered at $(0, 0)$ with a radius of $R_{{o}}$. It encloses $\sim 100$ or so smaller circles distributed randomly across the parent circle otherwise with known ...
3
votes
0answers
31 views
Number of distinct single-assignment forms with $j$ binary function calls?
Given $n$ inputs and $k$ outputs and $j$ identical binary function calls to $g$, how many possible distinct single-assignment forms are there?
The only assumption made about $g$ is that if $a = c \...
1
vote
0answers
50 views
Is there a simple way to construct a Boolean formula that is true if and only if at most $k$ of the input variables are true? [duplicate]
I could of course construct a truth table for the function
$$f(x) = \left(\sum_i x_i\right) \leq k$$
Where $x$ is an assignment and I'm slightly abusing notation to count Booleans. And then I could ...
-1
votes
1answer
20 views
Count points on same distance from set of points
Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
2
votes
1answer
33 views
Counting number of permutations respecting partial order
Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ ...
0
votes
1answer
57 views
Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?
I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
1
vote
3answers
319 views
How many 3-SAT expressions with up to N variables are satisfiable?
TL;DR
There are exactly 255 possible 3-sat expressions with exactly 3 variables (more meticulously defined below). Of those, exactly 254 are satisfiable. There are exactly 4,294,967,295 possible 3-...
1
vote
2answers
112 views
Count numbers less than $K$ in array
Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and ...
2
votes
1answer
62 views
Proving or disproving a set of total functions is countable
Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for
all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. ...
2
votes
1answer
669 views
Radix, merge, counting sort and when to use
Okay can't figure this out. I want to make sure I understand it.
There are n random keys each being float numbers with p decimal places.
So, for example,
123.456,
343.645,
234.543,
863.238,
956....
0
votes
1answer
57 views
Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays
$k = \Theta(n)$
The arrays consist only natural numbers $1$ to $n$
The sum of the length of all arrays = $\Theta(n)$
It should return the $k$ original arrays, each sorted on its own.
The running ...
