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 $...
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$ ...
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 ...
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 ...
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 ...
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 ...
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/...
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 ...
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 $...
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 ...
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$?
...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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<...
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 ...
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 ...
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$?