9

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the computational complexity. Run the binary search three times. At least two of the three results must be equal to the hidden number. Return the majority result. There ...


7

Dynamic Programming can be used to solve a problem as long as the problem has a recursive substructure and the sub-structural problems are overlapping. So, as long as a problem has the two properties, DP can be used for solving it. Problems with these properties are definitely not restricted to only optimization problems. So, yes. Here are some good ...


7

If normal binary search would take k questions, then you can solve this with 2k+1 questions: Ask each question twice. If you get the same answer, it was the truth. If not, a third question reveals the truth, this happens only once. I suspect you can do better. If the number is from 1 to 100 and I check the numbers 40 and 60 then knowing that one answer is ...


6

Here is a dynamic programming algorithm. Given a graph $G = (V, E)$ and two vertices $u, v \in V$. We define the recursive function $C:V\rightarrow \mathbb{N}$, such that $C(w)$ is the number of paths from $w$ to $v$. Note that we are looking for the value of $C(u)$. We set $C(v) = 1$ and $C(w)=0$ for each vertex $w \neq v$ with out-degree equal to zeroo. ...


6

Hint #1: Hint #2:


5

This is only a sketch of solution (there might be some off-by-ones) Looking at a permutation of $\{1\ldots,n\}$ is equivalent at looking its inversion table $(a_1, \ldots, a_n)$ where $a_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S_n$ and $\prod_{1\le i\le n} \{0,\ldots,i-1\}$ and ...


5

Heh…for the record, all I said was that the time seems to scale as approximately $\tilde O(2^{1.5n})$. If this was anything more than a conjecture based on the timing data that I included in the post, I would have said something more specific! I’m sure you’re familiar with the usual Wagner–Fischer algorithm for Levenshtein distance, where we compute $d_{i,j}...


5

Here is a systematic way to approach it. I suggest you define three values: $A_0(n)$ is the number of ways to tile a $3 \times n$ region. $A_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered. $A_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of ...


4

This technique is called Lagrangian relaxation. The regular $DP$ approach, where $DP[a][b]$ represents the length of the longest increasing subsequence that ends in the $a$'th number and restarts at most $b$ times, is $\mathcal{O}(nk \log n)$. For convenience we'll assume the last number is the largest, and therefore $DP[n][k]$ is the value we are looking ...


4

Because a local maximum is not always a global maximum. The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first ...


4

It's great that you're curious. A simplified explanation follows with a few links to delve into: All of the programs running in parallel is actually an illusion that is created by the OS. Even if we have a uniprocessor system, the OS can still achieve the same thing. For multiple programs running on the system, OS creates separate processes. Separate ...


4

I think there is some confusion in terminology here. Part of the problem is what we mean by problem and algorithm. But there is more to it: Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a ...


4

There is a $\mathcal{O}(nk)$ DP approach. Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must ...


4

The optimization function is designed in a way to find a solution that: uses a small number of lines is balanced (the number of extra spaces at the end of each line should be about the same length) Lets look first at the linear optimization function, i.e. the sum of all extra spaces. It is very clear, that the optimal solution under that function is one ...


4

Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$. Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations). Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that ...


4

This counting problem is one of the classical problems that can be solved efficiently by dynamic programming. Since we should find the number of ways to fill a 3 by $n$ rectangle, a natural set of subproblems is the number of ways to fill a 3 by $m$ rectangle, where $m\le n$. However, it turns out it is practically impossible to find a recurrence relation ...


4

For $i=1,\dots,N$, and $r \in \{S,R,B\}$ define $OPT[i,r]$ as the maximum profit that can be obtained by robbing a suitable subset of the first $i$ houses with the following constraints: If $x=S$ (as in Skip) then house $i$ must not be robbed. If $x=R$ then house $i$ must be Robbed while house $i+1$ will not be robbed (to avoid a case distinction later we ...


3

Memoization is the technique to "remember" the result of a computation, and reuse it the next time instead of recomputing it, to save time. It does not care about the properties of the computations. Dynamic programming is the research of finding an optimized plan to a problem through finding the best substructure of the problem for reusing the computation ...


3

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987). When the decision horizon is infinite and we are using e.g. the ...


3

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to ...


3

Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ indices we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq [i]$, such that $\sum_{j \in I} A[j] \geq ...


3

I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type. It also really helps to program them in (e.g.) Python so that you get some hands-on experience. So, perhaps it is better to start with a simpler tree ...


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

Suppose the gap between any two words in the same line spans a length of $k$, instead of 1. The only change needed in the Python code would be to change the line in def cost(i, j) from w = offsets[j] - offsets[i] + j - i - 1 to w = offsets[j] - offsets[i] + k * (j - i - 1) def cost(i, j) returns the minimum cost needed for placing the first $j$ words, if ...


3

This problem is a case of maximum flow problem. Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the following. Nodes are $s,\ p_1, p_2, \cdots, p_m,\ r_1, r_2, \cdots, r_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink. There is an ...


3

This can be solved in $O(n)$ time using BFS. Consider any sequence of moves that ends in a valid solution (all letters are in the second stack and are grouped). At every intermediate point in this sequence, the letters on the second stack must be grouped. (If the letters in the second stack ever become ungrouped, then they stay ungrouped from there on -- ...


2

Here is a way to solve the problem of longest valid parentheses by dynamic programming as you had hoped. Or almost. For simplicity, a string is called valid if it consists of well-formed opening and closing parentheses. The critical observation is that a string is valid if it is the empty string, a concatenation of two valid strings or "(" followed by a ...


2

A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \...


2

Suppose that the candidates are $x_1,\ldots,x_n$ and the target is $T$. I'm assuming all candidates are positive. If $T < 0$ then there are no solutions. If $T = 0$ then the only solution is the empty solution. Otherwise, there are two kinds of solutions: $x_1$ together with a solution for $T - x_1$ using all candidates. A solution for $T$ using the ...


2

Greedy algorithm doesn't always generate optimal solution. To get optimal solution with it, the problem needs to have some good property such as optimal substructure or matroid. The optimal substructure means optimal solution can be constructed from the optimal solutions of divided problems. Matroid theory shows another good property to characterize where ...


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