7

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below. Input: $e_1,\cdots,e_n\in E$, where $n\ge 3$. Output: $p_1, \cdots, p_n$, where $p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$, the product of all input elements except $e_j$. Procedure: Allocate array $p_1, p_2,\cdots, p_n$ ...


6

This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill? In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The ...


6

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


5

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


5

Hint #1: Hint #2:


4

One can view this problem as a dynamic programming problem with $3N$ subproblems. Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red....


4

I will show you how you can improve the computational complexity of Tom's solution. Let's rewrite his recursive relationship: $$RR(N) = RR(N - 1) + 2BR(N - 1)$$ $$BR(N) = RR(N - 1) + BR(N - 1)$$ You can express this relationship using matrix multiplication. $ \left( \begin{array}{cc} RR(N) \\ BR(N) \end{array} \right) % = \left( \begin{array}{cc} 1 & ...


4

The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank). The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this ...


4

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


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


3

Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible. Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum. Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ ...


3

Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all unaffected pairs, using $D'_j = D_j - TV_j$. The affect this has on the ratios is $$ \frac{D'_j - D'_{j+1}}{V_j - V_{j+1}} = \frac{D_j - TV_j - D_{j+1} + TV_{j+1}}{...


3

Every path must hit the top left and bottom right corners. Let $x$ be the minimal element among the remaining $NM-2$ elements. The lexicographically smallest path must go through $x$. If $x$ is at address $(i,j)$, this decomposes the original problem to two problems of the same form: one on an $i \times j$ matrix, and the other on an $(N-i+1) \times (M-j+1)$ ...


3

Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \{1,\ldots,K\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the ...


3

To complement Tom's answer: the coefficient of $x^n$ of the generating function $G(x)=\frac{1+x}{1-2x-x^2}$ is $$[x^n]G(x)=\frac{\sqrt{2}+1}{2}\left(\frac{1}{\sqrt{2}-1}\right)^n-\frac{\sqrt{2}-1}{2}\left(\frac{-1}{\sqrt{2}+1}\right)^n$$ so you have a closed form for the number of colorings. Note that this is the same as counting the number of (blue) ...


3

This answer fills the gap in the accepted answer by Tom van der Zanden, where the generating function is given by look-up magic without proper justification. This answer also produces the closed form of $RR(N)$. Here are the recurrence relations. $$\begin{align} RR(N)&=RR(N-1)+2BR(N-1) \tag{1}\\ BR(N)&=RR(N-1)+BR(N-1) \tag{2} \end{align}$$ ...


3

The problem is strongly $NP$-complete by reduction from 3-Partition. Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$. Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\...


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

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


3

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


3

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


2

Considering the "you have to visit all stations minimizing time", this is a Travelling salesman problem (see https://en.wikipedia.org/wiki/Travelling_salesman_problem). The additional constraints on sequencing correspond to scheduler optimization. I think the full problem is called "Sequential Ordering Problem". It is NP complete as both of its components. ...


2

From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c_1+\dots+c_k))$ to decompose, $O(\log n \cdot (c_1+\dots+c_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c_1+\dots+c_k))$ to finish up.


2

Yes, there is a pseudo-polynomial algorithm for this problem. Here is a wrong algorithm. Can you spot the biggest error? Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none. Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a ...


2

You can adopt the dynamic programming solution; the other solution looks harder to adapt. Given an array $A_1,\ldots,A_n$, we let $P_i$ be the maximum positive product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$, and we let $N_i$ be the minimum negative product of such a subsequence. If no such subsequences exist, we let $P_i = 0$ or $N_i = 0$. ...


2

Let $N(p,q)$ be the number of sequences containing $p$ many A's and $q$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $N(p,q) = 0$ if $q \geq p$ and $q > 0$. When $p = q = 0$ there are no non-empty prefixes, and so $N(p,q) = 1$. Suppose therefore that $p > q$, and consider any sequence ...


2

Your problem is essentially $(\min,+)$ matrix multiplication, also known as tropical matrix multiplication. This is because you're computing $$ C_{ik} = \min_j (A_{ij} + B_{jk}), $$ which is the same formula as usual matrix multiplication, with $\min$ replacing sum and $+$ replacing product. Usual fast matrix multiplication algorithms cannot be used for ...


2

I am afraid your approach does not work. Here is a counterexample. Box = 3 * 10 while Carpet = 4 * 8. One move is enough as you can fold the carpet by its width, reaching 2 * 8. If you fold the carpet by its length, 4 * 4 cannot fit into 3 * 10. Here is the answer. By the way, "length" refers usually to the longer side of a rectangle while "width" the ...


2

What are the subproblems of this problem when we try dynamic programming? Or what is the table? The subproblems are finding $dp[m][n]$, the largest area possible by $m$ non-overlapping rectangle which are under the first $n$ leftmost bars and, the rightmost of which contains the $n$-th bar. Let $dp2[m][n]$ be the the largest area possible by $m$ non-...


2

Suppose $BTC[H][N][L]$ shows the number of balanced trees with the height $H$, with $N$ nodes and $L$ leaves. Using the following formula, a dynamic programming algorithm can be developed for the problem: The recursive part: $\begin{align*} BTC[H][N][L] = \sum_{h=0}^H\sum_{n=0}^N\sum_{l=0}^L \qquad&(BTC[h-1][n][l]\times BTC[h-1][N-n][L-l])\\ +&(...


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