Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
119
questions with no upvoted or accepted answers
0
votes
0answers
82 views
How to solve this dynamic programming puzzle on matrix?
We are given 4 integers N,M ,Q and Z.
Initially,the matrix has all zeroes in it.
We have to perform Q operations on the matrix.
In each operation, any cell of the matrix can be selected(same cell ...
0
votes
0answers
107 views
Minimum Ratio Spanning Tree
Problem statement:
Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
0
votes
0answers
48 views
O(1) algorithm to get approximate number that is larger as a binomial coefficient
Ideally I need a to calculate the binomial coefficient ${p \choose n}$. But since the fastest algorithm to do this is an $\mathcal{O}(n)$ algorithm I would look to do something different. I don't ...
0
votes
0answers
251 views
Counting chords intersections in a circle
The problem is:
Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point,
that point counts as $\binom{n}{2}$ ...
0
votes
0answers
81 views
Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts
The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has ...
0
votes
0answers
70 views
Multi-trip travel salesman problem
Given a graph $G$, I want to find a shortest tour visiting each vertex. Different to the classical formulation of TSP, my tour needs to be divided into several subtours, each upper-bounded by a ...
0
votes
0answers
442 views
Permutation of multiple groups of different sizes
While working on my research for my master thesis I have stumbled upon the following problem:
Given $N$ groups of different sizes, create all the possible combinations $p$ such that:
$p = \{e_{0,j_0}...
0
votes
0answers
27 views
Assign team members to groups to maximize outcome
Team A has 2 Spots
Team B has 1 Spot
Player 1: 10 Units when on team A, Can't work on team B
Player 2: 8 Units when on team A, Can't work on team B
Player 3: 9 Units when on team A, 2 Units when ...
0
votes
1answer
151 views
Matching 2 sets of items by price
I'm trying to solve the following problem in the most efficient way I can find.
I want to trade my items for someone elses items, every item have a price and a value.
I want to maximize the value of ...
0
votes
0answers
85 views
no of ways to fill a row (1xN grid) with a set of 1D bars with some constraints?
Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row?
A is an integer array,
the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,....
0
votes
0answers
94 views
Get all possible combinations of distributing x*n balls into n boxes
I'm trying to figure out how to get all combinations of putting x*n balls into n boxes.
...
0
votes
0answers
54 views
Approximate algorithm to find the minimum score
Given $n$ variables and a function $f$ such that $f(v) = N(v) + D(v)$, where $N$ and $D$ are the subfunctions of function $f$. Function $f$, can be considered as an oracle.
Query: let $v \in P$, ...
0
votes
0answers
280 views
How many valid and unique Turing machines are there with restricted states and characters
This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of ...
0
votes
1answer
1k views
Data structures and algorithms for bridge game play?
In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There ...
-1
votes
1answer
79 views
Number of sequences of given type
Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
-1
votes
2answers
64 views
I am unable to understand the logic behind the code (I've added exact queries as comments in the code)
Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He
only has a limited amount of energy (e) to spare that he must entirely distribute among all of his
...
-1
votes
2answers
1k views
How many integers can you represent with 6 bits?
I might be wrong but I think it must be 2^6 = 64 integers?
-1
votes
1answer
200 views
What algorithms solve the minimun multidimensional multidemand 0-1 knapsack problem?
I've found an heuristic algorithm[scatter search] that solves the common version of MDMKP(MultiDemand Multidimensional Knapsack Problem)[the one that maximizes] but what about the minimize version? is ...
-2
votes
1answer
44 views
Given Q constraints find the number of binary arrays of N elements
You have to find the number of arrays having N binary elements (0/1), that satisfy the Q given constraints.
The constraints are of the form Li Ri Bi.
Where if Bi is 0, then it means that the sum of ...
