All Questions
58
questions
17
votes
3
answers
5k
views
In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?
For example:
$M = 2, N = 2$, ans $= 6$
$M = 3, ...
- 251
8
votes
1
answer
2k
views
Is there a simple algorithm to generate unlabeled graphs?
While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
- 1,431
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
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 \...
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
5
votes
1
answer
146
views
$X^A \equiv B \pmod{2K + 1}$
I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.
Is there something special about the modulus being odd that allows us to ...
- 51
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 ...
4
votes
1
answer
285
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
3
votes
2
answers
1k
views
Why do greedy coloring algorithms mess up?
It is a well-known fact that, for a graph, the greedy coloring algorithm does not always return the most optimal coloring. That is, it strongly depends on the ordering of the vertices as they are ...
- 731
3
votes
3
answers
6k
views
What are the prerequisites for combinatorics?
I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
- 55
3
votes
1
answer
2k
views
what' is the number of full subtrees of a full binary tree?
I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are:
Now my question is:
What is $N(h)$ the maximum number of full sub-trees of a full ...
- 13.8k
3
votes
1
answer
205
views
Traveling salesman neighborhood
I am solving some TSP problems and i got this one and i am not pretty sure about my answer.
By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
- 14.7k
3
votes
0
answers
72
views
Dividing class into groups
Just a question I have been pondering.
Assume you have a class of 100 students, each student chooses 3 friends. The goal is to split them into 4 groups of 25.
We define 'satisfaction level of ...
- 193
2
votes
1
answer
2k
views
Partitioning a set of integers into 4 subsets with equal subset sums
Given $n (n \leq 20)$ positive integers and each integer is $\leq 10,000$. Can they be partitioned into $4$ subsets such that sum of the subsets are pairwise equal to each other.
I am interested in ...
- 628
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