All Questions
Tagged with combinatorics algorithms
1,042
questions
2
votes
2
answers
86
views
Is this problem NP-hard？Or what kind of mathematical problem does it belong to?
Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
- 33
2
votes
0
answers
17
views
Mechanic shop with limited delay capacity
Suppose a mechanic shop serves $M$ customers for $N$ days. Each morning, each customer brings in a number of parts to repair (denoted by $0\leq A_{i,j}\leq A_{max}$).
Suppose all parts need to be ...
- 75
1
vote
1
answer
177
views
Total number of distinct possible marks for given number of questions and marks (ZIO 2023 Q1)
Q. There is an exam with N problems. For each problem, a participant can either choose
to answer the problem, or skip the problem. If the participant chooses to answer the
problem and gets it correct, ...
- 11
1
vote
0
answers
47
views
Squared multiplicty minimization in multiple set choosing problem
The problem is the IOI 2007 competition's Sails problem. It has also appeared in Pranav A. Sriram Olympiad Combinatorics notes (Chapter 1 Exercise 14). I copied the problem description from Pranav. ...
- 11
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 ...
0
votes
0
answers
35
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
1
vote
1
answer
92
views
A shuffling algorithm that limits the number of consecutive repetitions?
This question comes from Stack Overflow. I feel that we need more of a mathematical breakthrough, so I forward the question here.
I also found a similar problem that seems to be a special case of this ...
- 11
8
votes
0
answers
278
views
Count permutations with given longest increasing subsequence
Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
- 4,051
0
votes
2
answers
62
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 143
2
votes
0
answers
87
views
Finding all possible valid values of a set based on a list of rules.
I'm working on a programming project and I stumbled into a bit of a problem. I think it's not an impossible problem, but I'm guessing it would involve some math. It would be amazing if anyone can ...
- 121
1
vote
1
answer
48
views
Indexing function for placements of identical balls into distinct boxes.
I am trying to find out if there is a mathematical function which can take n objects and place them in m boxes in a way that is indexed?
For example if I had 3 balls and I wanted them in 4 boxes, the ...
- 111
0
votes
0
answers
24
views
Counting Paths in the XY Plane (Discrete math) [duplicate]
I need help with the following mathematical task:
A particle moves in the xy-plane according to the following rules:
U: (m, n) → (m+1, n+1)
L: (m, n) → (m+1, n-1)
where m and n are integers. I need ...
- 39
3
votes
1
answer
97
views
Expected Length of Maximum Decreasing Subsequences in Random Sequences
Given $ n $ distinct numbers that are randomly shuffled to form a sequence $ A = [a_1, a_2, \ldots, a_n] $, we select the largest number $ x_1 $ from the sequence. Subsequently, we pick the largest ...
- 1,231
2
votes
2
answers
84
views
Analytic solution for number of paths with length $k$ on an $n \times n$ Chessboard allowing Self-Intersecting?
Consider an $n \times n$ chessboard where the journey begins at the bottom-left corner $(1, 1)$ and concludes at the top-right corner $(n, n)$. How many distinct paths are available that necessitate ...
- 1,231
5
votes
0
answers
485
views
How many Color Balanced sets can you make with n colors?
You have n colors and you make nonempty sets from them. A set of these color sets is color balanced if each color is in the same number of the color sets.
Ex. For <...
- 51