3 votes
Accepted

Formal Proof on why Greedy isn't working on one Particular Problem

To prove that the greedy algorithm is not optimal, it suffices to give one counterexample, i.e. one problem instance $nums$ and $mult$ such that it is possible to obtain a value that is larger than ...
user avatar
2 votes
Accepted

Subdivide a graph into non-crossing triangles with maximum edge weight

With proper classification and memoization, an approach by dynamic programming runs in $O(n^3)$ time, where $n=|V|$. That seems efficient enough considering there are $n(n-1)/2$ edges. Assume $n\ge 3 ...
user avatar
  • 32.9k
2 votes
Accepted

Largest number of disjoint paths of length $k$ and maximum reward in a tree

Given a vertex $v$, let $r(v)$ denote $v$'s rewards, let $C_v$ be the set of $v$'s children, and let $T_v$ denote the subtree of $T$ rooted in $v$. Given a vertex $x$ at depth $d_T(x) \ge k$ in $T$, ...
user avatar
  • 22.7k
2 votes

Counting the number of parenthesization

Suppose you have $n$ matrices $M_1, M_2, …, M_n$. The product of all matrices is $M_1\times M_2\times…\times M_n$ and since the matrix product is associative, there is no need for parentheses from a ...
user avatar
  • 6,972
2 votes

Find the largest MinHeap subtree in a given Tree

I think this can be done quite easily in linear time: a heap is an almost complete tree that satisfies the heap property. An almost complete tree is one of the following: a leaf (a single node); a ...
user avatar
  • 6,972
1 vote

Counting the number of parenthesization

The split in a product is between the two outermost pairs of parantheses. For example, in $((a*b)*(c*d))*(e*f)$, the split is between the $d$ and $e$ because the last multiplication that is performed ...
user avatar
1 vote

Optimizing an arbitrary function of 10 variables

There are only 19448 combinations of $x$'s that meet the constraints. If $f$ is arbitrary, the best you can do is enumerate all 19448 combinations and see which leads to the largest value of $f$. ...
user avatar
  • 140k
1 vote

Solve modified knapsack problem using dynamic programming

Let $C \ge 1$ be the capacity of the knapsack and let $G_1, \dots,G_k$ be your groups, where each group is a non-empty collection of items, i.e., $G_i = \{ x^{(i)}_1, x^{(i)}_2, \dots \}$. Groups are ...
user avatar
  • 22.7k
1 vote

Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?

It is better to ignore the confusing text below, which was added to that page of Wikipedia by an anonymous user on "20 August 2020", as shown on this comparison page. However, if the ...
user avatar
  • 32.9k
1 vote

Find the largest MinHeap subtree in a given Tree

Perform a level order traversal of $T$, and store the visited nodes in an array $A$. Let $S$ be an array such that $S[i]$ is the size of the min-heap rooted at node $A[i]$. Initially the values of all ...
user avatar
  • 1,257

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