# Tag Info

9

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example: A subquadratic algorithm for minimum palindrome factorization by Fici et al EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.

9

Your problem is solved in the paper Spheres of Permutations under the Infinity Norm — Permutations with limited displacement by Torleiv Kløve. See also A002524 and other sequences linked there. I found Kløve's paper by calculating the first few values of A002524 and finding it on the OEIS.

8

With m eggs and k measurements the most floors that can be checked is exactly $$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$$ (maybe $\pm 1$ depending on the exact def). Proof is trivial by induction. This expression has no closed form inverse but gives good asymptotic.

6

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication. So, proving a $\Omega(nk)$ lower bound in the monotone circuit model ...

6

I think the answer to my Question 1 is affirmative: there are matroids on which simple DP fails badly! That is, simple DP may be much worse than Greedy when trying to solve an optimization problem exactly. Let the ground set consists of all edges of $K_n$. As our family of feasible solutions take the family of all forests in $K_n$. This is a motroid, and ...

6

The linear time algorithms for this sort of problem are based on the SMAWK algorithm rather than more straightforward dynamic programming / memoization. I have an implementation of a linear-time line-breaking algorithm (possibly not exactly the one you want, but likely similar) in the Wrap.py module of my collection of Python algorithm implementations (you'...

5

One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability: When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?

4

You can solve this with dynamic programming as well. To see this, first realize you can see this problem as splitting the numbers between $0$ and $N$ into two subsets $X$ and $Y$ (the cumulative sums) that cannot overlap except at $0$ and $N$ (and must overlap there), and where the difference between consecutive elements of a subset is at most 3. ...

4

Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.

4

There's a polynomial-time dynamic programming algorithm in section 3.2 of https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p225.pdf (Albert et al, "Longest subsequences in permutations", Australas. J. Combin. 28 (2003), 225–238)

3

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm. Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time polynomial in $n$ and $\max_i p_i$. Proof. We first observe that the problem reduces in polynomial time to the "flipped" variant, where the profits are ...

3

Here's a poly-time dynamic-programming algorithm. Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm. Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$. For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows. Consider the problem restricted to the first $t$ time slots. (That is, ...

3

This is not a research level question. In any case DP is obtained by memoizing a recursion. If you start with an instance $I$ then the recursion generates several subproblems. You can obtain a dependency graph $G$ on these subproblems where each node is a subproblem and there is an arc $(I_i,I_j)$ if $I_j$ calls $I_i$. This dependency graph must necessarily ...

3

The main difference, in my view, is that DP solves subproblems optimally, then makes the optimal current decision given those sub-solutions. Greedy makes the "optimal" current decision given a local or immediate measure of what's best. Greedy doesn't reason about the subsequent choices to be made, so its measure of what's best is shortsighted and might be ...

2

This problem has an algorithm of time complexity that is polynomial in N, T and U (but not in polynomial in the size of N, T and U). This technicality is worth noting since the problem instances can be described by specifying just the integers T, U and N and hence strictly speaking the size of the input to this problem is O(log N + log T + log U). So in ...

2

In my comment above I said perhaps $\Theta(\min_{k \le m} kn^{\frac{1}{k}})$ is a tight bound. I'm not sure about the lower bound, but since you just want an explanation for what $k$ means, I can explain the intuition using the upper bound. As you guessed, $k$ is the number of eggs actually used. That explains the $\min$ on the outside. Now once we've ...

2

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input. There is a classical construction that is used to show that universality of a CFG is undecidable. The construction takes a Turing machine $M$ and outputs a grammar $G_M$, such that all strings in $L(G_M)$ are not valid accepting ...

2

Dynamic programming is not a greedy algorithm. It just embodies notions of recursive optimality (Bellman's quote in your question). A DP solution to an optimization problem gives an optimal solution whereas a greedy solution might not.

2

One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$. Another example is that of “connectivity problems”, such as ...

1

It's hard for $k\ge 2$ by a reduction from Partition. Let's first look at $k = 3$. Suppose that the input to Partition is the numbers $x_1, \ldots, x_n$, and their sum is $S$. For each $i$ create a vector $v_i$ whose first coordinate is $x_i$, second coordinate is $-x_i$, and the third coordinate is $0$. Add another vector $v_{n+1}$ with first coordinate $0$,...

1

Since you specifically ask later about the version of the problem in which the given path is restricted in how many times it visits each vertex/edge, I assume that the original version of the problem has no such restriction. In other words, in the original version of the problem the "path" is actually a trail (i.e., any sequence of vertices such that each ...

1

You can build the whole table using the following $O(n^2)$ construction: 1: 1 1 0 z:0 w:1 2 1 0 0 0 1 2: 2 1 0 1 3 3 1 0 0 1 3: y:2 1 1 3 4 v:3 1 0 1 4: x:2 2 3 4 u:4 ... 5: ... ... At every step you are calculating the value $x$ at the top of a "reversed triangle", and the value is ...

1

The answer is available online You can read their description and comparisons on wikipedia: http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm http://en.wikipedia.org/wiki/Dynamic_programming You can watch Tim Roughgarden's videos about these two topics: http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms

1

There is a nice trick to reduce $\geq k$ cycle to finding a cycle of length exactly $t$, for $t \leq 2k$ (I first heard of this trick from Daniel Marx). The key observasjon is that contracting an edge of $G$ may not increase the length of the longest cycle in G, and may only decrease the length by a factor at most two. Thus we can search for cycles of length ...

1

I think I figured it out. $Com_{H}(v, u)$ are paths leaving the region and connecting through some vertices outside the region. $Path_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region. $Path_{H}$ are paths inside the region If this is true, then the proof of Lemma 3.2 has some typing errors (the 2 a.m. kind). And ...

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