All Questions
18
questions
1
vote
1
answer
44
views
find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom
here is the full question:
Use inclusion/exclusion to find the number of ways of distributing 30
students into six classrooms assuming that each classroom has a maximum capacity
of six students.
Let $...
- 15
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
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
0
answers
461
views
Count number of m-subsets with xor = 0 [closed]
Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let $[k]=\{1,2,\...
- 740
0
votes
2
answers
313
views
Sum of roots of binary search trees of height $\le H$ with $N$ nodes
Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees.
For example, for $N$ = 3, $H$ = 3: ...
- 412
1
vote
1
answer
492
views
Select $k$ non overlapping segments from $n$ points
We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap.
One possible solution would be by using a recurrence relation $f(k,n)=\sum i*f(k-1,n-...
- 6,038
1
vote
0
answers
44
views
What does "combining the solutions in O(n) time" mean?
Algorithm $X$ proceeds by recursively solving $5$ subproblems of
one-half the size, then combining the solutions in $O(n\log n)$ time.
Algorithm $Y$ makes $9$ recursively calls on subproblems ...
- 49
0
votes
1
answer
70
views
How to quickly determine running time of such recurrence relations?
$$T(n)=5T(\frac{n}{2})+n\log n$$
$$T(n)=9T(\frac{n}{3})+n^2$$
$$T(n)=2T(\frac{2n}{3})+n^{1.5}$$
What are the running times of each $T(n)$? Each one looks like the form of the Master Theorem, but only ...
- 1
0
votes
2
answers
1k
views
Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$
So $T(n)=3T(n/3)+\log n$ and $T(1)=1$.
I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern:
$T(n/3) = 3T(n/9)+\log (n/3)$
$T(n) = 3[3T(n/9)+\log (n/3)]+\...
1
vote
1
answer
2k
views
How many binary string are there such that there are no k consecutive characters are the same?
Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same.
Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
- 2,977
1
vote
1
answer
230
views
Algorithm for retrieving all the permutations (randomized) for a vector sequence 1...N with only unique values
Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$).
I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
- 149
1
vote
1
answer
209
views
Arrange blocks to form matrix of $N \times 3$
Given are the blocks of 3 different colors (Red,Green and Blue).
Red colored block of size $1 \times 3.$
Green colored block of size $1 \times 2.$
Blue colored block of size $1 \times 1.$
We ...
- 33
0
votes
1
answer
399
views
number of ways to fill a 2D grid
We have a 2D grid with n rows and m columns, we can fill it with numbers between 1 and k (both inclusive). Only condition is that for each r such that 1<=r<=k ,no two rows must have exactly the ...
- 315
3
votes
1
answer
808
views
number of derangements
In the normal derangement problem we have to count the number of derangement when each counter has just one correct house,what if some counters have shared houses.
A derangement of n numbers is a ...
- 315
3
votes
2
answers
194
views
Google Question: Number of ways to select sets such that n is pure
Consider a subset $S$ of positive integers.
A number in $S$ is considered pure with respect to $S$ if, starting from it, you can continue taking its rank in $S$, and get a number that is also in $S$, ...
- 315
0
votes
1
answer
613
views
probability of sum of a given set of whole numbers being greater than a certain number
There are total of n balls in k boxes. Box one contains n1 balls, box 2 contains n2 balls and so on. The probability of picking balls from boxes is p1,p2,...,pk. We can pick either all the balls in a ...
- 275
2
votes
1
answer
322
views
Solving for the closed form of a recurrence relation
Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
- 813
7
votes
1
answer
169
views
Put a mouse to the last cell
We have (n=12) cells $C_1, C_2 ,\dots, C_{12}$ which are initially empty.
At each step, we can do one of two operations:
$\mathbf{P}$: Put only in the first cell $C_1$ 2 mice.
$\mathbf{M}$: Move ...
- 1,356