All Questions
58
questions
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