Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

119 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...

1 2
3