Questions tagged [counting]
The term Counting in Computer Science is usually used to refer counting objects in certain arrangements or with certain properties.
0
votes
0answers
18 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} (...
1
vote
0answers
12 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$?
1
vote
0answers
28 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
18 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
10 views
Counting rectangles in one big histogram
Let's say we have given array of $N$ integers which actually represent the height of a histogram, now for each rectangle with lower side at the base of the histogram we need to count how many elements ...
0
votes
0answers
19 views
Given graph with N nodes colored in K colors, count paths visiting each color exactly once
Let's say we have given graph of at most $N = 400$ nodes, and each node is colored in one of $K = 21$ colors. We need to count paths of length $K$, such that each node on the path is in one of the $K$ ...
0
votes
0answers
27 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
86 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
63 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
68 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
27 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
37 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
64 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
65 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
65 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
45 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
48 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
41 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
75 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
29 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
61 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
122 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
30 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
25 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
16 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 ...
0
votes
0answers
28 views
Applications of counting queries
Following the paper on AD-Trees (a data structure to answer counting queries efficiently).
The paper discussed the applications of such a data structure to useful for machine learning methods such as ...
3
votes
1answer
22 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
45 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
183 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
84 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
47 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
481 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
51 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 ...
1
vote
0answers
25 views
Approximate count per element in list/stream via Counting Bloom+Morris
I've a large list A of elements. Given another list B of elements, I need B to be sorted by ...
0
votes
1answer
122 views
Sorting an array in linear time
I need to find a method to sort an array in $O(n)$ time complexity.
I saw this link,
however I'm not sure how to apply it to the elements I need.
Input: an array $A$ of length $n$, containing ...
2
votes
1answer
54 views
On lowness of $\oplus P$
$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$).
Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$?
Are there complexity classes $\mathcal C$ ...
2
votes
1answer
585 views
How to count all contiguous subsequences with positive sum?
I have array $t$ with size $n \leq 10^6$. It has only two kinds of elements inside: $1$ or $-1$.
I need to count how many contiguous subsequences have positive sum.
This pseudocode demonstrates ...
5
votes
0answers
115 views
Count Wildcard Parenthesizations of a String
Let $\Sigma = \{ (, ), ? \}$ be an alphabet. For a given string $s \in \Sigma^*$, we denote by $f(s)$ the number of ways to replace each symbol $?$ either with $($ or with $)$ such that $s$ is ...
0
votes
1answer
185 views
Using Pascal's Triangle to implement queues and stacks using heaps
I have the following question as homework in an algorithms, analysis and data structures class:
And here's an answer I wrote up:
A queue is a first-in-first-out data structure. A heap is a data ...
2
votes
1answer
52 views
Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT
A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:
There exist a clause where all variables are unsatisfied.
Unfixing any variable make every clause contain at least ...
-2
votes
1answer
148 views
How to use Bitmasking to solve this problem?
http://codeforces.com/problemset/problem/535/B
The problem is:
You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 ...
2
votes
1answer
280 views
Can counting problems have optimal substructure?
I understand that for a problem to be solvable using dynamic programming, it needs to have the following properties:
optimal substructure
overlapping subproblems
I stumbled upon an article which ...
3
votes
1answer
147 views
How many different trees can we form from given graph?
I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$
In this graph I want to count the sub-...
1
vote
3answers
283 views
Are counting problems the same as problems involving listing all possible combinations?
I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of ...
0
votes
1answer
47 views
What's wrong with this [closed]
Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count).
I then write this code down:
table = new SimpleTable("baby-...
2
votes
3answers
139 views
Count arrays with size n, sum k and largest element m
I'm trying to solve pretty complex problem with combinatorics.
Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K ...
7
votes
2answers
685 views
Count of distinct substrings in string inside range
Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ ...
0
votes
1answer
169 views
How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions
How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:
no or minimal redundancy
only use 1 integer variable or k independent integer variables with a ...
0
votes
1answer
85 views
Proving $\#CYCLE \in \#P$
I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.
I saw this question:
...
-1
votes
1answer
51 views
Display Counting Algorithm
I am writing some firmware for a display that will take measurements and present them in real time on an LCD screen. I would like for the measurements to display as smoothly as possible... What I mean ...
