## Find maximal subset with interesting weight function

You are given $$n$$ rows of positive integers of length $$k$$. We define a weight function for every subset of given $$n$$ rows as follows – for every $$i = 1, 2, \dots, k$$ take the maximum value of $$i$$-th column (), then add up all the maximums.

For example, for $$n = 4$$, $$k = 2$$ and rows $$(1, 4), (2, 3), (3, 2), (4, 1)$$ the weight of subset $$(1, 4), (2, 3), (3, 2)$$ is $$\max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$$.

The question is, having $$m \leq n$$, find the subset of size $$m$$ (from given $$n$$ rows) with maximal weight.

The problem looks trivial when $$m \geq k$$, but how can one solve it for $$m < k$$? Looks like dynamic programming on subsets could work for small $$k$$, isn’t it? Are there other ways to do it?

Posted on Categories proxies

## Oriented spanning tree of a directed multi-graph with minimum weight

I have problem of finding the minimum spanning tree of a simple graph, but the result is restricted by additional two types of condition:

• There is a known root, which is s in the following example.
• We know directions of some edges if they are chosen. These edges are chosen yet, or the problem becomes a Steiner tree problem.

Note that numbers on edges are their weights. So we will get s -> b -> c -> a if a normal min spanning tree is applied, but the direction of edge ac is wrong. On the other hand, we cannot use Chu–Liu/Edmonds’ algorithm for spanning arborescence of directed graphs, because we don’t know and cannot infer the direction of edge bc. We can infer some edges’ directions according to the position of the root. For example, in the example, we know s -> b and s -> a.

## Oriented Spanning Tree

In the final section of spanning tree, Wikipedia, oriented spanning tree is mentioned and a paper [levine2011sandpile] is referred. The problem fits the setting. It says:

Given a vertex v on a directed multigraph G, an oriented spanning tree T rooted at v is an acyclic subgraph of G in which every vertex other than v has outdegree 1.

Note that the term "outdegree" is a bit confusing, which I think should be "indegree". But it doesn’t matter, because it just restricts the simple subgraph to be a directed tree with root being source or sink.

For edges (in the original simple graph) whose directions are unknown, we add two directed edges between two vertices with inverse directions. Then we find the oriented spanning tree of this multi-graph. But it is not clear to me how an algorithm can be implemented according to that paper.

• Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree
Posted on Categories proxies

## Does Improved Grab pull in the grappled regardless of weight?

Reviewing the choker I noticed the default strength is only 16. It caused me to wonder if an improved grab can pull a creature up in the air even if the strength does not have enough to carry (envision either a very heavy character or a magically strength reduced choker if you need to).

Improved grab itself seems silent on the issue, though it does mention weight when talking about moving the creature being grabbed which makes me suspect it would be limited:

It can even move (possibly carrying away the opponent), provided it can drag the opponent’s weight.

Posted on Categories Best Proxies

## What is Strahd von Zarovich’s weight in bat form?

This question concerns D&D 5e. The relevant ability, with my emphasis, is as follows:

While in bat or wolf form, Strahd can’t speak. In bat form, his walking speed is 5 feet, and he has a flying speed of 30 feet. In wolf form, his walking speed is 40 feet. His statistics, other than his size and speed, are unchanged… (Curse of Strahd page 240)

Simply put, what does Strahd weigh as a bat? Since size and weight are not the same, I would argue that he simply becomes a (very heavy) Strahd-weighted bat. Is this correct?

## Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be assigned to the nodes such that the graph satisfies the condition that for every edge its edge weight is exactly equal to maximum of two node values this edge is incident on.

Posted on Categories proxies

## Can Mage Hand drag more weight than it can carry?

I have been watching/listening to Chance’s D&D Spellbook, which highlights a potential ‘loophole’ in that the spell doesn’t list how much the hang can drag, say if attached via a rope that weighs less than 10lbs.

Normally a spell only does what it says, but carrying and dragging seem closely enough related that there might be some room for interpretation.

## Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

Assume for the regular knapsack problem we have additional information – maximal weight of every item – lets denote it as P. Using this information, I want to solve the problem using dynamic programming in $$O(n^2P)$$. Anyone have an idea how to solve it?

Posted on Categories proxies

## Does the limitation on the Cave Fisher’s Filament action include the weight of carried equipment?

The Cave Fisher from Volo’s Guide to Monsters (pg. 130) has an action called Filament which says:

One creature grappled by the cave fisher’s adhesive filament must make a DC 13 Strength saving throw, provided that the target weighs 200 pounds or less. On a failure, the target is pulled into an unoccupied space within 5 feet of the cave fisher, and the cave fisher makes a claw attack against it as a bonus action.

Emphasis mine. I imagine its pretty uncommon for a medium sized PC’s bodyweight and carried equipment combine for a weight under 200 lbs. Does the Cave Fisher’s attack limitation include the weight of carried equipment?

Posted on Categories Best Proxies

## Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :

$$\begin{cases} T(n) = \Theta(1), & \text{for small enough n ;}\ T(n) \leq T(a_n n + h(n)) + T((1-a_n)n+h(n)) + f(n), & \text{for larger n .} \end{cases}$$ Where:

• $$a_n$$ is unknown and can depend on $$n$$ but is bounded by two constants $$0.
• $$h(n)$$ is some “fudge term” which is negligeable compared to $$n$$ (say $$O(n^\epsilon)$$ for $$0\leq \epsilon < 1$$).

If $$a_n$$ was a constant, then I could use the Akra-Bazzi method to get a result. On the other hand, if the fudge term didn’t exist, then some type of recursion-tree analysis would be straight-forward.

To make things a bit more concrete, here is the recurrence I want to get the asymptotic growth of:

$$\begin{cases} T(n) = 1, & \text{for n = 1;}\ T(n) \leq T(a_n n + \sqrt n) + T((1-a_n)n+\sqrt n) + n, & \text{for n \geq 2 } \end{cases}$$ Where $$\frac{1}{4} \leq a_n \leq \frac{3}{4}$$ for all $$n\geq 1$$.

I tried various guesses on upper bounds or transformations. Everything tells me this should work out to $$O(n\log(n))$$ and I can argue informaly that it does (although I might be wrong). But I can only prove $$O(n^{1+\epsilon})$$ (for any $$\epsilon>0$$), and this feels like something that some generalization of the Master theorem à la Akra-Bazzi should be able to take care of.

Any suggestions on how to tackle this type of recurrence?

Posted on Categories proxies

## Does falling damage by weight get limited to 20d6?

I’m trying to build a character that does damage by dropping on people. (It’s a baleen whale with grafted wings.) I was reading the SRD on falling damage and it has this very confusing line about falling objects:

For each 200 pounds of an object’s weight, the object deals 1d6 points of damage, provided it falls at least 10 feet. Distance also comes into play, adding an additional 1d6 points of damage for every 10-foot increment it falls beyond the first (to a maximum of 20d6 points of damage).

Is the total falling damage limited to 20d6 or just the falling damage from height (which would make more sense since falling damage is limited because of terminal velocity)?