Mixing
A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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_jleft(sum_i=0^j s_il_iright) $$
$$m_2 = max_jleft(sum_i=0^j
s_il_iright) $$
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.
algorithms
edited 3 hours ago
Yuval Filmus
183k12171333
asked 3 hours ago
Javant
1214
add a comment |Â
up vote
2
down vote
favorite
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_jleft(sum_i=0^j s_il_iright) $$
$$m_2 = max_jleft(sum_i=0^j
s_il_iright) $$
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.
algorithms
edited 3 hours ago
Yuval Filmus
183k12171333
asked 3 hours ago
Javant
1214
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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_jleft(sum_i=0^j s_il_iright) $$
$$m_2 = max_jleft(sum_i=0^j
s_il_iright) $$
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.
algorithms
edited 3 hours ago
Yuval Filmus
183k12171333
asked 3 hours ago
Javant
1214
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_jleft(sum_i=0^j s_il_iright) $$
$$m_2 = max_jleft(sum_i=0^j
s_il_iright) $$
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.
algorithms
algorithms
edited 3 hours ago
Yuval Filmus
183k12171333
asked 3 hours ago
Javant
1214
edited 3 hours ago
Yuval Filmus
183k12171333
asked 3 hours ago
Javant
1214
edited 3 hours ago
Yuval Filmus
183k12171333
edited 3 hours ago
Yuval Filmus
183k12171333
edited 3 hours ago
Yuval Filmus
183k12171333
183k12171333
asked 3 hours ago
Javant
1214
asked 3 hours ago
Javant
1214
asked 3 hours ago
Javant
1214
1214
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
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_iell_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.
answered 3 hours ago
David Richerby
62.5k1595179
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
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_iell_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.
answered 3 hours ago
David Richerby
62.5k1595179
add a comment |Â
up vote
2
down vote
accepted
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_iell_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.
answered 3 hours ago
David Richerby
62.5k1595179
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
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_iell_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.
answered 3 hours ago
David Richerby
62.5k1595179
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_iell_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.
answered 3 hours ago
David Richerby
62.5k1595179
answered 3 hours ago
David Richerby
62.5k1595179
answered 3 hours ago
David Richerby
62.5k1595179
answered 3 hours ago
David Richerby
62.5k1595179
62.5k1595179
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f98278%2fa-robot-arm-consisting-of-a-sequence-of-rigid-line-segments-l1-l2-ln-h%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password