All Questions
70
questions
18
votes
4
answers
7k
views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{...
- 484
12
votes
1
answer
831
views
Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM
Question:
Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$)
More precisely, for $n \in \mathbb{N}$, we can a find ...
- 2,624
12
votes
1
answer
331
views
Searching radioactive balls
There are $n$ balls, and $m$ of them are radioactive. You can test any set of balls and find out whether there is at least one radioactive ball in this set (but it is impossible to know how many of ...
- 15.7k
11
votes
2
answers
563
views
Pouring water from bottles
There are three buckets of size $x_1, x_2$, and $x_3$ liters (positive, but not necessarily integers), and some bottles, possibly of different sizes, containing a total of $x_1+x_2+x_3$ liters of ...
- 1,971
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
8
votes
2
answers
1k
views
Algorithm for least required matches to rank players in tournament
Assuming the following conditions:
A higher skill level always beats a lower skill level.
Given n players, each have a distinct skill level compared to the other (n-1).
If player A has beat player B, ...
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k
5
votes
2
answers
1k
views
How to find the optimal mapping between two sets?
Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
- 701
4
votes
3
answers
4k
views
Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)
We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks ...
- 143
4
votes
2
answers
2k
views
How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?
Let $D$ be set of denominations and $m$ the largest element of $D$. We say that $c$ is a counterexample if the greedy algorithm gives an answer different from the optimal one.
Now, apparently, if for ...
- 175
4
votes
0
answers
103
views
Reducing column ranges of a matrix
I'm looking for an algorithm to reduce the sum of column ranges in a sparse integer matrix by subtracting $1$ from all nonzero elements in a subset of the rows.
Let $R = 1, \ldots, m$ and $C = 1, \...
- 146
3
votes
1
answer
105
views
Show that a minimal solution has degree at most 2
Given a graph $G=(V,E)$, and a set $T\subseteq V$ of terminals, we say that $S \subseteq V\setminus T$ is feasible if $G[T\cup S]$ is connected.
In other words, a feasible solution is a set of non-...
- 578
3
votes
1
answer
62
views
Re-Balancing Bins with Capacity Limit Problem
Let $\hat n = \{1, \dots, n\}$. Assume that we have a sequence of bins
$$ B_1, B_2 ..., B_n $$
which all have the same capacity limit $c \in \mathbb{Q}$. Now, there is a finite set of items $I \...
- 2,653
3
votes
3
answers
129
views
Efficient algorithm for optimization problem.
I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers:
...
- 391
3
votes
0
answers
99
views
What set of angles uniquely defines a convex quadrilateral?
I am trying to characterize the set of angles in a (convex) quadrilateral that distinguishes it from any other quadrilateral that is not similar to it. Such a set will be said to uniquely define a ...
- 1,022