All Questions
58
questions
1
vote
1
answer
74
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
- 129
0
votes
1
answer
27
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
1
answer
52
views
Find Number of unique durations that can be created given a list of durations and an upper bound [closed]
Lets say we are given a list of durations (5s, 10s, 10s, 15s, 15s, 15s, 25s, 30s....) and we want to find a list of unique durations that can be created using this list of single durations.
for ...
0
votes
0
answers
21
views
Filtering out faulty durations
I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2:...
5
votes
1
answer
153
views
What are the chances that the Enemy/Defender game has a stable solution?
There is a game called Enemy/Defender that you might play with kids. The setup is as follows:
Everyone stands in a circle. You say, "Look around the circle and select someone (at random) to be ...
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,019
1
vote
2
answers
71
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 271
0
votes
0
answers
32
views
Effectively solve optimization problem in this system?
The system :
Given
$2$ sets $I,J$ such that $I\cap J = \emptyset , \#I = \#J$
a time-dependent function $c : \mathbb{R}_{\ge 0} \times I \times J \to \mathbb{R}_{\ge 0}$ .
Consider a system that ...
- 910
1
vote
0
answers
73
views
How to quickly eyeball maximum sum subarray?
Given an integer array, I want to find the continuous subarray (containing at least one number) which has the largest sum. There are some algorithmic solutions to this here: https://en.wikipedia.org/...
- 1,415
0
votes
0
answers
68
views
Finding the general formula for the last standing soldier
Suppose there are 'n' soldiers standing in a circle who have decided to kill each other (just because they don't want to surrender to the opposition).
Lets say they are denoted from a1 to an in the ...
- 1
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
3
votes
2
answers
1k
views
Why do greedy coloring algorithms mess up?
It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
- 731
0
votes
1
answer
63
views
Determining all possible values of $n$ in terms of $x$ of the following tree.
Let $T$ be a maximal heap tree. Let $T$ hold the integers $1$ to $n$ as its nodes without duplicates. Let $x$ be a child of the root. What are the possible values that $n$ could take, in terms of $x$?
...
- 1
0
votes
0
answers
67
views
Greedy algorithm for variation of bin packing
Consider the bin packing problem where an input array of weights have to be packed in the minimum number of bins possible. Consider the two following restrictions. First, for any bin, a heavier weight ...
- 127
1
vote
1
answer
637
views
Change making problem - Pearson algorithm to check the optimality of greedy solution
This is a question regarding the common version of the Change making problem, which is:
"how can a given amount of money be made with the least number of coins of given denominations (we have ...
- 113
0
votes
1
answer
135
views
General interval scheduling
We shall start with below problem.
Problem: Given a list of classes for student to subscribe for a week:
Math: Monday 1pm-3pm; Wednesday 4pm-6pm
(That means Math class learn from 1pm to 3pm on Monday ...
- 55
0
votes
1
answer
44
views
Proof of greedy algorithm.
Given n numbers find the way to assign them to blocks of 3 (and possible one block of 1 or 2 if n is not divisible by 3) so that sum of smallest elements from each full block is maximal.
ie.
numbers ...
- 101
1
vote
1
answer
770
views
Sorting an array using reverse
I ran into an Olympiad question recently, and one challenging question surprised me:
We have an array $A$ with $n$ elements. $\operatorname{Rev}(i, j)$ for $1 \leq i < j \leq n$ reverses subarray $...
6
votes
2
answers
214
views
a semi-hard problem on combinatory
I ran into a nice interview question.
the problem is as follows:
We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of ...
user871754
0
votes
1
answer
84
views
Optimal planning for mail box servicing and processing (for a message queue online consumer scheduling)
Consider I have $n$ mail boxes $\{m_1, m_2, \dots, m_n \}$. Messages come to each box at different rate/sec e.g., mail box $n$ has an arrival rate of messages equal say 5 per second. In general, let ...
- 131
1
vote
1
answer
247
views
parenthesis of expression in such a way value not changed
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
- 119
6
votes
4
answers
3k
views
What's the number of decibinary numbers that evaluate to given decimal number?
Let's define a decibinary number system, where each bit (or digit) can range from $0$ to $9$, but it's place value corresponds to the one in the binary system. For example:
$$(2020)_{decibinary} = 2 \...
1
vote
1
answer
54
views
Minimize the sum of components of a hypercube under a system of $0,1$ equations.
Let $x_1, \dots, x_5, y_1, \dots, y_4$ be a total of nine variables taking values merely in $\{0, 1\} \subset \Bbb{Z}$. Therefore a solution is a point on a hypercube.
These are the constraint ...
1
vote
2
answers
1k
views
How many essentially different strings are there of length $\leq n$ and over an alphabet of size $|\Sigma| = m$?
For example, $aaaaaabb \simeq ccccccdd$ essentially, because a smallest grammar algorithm would perform the exact same steps to reduce one as the other. So how can I phrase this in terms of formal ...
2
votes
1
answer
76
views
Building a sequence that approximates given sequences
Suppose that we are given three sequences $a1,a2$ and $a3$ each describing a total ordering on $N$ 'entities'. For example,
$$\langle a1\rangle=1<9<8<2<3<\cdots<N $$
means that ...
- 368
1
vote
1
answer
133
views
Rearranging a given sequence to satisfy order constraints on certain members
Suppose that we are given a sequences of $2N$ 'entities' (not numbers) with some total ordering defined among these entities. An example could be
$$\langle a\rangle=1<4<8<2<3<\cdots<...
- 368
0
votes
0
answers
225
views
How to generate all graphs on $n$ vertices including a given subgraph?
I'm working on a graph theory problem and as an intermediate step I need to draw all the simple graphs on $n$ vertices including a given subgraph, is there an algorithm to make sure I can generate all ...
- 29
2
votes
0
answers
135
views
Clearing all levels with minimum coins [closed]
Thor is playing a game where there are N levels and M types of available weapons. The levels are numbered from 0 to N-1 and the weapons are numbered from 0 to M-1 . He can clear these levels in any ...
- 29
1
vote
2
answers
446
views
Question in proving a recurrence relation for Catalan numbers [closed]
How to prove the recurrence relation for Catalan numbers, stating
$$C_{n}=\sum_{i=0}^{n-1}C_{i}C_{n-1-i}$$
where we define $C_{0}$ as $1$?
- 119
1
vote
0
answers
160
views
How would you prove that a dynamic programming problem is solvable by a greedy algorithm?
I have solved a few optimizations problems using dynamic programming, but some of those problems are also solvable by Greedy algorithms which are computationally more efficient to calculate.
For ...
- 1,035
3
votes
0
answers
72
views
Dividing class into groups
Just a question I have been pondering.
Assume you have a class of 100 students, each student chooses 3 friends. The goal is to split them into 4 groups of 25.
We define 'satisfaction level of ...
- 193
0
votes
1
answer
108
views
How to make the subset sums of a given array of numbers, even.
I'm not sure if I've been able to clearly state my problem here, but here's the extensive problem description:
We have an array of $n$ numbers, and another given number $d$, one step at a time, we ...
- 617
1
vote
0
answers
72
views
Learning about Proofs and how to write them? (A programmer's perspective)
I have a B.S. Degree in computer science and have taken more math classes then the average person but not enough to consider myself good at it. I have been briefly introduced to proofs.
I'm currently ...
- 111
0
votes
2
answers
167
views
How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$?
How many unique sums $x_0+x_1+x_2+\cdots+x_n=S$ where $x_i>x_{i-1}$ are there for each $S$?
$x_i$ and $S$ are non-negative integers.
My Computer Science prof also said that this can be solved ...
- 181
1
vote
1
answer
66
views
Find least number of radial-subgraph of a graph
Background:
Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader?
...
- 19
1
vote
0
answers
185
views
Determine Huffman Tree Depth Using any combinactory ways?
I see this link for determining depth (height) of Huffman tree, but not useful for me.
My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
1
vote
1
answer
93
views
Load balance N customers over K servers with different capacities
Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
- 111
1
vote
3
answers
509
views
Isomorphism of Non-Symmetric Matrices
$A, B$ are non-symmetric matrices of dimension $m \times n$ where $m=n$ or $m \neq n$.
Example: An example of $6 \times 3$ non-symmetric matrix is
$$
\begin{pmatrix}
1 & 0 & 0 \\
0 & ...
- 499
1
vote
0
answers
25
views
Finding objects from a list with some properties in $O(n)$
Lets say I have $2$ strings each having $4$ characters.
$k$ is a number $\le 4$.
If, $2$ strings have exactly $k$ common characters lets say they are a "happy pair" with $k$ points.
If I have $n$ ...
- 275
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
2
votes
1
answer
40
views
Finding the size of sumsets in limited space
Let $S=\{a+b:\ a\in A,\ b\in B\}$. I have an explicit representation of $A$ and $B$, but $S$ is too large to store in memory. (For the sake of argument, say $A$ and $B$ are 100 MB and $S$ is 1000 TB.) ...
- 32.3k
3
votes
1
answer
2k
views
what' is the number of full subtrees of a full binary tree?
I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are:
Now my question is:
What is $N(h)$ the maximum number of full sub-trees of a full ...
- 13.8k
3
votes
1
answer
205
views
Traveling salesman neighborhood
I am solving some TSP problems and i got this one and i am not pretty sure about my answer.
By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
- 14.7k
2
votes
1
answer
619
views
Counting the number of complete bipartite subgraphs
I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
- 22.5k
2
votes
0
answers
71
views
Finding whether a sum of numbers in a set generate another number
I have a set of numbers $\{a_1,\dots,a_n\}$ and another number $k$. I need to find whether sum of any combination of numbers in the set produces $k$. It can be $a_1 + a_2$ or $a_1 + a_2 + a_3 + a_7$. ...
- 121
0
votes
1
answer
67
views
looking for hypergraph decompositions
there are many thms for/types of graph decompositions. in contrast,
am looking for various types of hypergraph decompositions...?
also esp interested in graph analogs that translate somehow eg say ...
- 844
0
votes
1
answer
239
views
Constrained disjoint subsets
How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that $...
- 298
2
votes
1
answer
303
views
Combinatorics/Task Dependency
Here is a competitive programming question:
You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
2
votes
1
answer
658
views
Finding the shortest/"most negative" closed directed trail in a weighted digraph with negative weights
I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
- 8,000