All Questions
Tagged with combinatorics algorithms
1,042
questions
1
vote
1
answer
318
views
Converting Undirected Graphs to a Tree While Preserving Edge Information
I'm working on a problem where I need to convert an undirected and unweighted graph with cycles into a tree while preserving the edge information (all the edges from the graph are preserved in the ...
- 11
1
vote
2
answers
71
views
When can a deck be shuffled by shuffling fixed subdecks?
Suppose I want to shuffle a deck of $n$ cards, but I have a problem -- for some reason, I am only able to shuffle at most $n-1$ cards at a time at some fixed indices. For example, if $n=5$, I could ...
- 685
4
votes
1
answer
283
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
46
views
Last step of an intense algorithm requiring efficiency: A closed form for $\sum_{s=2}^{\lfloor\frac{T}{2}\rfloor}{2s-1 \choose s-2}{T \choose T-2s}$?
I'm working on an algorithmic problem for HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler106/problem
The broad overview of the problem is finding how many evenly-sized ...
- 11
3
votes
1
answer
115
views
Social golfer problem with additional requirement
I need to write a program that sorts people into groups.
To give a little context: The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the ...
2
votes
1
answer
126
views
Optimal strategy in number guessing game?
Consider the following game.
Two players each create a passcode using the digits 0-9 four times with repetition allowed.
The two take turns asking a yes or no question about the opponent's passcode. ...
- 21
0
votes
1
answer
123
views
Generalised Rubik's cube algorithm to go from any valid cube state A to any valid cube state B.
For a $3 \times 3 \times 3$ cube, there are several known algorithms to go from any valid state of the cube to the solved state, $S$, of the cube (same color on each side).
How about a more general ...
- 79
1
vote
1
answer
180
views
Closed formula for recursive algorithm
The $treeSize(n)$ function is designed to calculate the number
of leaf nodes in a spherical tree structure. The tree is generated
by recursively exploring points in three-dimensional, discrete space,
...
- 29
1
vote
0
answers
30
views
Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?
This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
- 141
0
votes
0
answers
76
views
Deranged generous gift giving in the limit
I was writing a routine for a game and stumbled upon some algorithm issues and a theoretical question about it. Here I'm mostly concerned with the latter, which may be phrased as a sort of graph ...
- 12.3k
1
vote
1
answer
54
views
All cliques of a graph
Given an arbitrary undirected graph $G$ with $n$ vertices, I am interested in counting the number of cliques.
(For example, the number of cliques of a complete graph $K_n$ is trivially $2^n-1$;the ...
- 203
0
votes
1
answer
139
views
On a Codeforces combinatorics problem, from $O(m^2n)$ to $O(n \times \min(m, n))$? [Codeton 5 Problem G]
Problem link: https://codeforces.com/contest/1842/problem/G
Brief explaination:
Given a positive integer array $a$ ($1$-indexed) of length $n$ ($1 \leq n \leq 5000$) and a positive integer $v$, ...
- 1,008
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 2,979
2
votes
0
answers
47
views
How many ways are there to remove $2 \times 2$ rooms from $n \times m$ bounded grid by building walls
On an $n\times m$ grid, a room is considered to be a $2\times 2$ subgrid such that there isn't a wall between any $2$ cells in that subgrid that share an edge.
Initially, there are no walls in the ...
- 93
1
vote
1
answer
49
views
Optimizing Uniform Distribution of Attributes in Item Selection: A Combinatorial Problem
I am an engineer with limited mathematical proficiency, and I have encountered a quite challenging mathematical problem during my work. The problem as a whole is intricate, but I will try my best to ...
- 13