New answers tagged

0

The numbers involved are small, which makes this quite trivial. The numbers are ≤ $10^5$. We have $10^5 < 47^3$, and there are 14 primes < 47. So for each of the numbers x, y in X, Y, we calculate a 14 bit integer with bit #i set if x, y is divisible by an odd power of the i-th prime, and we also calculate x', y' which are x, y divided by the ...


3

Consider the following special case where for each element $i$ the table contains the constraint $\#i \geq (1/l) \cdot l$. This means we need to select the sets in such a way that each element appears at least once. This problem is called the set covering problem, where you have to output whether there is a subset of $l$ sets in the input that covers all the ...


3

There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x ...


0

I can't follow how you get 30 combinations, you have 2 matches per journey each of the 2 matches can result in 5 different attributions, so you get 5*5 = 25 different attribution per match. At each journey there are 3 possibilities to make 2 matches. So the result would be 25/3 + 25/3 + 25/3 = 25 different point attributions. Did I got something wrong? You ...


0

Just define a function $a(n)$ that adds 1 to non-zero (i.e., $a(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n + 1$) and another one $s(n) = \operatorname{if} n = 0 \operatorname{then} 0 \operatorname{else} n - 1$. For any given function $f(n)$, there are an infinite collection of functions computing the same result, like $s(a(f(\...


1

For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence: $$ \begin{align} &M(k,s) = 1 \\ &M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\ &M(n+1,tc) = M(n,ct) \end{align} $$ Here $t$ is a ...


Top 50 recent answers are included