Questions tagged [counting]

The term Counting in Computer Science is usually used to refer counting objects in certain arrangements or with certain properties.

Filter by
Sorted by
Tagged with
3
votes
0answers
91 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
414 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
59 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
21 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
42 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
62 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
481 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
136 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
71 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. ...
3
votes
1answer
796 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
60 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
43 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
259 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
64 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
1k 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
140 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
297 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
101 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
357 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 ...
4
votes
1answer
407 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
218 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
640 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
78 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
165 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
1k 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
218 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
162 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
65 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 ...
9
votes
2answers
936 views

Counting islands in Boolean matrices

Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
0
votes
0answers
35 views

Number of possible balanced binary trees [duplicate]

A tree is balanced if the subtrees of each node differ in height by at most one. How many balanced binary trees can we create from $n$ nodes?
0
votes
0answers
164 views

Finding all possible bottom-most overlapping rectangles on a table

Let's say that I'm given a $n\times n$ ($n\leq 1000$) grid (more of like a table) and I color the grid with $n^2$ rectangles, each of a different color (let's say they have colors 1 to $n^2$ for ...
2
votes
0answers
400 views

Estimating size of state space search problem

Im currently enrolled in an AI course and we are starting with state space search problems. My professor always seems to ask, given a certain problem, what is the estimate size of the state space? It'...
5
votes
0answers
624 views

Sorting in place & stable in linear time

Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics- The algorithm runs in $O(n)$ time. The algorithm is stable. The algorithm sorts ...
5
votes
2answers
922 views

Counting substrings with a given number of different characters in O(N)

Given a string $S$ of length $n$, and a number $k$, count the number of substrings (regardless of their length) that contain exactly $k$ different characters. The obvious solution takes $O(n^2)$ time ...
2
votes
1answer
316 views

Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph

Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave ...
0
votes
1answer
61 views

Finding alternative way of combinatorial counting

The question is related to databases: There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are? I thought if any one of the $(n-...
1
vote
0answers
98 views

What are widely-used, practical applications to come from the study #P problems?

When, beyond theoretical exercises, do we care how many solutions we can find for something? I had an analogous question for TMs before - why is it useful to study machines that can only deliver ...
2
votes
1answer
117 views

Computing counts of combinations (?)

I'm not sure what terminology to use. Here is some input: John has items: A B D Peter has items: A C D And I want to produce such a table, that would count the #...
8
votes
3answers
2k views

Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
1
vote
0answers
80 views

Count all possible 2-3-monotone sequences

Let $N \leq 1000$, a 2-3-monotone sequence $s$ of length $N$ is defined as: $s_i < s_{i+2}$, for $1 \leq i \leq N-2$ $s_i < s_{i+3}$, for $1 \leq i \leq N-3$ $s_i \in \{1,\dots, N\}$ Given $N$...
1
vote
3answers
60 views

Count elements in the real world in constant time by weighing them

I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out ...
-1
votes
1answer
984 views

DFS for all possible walks from a source to a destination with exactly k edges

Problem Statement: Given a directed graph and two vertices ‘u’ and ‘v’ in it, count all possible walks from ‘u’ to ‘v’ with exactly k edges on the walk. My question is that, say we have a DAG (...
-2
votes
2answers
662 views

Count all numbers up to X that are divisible by at least two of their digits

I want to count how may numbers are there in range [1,X] which are divisible by at least two of their digits, different and >1. I found a sequence on OEIS, but this will take lot of time to generate ...
2
votes
1answer
71 views

Counting specific subgraphs

For a given undirected graph G, I want to count all the subgraphs H that satisfies the following conditions: H.V = G.V (The subgraph will containt all the original graph nodes) H is connected (Note: ...
0
votes
0answers
33 views

Complexity of Self avoiding walks in unary

In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and ...
3
votes
1answer
5k views

How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
29
votes
5answers
5k views

Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding ...
3
votes
1answer
119 views

Number of states in an AND-OR DAG

Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
14
votes
1answer
488 views

Why is the counting variant of a hard decision problem not automatically hard?

It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a ...