New answers tagged

1

There's the trick that is typically used when FFT is used for multiplication of large integers: If your calculation produces a floating-point number x, and you know that the mathematically correct result is an integer, and you can prove through careful analysis that the total rounding error in your result is less than 0.5, then x rounded to the nearest ...


1

Based on the, apparently famous paper on the field, Ryser 56, and the thesis recommended by @orlp, the test to know if a row and column sum vectors forms a match, e.g., a matrix $M_{h,w}$ exists having these row and column sum vectors, is the following one: Let $R_h$ be a vector of $h$ elements sorted in a non-increasing order ($r_1\geq r_2\geq\ldots\geq ...


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 ...


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 ...


0

Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings $S$ and $T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest. One way to detect if a sequence forms a valid balanced parenthesis is to change ( for +1 and ) for -1 and ...


0

it's possible that a clever method of indicating which permutation to use could get below the full 73 bits No, because encoding the permutation/relabelling/rotation/whatever takes you back to 73 bits. Off the top of my head, I'm guessing there are 8 possible symmetries. Then assuming that you need two permutations (rows and columns?) and one relabelling: $$...


1

Here's a no-table method that combines a 75-bit encoding of the solution grid with an 81-bit encoding of which cells are clues to give a 156 bit fixed-length encoding for all puzzles ([edit] also see below for further development of a variable length encoder for the clue positions which needs 73.1 bits on average instead of 81, yielding 148.1 overall with an ...


0

I know it is a bit late for an answer to that post. Maybe you should have closed it within a year of no relevant answer. The problem is not that easy, just with one additional constraint, there is a lot of work dealing with the problem. You can use branch and bound algorithm. In the branch and bound, there are different ways to proceed.


-1

EDIT: As pointed out in the comments this doesn't work! Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid ...


Top 50 recent answers are included