All Questions
32
questions
5
votes
1
answer
163
views
Minimal number of questions to identify a subset
This is a curiosity question.
Recently I stumbled across the following problem :
Given three integers $k,m, n$ such that $m+k\leq n$. A friend chooses a subset $S\subseteq\lbrace1,\ldots,N\rbrace$...
- 13.8k
22
votes
6
answers
539
views
Proving surjectivity of some map from a power set to a subset of integers.
We assign to every element $i$ from $N=\{1,2,...,n\}$ a positive integer $a_i$. Suppose $$a_1+a_2+...+a_n = 2n-2$$ then prove that map $T: \mathcal{P}(N) \to \{1,2,...,2n-2\}$ defined with $$T(X) = \...
- 90.7k
9
votes
3
answers
535
views
What is the largest possible number of moves that can be taken to color the whole grid?
Consider a $10\times 10$ grid. On every move, we color $4$ unit squares that lie in the intersection of some two rows and two columns. A move is allowed if at least one of the $4$ squares is ...
- 90.7k
2
votes
2
answers
223
views
Greedy algorithm in matching students to juries that they like with an upper bound number of students each jury can check
Recently I solved this following problem using greedy algorithm.
There are $100$ students who participate at exam.Also there are $25$ members of jury.Each student is checked by one jury.Known that ...
- 4,102
1
vote
1
answer
1k
views
Sum over all contiguous partitions of an array
Consider an array $A$ of length $n$. We can split $A$ into contiguous segments called pieces and store them as another array $B$ . For example , if $A = [1,2,3]$, we have the following arrays of ...
- 13
1
vote
1
answer
283
views
Showing there exists a sequence that majorizes another
The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can ...
- 1,408
5
votes
1
answer
2k
views
Match off points into $N$ red/blue pairs with straight lines connecting pairs, so that none of lines we draw intersect
Suppose we are given $2N$ points in the plane (we may assume that no $3$ are collinear). Assume that $N$ of these points are colored red, and $N$ points are colored blue. Can we match off the points ...
user268197
7
votes
2
answers
3k
views
Given $2n$ points in the plane, prove we can connect them with $n$ nonintersecting segments
Given $2n$ points in the plane such that no three points lie on one line. Prove that it is possible to draw $n$ segments such that each segment connects a pair of these points and no two segments ...
- 1,408
4
votes
2
answers
1k
views
Algorithm to uniquely determine a number using two adjacent digits
(Russia)
Arutyun and Amayak perform a magic trick as follows. A spectator writes down on a board a sequence of $N$ (decimal) digits. Amayak covers two adjacent digits by a black disc. Then Arutyun ...
- 3,914
1
vote
1
answer
2k
views
Making all row sums and column sums non-negative by a sequence of moves
Real numbers are written on an $m\times n$ board. At each step, you are allowed to change the sign of every number of a row or of a column. Prove that by a sequence of such steps, you can always make ...
- 3,914
2
votes
1
answer
133
views
Find different sequences of game to find winner
Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
- 272
1
vote
1
answer
342
views
Count ways to distribute candies
N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students ...
- 272
0
votes
1
answer
1k
views
Minimum number of moves to equalize a list
Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list?
For example: If the list is $2,...
- 1
1
vote
1
answer
377
views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$
(integer division) (nodes ...
- 21
4
votes
1
answer
893
views
Card Shuffling [SPOJ]
The original question is posted on SPOJ, and included below:
Here is an algorithm for shuffling N cards:
1) The cards are divided into K equal piles, where K is a factor of N.
2) The ...
- 183