2
This is simply a tree, where all elements are unique. I'm not aware of any special name.
2
I'm not sure why you think this solution is invalid. It implies that
$$
\sum_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n,
$$
and in particular,
$$
\sum_{i=0}^n 6^i(n-i)^3 = \Theta(6^n).
$$
You can also check it for particular values of $n$.
For example, when $n = 0$ you clearly get zero, and for $n = 1$ you get
$$
\frac{-125-450-630+366 \cdot 5}{625} = 1 = ...
2
It comes from set theory. To see that these ideas were around before computers and that they were explicitly called trees consider the following famous tree. The convention set theorist sometimes use (some use use the convention you gave) is the opposite (the root $\hat{0}$ is the smallest, i.e. $\hat{0}<x$ for all $x\neq \hat{0}$, not the biggest ... ...
1
Merge all hotspots into a single node $h$ (Instead of a tree - the input is now an undirected graph). The problem can now be represented as follows:
Given an undirected graph $G$ and a node $h$ (the merged hotspot), we want to answer queries $Q(c, e)$:
$Q(c, e)$: Given node $c\in G$ and edge $e\in G$, return $\mathrm{distance}(h, c)$ in $G\setminus \{e\}$.
...
1
You can use the top-tree data structure.
It maintains a forest $F$ on $n$ nodes and supports (among others) each of the following operations in $O(\log n)$ time per operation:
Given an unmarked vertex $v$ mark $v$.
Given a marked vertex $v$ unmark $v$.
Given two vertices $u,v$ that belong to two different trees in $F$, add the edge $(u,v)$ to $F$ (thus ...
1
The data structure that is the closest to what's needed here seems to be the rose tree. It has all the properties except the uniqueness constraint.
There is also an implementation of this data structure in the containers package, where the implementation looks like this:
data Tree a = Node {
rootLabel :: a,
subForest :: Forest a
}
type ...
1
The greedy algorithm does not always work. Example: $S_1 = \langle 3, 1, 1,1\rangle$, $S_2 = \langle 2, 2,2\rangle$, $W=6$.
In general, let $S_1 = \langle x_1, \dots, x_k \rangle$ and $S_2 = \langle y_1, \dots, y_h \rangle$. I will assume that individual book weights are positive integers.
To solve your problem optimally you can use a sliding-window ...
1
The proof seems correct to me.
1) The base case proves the claim when the height of the subtree rooted at $x$ is $0$. The inductive step proves the claim for every subtree rooted at $x$ of positive height $h$ assuming that the claim is true for all subtrees of heights from $0$ to $h-1$. So the inductive step for $h=1$ is able to prove the claim for all ...
1
An exact but somewhat complicated $O(n\log n)$ algorithm
This problem intrigued me, and the solution I've come up with uses a strategy that's totally new to me (I doubt it's new to the world -- if anyone knows of other problems that can be solved "this way", let me know!). This algorithm allows negative and/or fractional edge costs, and operates directly on ...
Only top voted, non community-wiki answers of a minimum length are eligible
