# Tag Info

6

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for integer-valued functions in Chapter 1. It gives a simple greedy algorithm for solving this problem: While the proof of theorem (1.1.13) is somewhat involved, the ...

6

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.

5

Suppose that your team contains $n$ people. Each round of discussions ("session") corresponds to a matching in the complete graph $K_n$. Therefore you want to partition into as few matchings as possible. The answer depends on the parity of $n$. Case 1: $n$ is even. In this case, $K_n$ contains $\binom{n}{2}$ edges, and a matching contains at most $n/2$ ...

4

Strictly speaking it is possible to construct $2k$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $2k-1$ spanner. Indeed, assuming Erdős Girth Conjecture, there are graphs $G=(V,E)$ with girth (length of the shortest cycle) $2k+2$ and $\Omega(n^{1+\frac{1}{k}})$ edges. A $2k$ ...

4

Here is a simple iterative solution. We maintain two arrays, an output array $L$, and a Boolean array $A$, which keeps track of the elements currently in $L$. We update $A$ as we add and remove elements from $L$. We initialize $L$ with $0,\ldots,k-1$, which is also our first output. Now we repeatedly try to "increment" $L$. If successful, we output ...

4

The most appealing solution so far seems to be a spin on Python's own permutations function (source) that can be slightly simplified for this use case; thanks @Peilonrayz: def combinations(r: int, n: int=10) -> Iterable[Sequence[int]]: pool = range(n) indices = list(pool) cycles = list(range(n, n-r, -1)) r_range = range(r-1, -1, -1) ...

3

This problem is NP-complete. Let's reformulate it first: we have a bipartite graph, where The left side corresponds to elements The right side corresponds to sets The edge $(u,v)$ means that $u \in v$. Our goal is to find the bipartite clique with the maximum number of edges. As stated in Rene Peeters, "The maximum edge biclique problem is NP-complete&...

3

Let $(u,v,w)$ be a particular triangle in the stream, and suppose that the edge $(u,v)$ appears first. The probability that we chose $(u,v)$ in the first step is $1/m$. The probability that we chose $w$ in the second step is $1/(n-2)$. Hence the probability that we chose the triangle $(u,v,w)$ is $1/[m(n-2)]$. Let us denote this event by $E_{u,v,w}$. If $(... 3 If you have$n$sets of$k$elements, your problem is equivalent to that of generating all numbers with up to$n$digits in base$k$(where the$i$-th digit of a number represents the index of the element to select from the$i$-th group). This can easily be done by starting from the number$(00\dots000)_k$and iteratively adding$1$. Let$d_i$be the$i$-th ... 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 ...

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

I think this can be solved by reduction to a circulation problem. Introduce a graph with source $a$ and sink $z$. The edges are as follows: All edges will have infinite capacity, lower bound 0, and cost 0 unless mentioned otherwise. Add an edge $z \to a$ with cost 1. Add edges $a \to c_i$ for each color $c_i$ and $s'_k \to z$ for each smell $s_k$. For each ...

3

The way Raymond Hettinger's itertools permutations works is by following the cyclical nature of permutations. And converting from a recursive to iterative function. Establishing a recursive pattern We can build a recursive function to show us the underlying pattern. We can build off of Yuval Filmus's recursive solution. However we should change the code to ...

2

The very general problem is (weakly) NP-complete if you want the optimal solution, however, in general there aren't arbitrarily large sibling cliques. The problem can always be modeled as an integer linear program (ILP). If you just want a good enough solution, then I would start with a greedy algorithm, followed by local search. You can always keep the ...

2

Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph. Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for ...

2

You can use recursion. def recursive_generate(S): IF #S = 1: s <-- the single set in S return {{item} | item \in s} END IF S' <-- {} s <-- some selected set from S FOR item in s: For r in recursive_generate(S\{s}): S' <-- S' \union (r \union {item}) END FOR END FOR RETURN S' ...

2

For the diagonal case, split to two proofs - one for each "rotation" of the diagonal line. When the diagonal line is "from top left to bottom right", then assume for the sake of contradiction we have two queens $i,j$. Then in order for them to be on the same diagonal line, there must be some $k$ where $i+k=j$ and $2i \pmod n + k =2j \pmod n$. Thus both $k=j-... 2 Vertically: if$Q_i$and$Q_j$have the same$x$-coordinate,$i = j$so they're the same queen. Horizontally: if$Q_i$and$Q_j$have the same$y$-coordinate,$2i = 2j \pmod n$, so$2i = 2j + kn$for some$k \in \mathbb{Z}$; since$n$isn't divisible by 2,$k$must be, and we have$i = j + (2k')n$, so$i = j \pmod n$. Since both$i$and$j$are$\le n$, ... 2 Consider$i < j$between 0 and$ n-1$. Of course, the first coordinate can’t be same for any two queens, hence they aren’t in same row. Now, suppose, for the sake of contradiction, they lie on the same column. Then,$2(i-j) = nk$for some natural$k$. Now, as n doesn’t contain 2 as it’s divisor,$k$must be even. So, either$k$is 0, which is not ... 2 "Binary toggling games" are generally just arithmetic problems over GF(2). Your particular problem is equivalent to the following over GF(2): $$\sum_i V_iS_i = 1 + A_M$$ If we write$\vec{S} = [S_1, S_2, \dots]^T$and$V = [V_1, V_2, \dots]^T$we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A_M$$ You can ... 2 If$|S|=2N$, then the largest "partnering" is a$1$-factorisation of the complete graph, or a round-robin tournament schedule. There always exists a schedule that pairs all people exactly once in$2N-1$rounds without repeating pairs. There are various algorithms to find such a schedule, see the previous link. 2 Erdős and Gallai showed in their paper Solution of a problem of Dirac then the chromatic number of a non-complete regular graph is at most$\frac{3}{5}n$. Caccetta and Pullman constructed in their paper Regular graphs with prescribed chromatic number connected$k$-chromatic regular graphs on$n$vertices for all$k > 1$and$n \geq \frac{5}{3}k$. You can ... 2 I understood the problem as that we can select any$S_i$satisfying these conditions. Then the answer is$\{0, 1, 2, 3, 4, 5\}$. The construction is unique in a certain sense. Wlog we can assume that$S=A$(otherwise, just remove redundant elements from$S$). I'll use$A, B, C, D, E$instead of$S_i$. One way to arrive at a solution is to draw a Venn diagram ... 2 Let's denote:$C$, the$c$different colors,$T$, the$t$different tastes,$S$, the$s$different smells,$X$, the edges of the possible color/taste combinations,$Y$, the edges of the possible taste/smell combinations,$G((C, T, S), (X, Y))$, the tripartite graph of the problem. FIRST STEP Let's take the bipartite graph$G_L (C, T, X)$containing ... 2 The problem of iterating all partial permutations is closely related to the problem of generating a uniform random sequence$U$of$k$(u)nique integers from$0 \le U[j] < n$. The usual solution to that problem is first to generate a uniform (r)andom sequence of numbers$R$satisfying$|R| = k0 \le R[j] < n - j$then covert$R$to$U$. So for ... 2 It's a bad practice to use the same variable for two purposes, so I'll say that you have$C$conflicts$(c_1, c_2, \dots, c_C)$and similarly$M$conflict resolution methods. To simplify, let$r_{ji} = 0$if$c_i$and$m_j$are disconnected. Suppose$t_j$is a variable indicating how many times method$m_jwas used we can phrase your problem as \begin{align}... 2 You can indeed formulate an Integer Linear Program. Letx_i \in \{0,1\}$denote whether you select item$i$. For each item$i$define$f_a(i)$,$f_b(i)$, and$f_c(i)$as the integer values for the properties$A$,$B$, and$C$. Then we define the objective function as maximizing$\sum_{i = 1}^{m} f_a(i) \cdot x_i$, given$m$items in total. Your constraints ... 1 Multilinear polynomials If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing. You want to test whether$f(x)=g(x)$holds for all$x$, where$f,g$are multilinear oolynomials. This is an instance of the polynomial identity testing problem. There are effective randomized algorithms for ... 1 I assume you want to put items$w_1$to$w_{i_1}$into the first bin,$w_{i_1+1}$to$w_{i_2}$into the second bin, etc. etc. The number n of bins is given. This can be done with something similar to dynamic programming. Examine all possible choices for$_1$and calculate the error from bin 1 for each of these choices. Then examine all possible choices for$...

1

In order to bound the number of functions computed by circuits of size $k$, you have at least two options: Construct a large number of circuits of size $k$, which by construction compute different functions. Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function. ...

Only top voted, non community-wiki answers of a minimum length are eligible