All Questions
Tagged with trees dynamic-programming
26 questions
2
votes
1
answer
212
views
Tree algorithm - arrange integer array numbers to form largest number
I have solved leetcode's Largest Number.
I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
- 123
1
vote
0
answers
74
views
How do I optimally fuse nodes in a tree structure?
I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
- 239
0
votes
0
answers
43
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
1
vote
0
answers
123
views
Find maximum number of vertex-disjoint paths of length $k$ in a tree with no restrictions for the paths
I am working currently on Path-Packing problems and found this Book:
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
My question is about exercise 23b on page 184.
Here is ...
- 11
0
votes
0
answers
107
views
Finding the diameter of a N-ary tree graph, without using BFS
As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph.
This must be done in linear time.
The problem states that the graph is undirected ...
- 377
0
votes
2
answers
214
views
Find the largest MinHeap subtree in a given Tree
We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in ...
- 31
0
votes
0
answers
32
views
Find set of vertices of max size under some restrictions [duplicate]
I've faced a problem and I don't know what approach I must follow, dynamic programming or greedy method, so here is the question.
Question: Given a directed tree $T=(V,\ E)$. We're required to find a ...
- 479
4
votes
2
answers
350
views
Given a list of integers, how to find the smallest positive integer such that I can get all the integers in the process of dividing it by 2?
The title could be a little bit confusing, and it is not easy to summarize it within a sentence, therefore I will explain it in detail below. If you have any thoughts on optimizing and rephrasing the ...
- 41
1
vote
1
answer
354
views
Minimum cost of "signal" cover in a tree with DP
I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ ...
- 47
3
votes
0
answers
567
views
Facility location on a tree
Question:
Given a tree representing a neighbourhood where each node is a house.
Assign an antenna to each node such that the whole tree is covered.
An antenna of strength 0 can only ...
- 31
4
votes
2
answers
1k
views
Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems ...
- 227
2
votes
0
answers
115
views
Join Order Optimization
Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player
What is the optimal join order?
Based on the schema on the following picture:
I am suppoused (and that's what I tried) to use ...
user97496
0
votes
1
answer
237
views
Dynamic Programming Problem on Tree
Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
- 51
1
vote
0
answers
478
views
Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))
So this is a question within a bigger question for which I've reduced to this so far:
If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
- 11
0
votes
1
answer
159
views
Transform 2D range query matrix into segment tree to make memory usage lower
Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x_1, y_1, x_2, y_2)$ which will return the number of ones in the sub-...
- 1,428