All Questions
12
questions
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
- 419
4
votes
1
answer
2k
views
Expected value when die is rolled $N$ times
Suppose we have a die with $K$ faces with numbers from 1 to $K$ written on it, and integers $L$ and $F$ ($0 < L \leq K$). We roll it $N$ times. Let $a_i$ be the number of times (out of the $N$ ...
- 235
3
votes
1
answer
309
views
Algorithm to partition a multiset into $K$ equal sized multisets
How can I partition a multiset of integers, $A$, of size $N=MK$, into $K$ equal-sized multisets, $G_1,G_2,\ldots,G_K$, such that $\sum_i \mathrm{\lvert \min(G_i)\rvert}$ is maximized? Here, $\min(G)$ ...
- 53
7
votes
1
answer
830
views
Alice and Bob make all numbers to zero game
Alice and Bob are playing a number game in which they write $N$ positive integers. Then the players take turns, Alice took first turn.
In a turn :
A player selects one of the integers, divides it ...
- 235
3
votes
3
answers
354
views
why $m$ power by $n$ equals sum of $n$ numbrs
$$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$$
(a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are $m$ and $n$. I know that this is true, ...
- 1,680
2
votes
1
answer
1k
views
Greedy algorithms: why does no optimal solution for smaller coins mean that the greedy algorithm must work?
I'm reading Competitive Programmer’s Handbook. They take the Euro to perform analysis on a greedy algorithm.
For example, if the coins are the euro coins (in cents)
{1,2,5,10,20,50,100,200} and n ...
- 149
2
votes
1
answer
2k
views
How to check if any subset of a given set of numbers can sum up to a given number
Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,\dots n_k$ times. How do I tell if it is possible to find a ...
- 121
2
votes
1
answer
3k
views
Count arrays with each array elements pairwise coprime
Given two integers $N$ and $M$ , How to find out number of arrays A of size N, such that :
Each of the element in array, $1 ≤ A[i] ≤ M$
For each pair i, j ($1 ≤ i < j ≤ N$)
$GCD(A[i], A[j]) = 1$...
- 235
2
votes
1
answer
163
views
Find two subsets with a common sum in two sequences
For a positive integer $n$ and two integer sequences $a_1,a_2...a_n$ and $b_1,b_2...b_n$ where $\forall i$, $a_i,b_i \in [1,n]$, I want to find two non-empty subsets, one in each sequence, with the ...
- 232
0
votes
1
answer
2k
views
Number of ways to win chocolate game
Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates.
The game goes like ...
- 311
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
0
votes
1
answer
79
views
Maximizing sum of metric function on a set (Adaptation of Hungarian Algorithm)
Suppose I have a set of unique elements $A=\{a_1, a_2, ..., a_n\}$. Suppose I also have a metric function $f:A\times A \rightarrow R^+$. I want to choose $k$ elements from $A$ (i.e. $a_{i_1},a_{i_2}, ....
- 2,457