A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively

Question

Hi I am a Computer Science student attempting to solve this problem for extra credit. Problem is I am unsure what this algorithm is asking for as the language is a bit hard for me to follow:

Imagine that you have a robot arm consisting of a sequence of rigid line segments $L_{1}, L_{2}, \dots , L_{n}$ hinged together consecutively. The lengths of the line segments $l_{1}, l_{2}, \dots , > l_{n}$ are positive integers. You may rotate freely around the hinges and the line segments are allowed to cross over. Our goal is to pack in the line segments into one line segment as compactly as possible. More precisely, given positive integers $l_{1}, l_{2}, \dots , l_{n}$ (and $l_{0} = 0)$ and a sequence of $\pm1$’s, $s_{0}, s_{1}, \dots , s_{n}$, where $s_{i} = 1$ or $s_{i} = −1$, $0 ≤ i ≤ n$, define

$$m_1 = \min_j\left(\sum_{i=0}^j s_il_i\right) $$ $$m_2 = \max_j\left(\sum_{i=0}^j s_il_i\right) $$ where ($0 ≤ j ≤ n$). Find $\min_s (m_{2} − m_{1})$, where the minimum is taken over all sequences $s = (s_0, s_2, \dots , s_n)$.

The goal is for me to write an algorithm that solves this problem. But I am not entirely sure what the question is asking. My understanding is drawn below:

The arms shall be compacted as much as they can be such the vertical height of the extended arm is minimized. But I don't understand what the $s_0, s_1,\dots, s_n$ sequence is for? And if someone could describe in layman's terms what the sequences $m_1$ and $m_2$ are asking for that would be great.

Answer 1

The $s$'s tell you which way each segment of the arm is pointing: $s_i=+1$ if the $i$th segment points up and $s_i=-1$ if the $i$th segment points down.

This means that $S_j := \sum_{i=0}^j s_i\ell_i$ is the distance of the end of the $i$th segment from the pivot. So $\min_j S_j$ and $\max_j S_j$ are the height of the lowest and highest points of the arm when it's folded in the way that $s_0, \dots, s_n$ describe.