1
$\begingroup$

Given a chain of $n$ links, each of length $a_1, a_2,..a_n$, where each $a_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists a $t \in [0, L]$ and $s_1,...,s_n \in \{-1, +1\}$ such that $t + \sum_{i=1}^j(s_ia_i)\in[0,L]$ for all $j\in\{0,..,n\}$.

For example, given $a_1 = 5, a_2 = 1, a_3 = 7, a_4 = 2, a_5 = 8,$ and $L = 9$ a possible solution could be $5+1-7-2+8$ such that the entire chain is contained within a space of $9$ units.

We need to provide an $O(nL)$ time algorithm to decide if the chain can be folded or not.

My approach: I tried a couple of different approaches:

  • Greedy algorithm: starting with the first link, check if it is greater than $L$, if yes then subtract $(s = -1)$ the second link from the first link. If it is still greater than $L$, the repeat. If it was not greater than $L$ initially, then add the second link to the first. This approach failed.

  • Tree approach: For every link, we can have $s=1$ or $s=-1$, this gives us $2^n$ possible arrangements. We can create a binary tree of size (layers) $n$ from this. But this method won't work due to the sheer size of the tree.

Any hints or guidance is appreciated.

I was also thinking that if $L$ is not given, is there a way to determine $L$ such that it is the best folding possible?

$\endgroup$
  • 1
    $\begingroup$ You have tried greedy algorithm and simple brute force. Have you tried dynamic-programming, the only approach that you have tagged the question with? $\endgroup$ – Apass.Jack Mar 5 at 12:33
  • $\begingroup$ I suggest studying the material at cs.stackexchange.com/tags/dynamic-programming/info and then try applying it to your situation. $\endgroup$ – D.W. Mar 6 at 1:57
  • $\begingroup$ Additionally, one can show that this problem is NP-Compete by reducing from 2-partition. Therefore, it is unlikely that it has a polynomial solution. (Note that $O(nL)$ is only pseudo-polynomial) $\endgroup$ – GBat Mar 6 at 6:29
0
$\begingroup$

The crux of the problem is to identify when we can extend a chain $t, s_1a_1, \cdots, s_ka_k$ to a longer chain?

Let $m$ be the length of that chain, i.e., $m= t +\sum_{i=1}^ks_ia_i$. If $m+a_{k+1}\in [0,L]$, then we can extend it with $+a_{k+1}$. If $m-a_{k+1}\in [0,L]$, then we can extend it with $-a_{k+1}$. Otherwise, the chain cannot be extended.

An approach by dynamic programming.

Create a $(n+1)$-row by $(L+1)$-column table $F$ (shorthand for foldable). All entries of $F$ are False initially. $F[k][j]$ will be true if there is a chain made from $a_1,\cdots, a_k$ with length $j$ and within space $L$.

Set $F[0][j]=\text{True}$ for all $j$, $0\le j\le L$. According to the analysis above, $F[k+1][j]$ is true in two cases.

  • $j-a_{k+1}\in [0,L]$ and $F[k][j-a_{k+1}]$ true.
  • $j+a_{k+1}\in [0,L]$ and $F[k][j+a_{k+1}]$ true.

In other words, we can fill all values at row $F[k+1]$ if we know all values at row $F[k]$.

If $F[n][j]$ becomes True in the end for any $j$, then we return yes. Otherwise, return no.

Explanation on 5, 1, 7, 2, 8

     0   1   2   3   4   5   6   7   8   9
t 0  T   T   T   T   T   T   T   T   T   T
5 1  T   T   T   T   T   T   T   T   T   T
1 2  T   T   T   T   T   T   T   T   T   T
7 3  T   T   T                   T   T   T
2 4  T       T   T   T   T   T   T       T
8 5  T                           T

The fourth row $F[3]$ corresponds to chains of the form $t$, $\pm5$, $\pm1$, $\pm7$. Their lengths can only be 0, 1, 2, 7, 8, 9. Now if you add $\pm2$ to them, you can get lengths

     2,  3, 4, 9, 10, 11 (for +2)
    -2, -1, 0, 5,  6, 7  (for -2)

So the possible lengths of chains of the form $t$, $\pm5$, $\pm1$, $\pm7$, $\pm2$ are 2, 3, 4, 9, 0, 5, 6, 7, which correspond to row $F[4]$.

How to find the smallest realizable $L$?

A binary search on integers in [a_1, 2M-1] should be a nice way to find the answer, where $M$ is the maximum value of $a_i$s. Binary search is feasible since, if $L$ is realizable, values larger than $L$ are realizable too.

Exercises

Exercise 1. (One minute or less) Show that the smallest realizable $L$ is at most $2M-1$, where $M$ is the largest of $a_i$s.

Exercise 2. Adjust the algorithm if $s_i\in\{-2,-1,1,2\}$ for all $i$ instead of $\{-1,1\}$.

$\endgroup$
  • $\begingroup$ Makes sense, but what I don't understand is why the rows and columns are n+1 and j+1. Wouldn't we just n rows and j columns? $\endgroup$ – hussain sagar Mar 5 at 20:43
  • $\begingroup$ $F[0]$ is the first row, which corresponds to the chain that has $t$ only. $F[n]$ is the last row, which corresponds to the chain that contains $s_na_n$. So there are $n+1$ rows. $\endgroup$ – Apass.Jack Mar 5 at 21:04
  • $\begingroup$ For each chain, its length can be $0, 1, 2, \cdots, L$. There are $L+1$ values. $\endgroup$ – Apass.Jack Mar 5 at 21:05
  • $\begingroup$ Could you also illustrate the algorithm you gave using the example I mentioned? I was thinking the first row would be {0, T, T, T, T} here the first element is 0 because we are not adding or subtracting 5 from itself. The second row would be {T, 0, T, T, T} as adding 1 to all the other elements doesnt exceed our L. The third row is where I am confused. When encountering the 7, how do we treat it? what would the third row look like? I know my understanding is flawed, sorry about that. $\endgroup$ – hussain sagar Mar 5 at 21:05
  • $\begingroup$ Please come to collabedit.com/pqagc for a chat. $\endgroup$ – Apass.Jack Mar 5 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.