# To check if a chain with $n$ links can be “folded” into a size at most $L$

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?

• You have tried greedy algorithm and simple brute force. Have you tried dynamic-programming, the only approach that you have tagged the question with? – John L. Mar 5 '19 at 12:33
• I suggest studying the material at cs.stackexchange.com/tags/dynamic-programming/info and then try applying it to your situation. – D.W. Mar 6 '19 at 1:57
• 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) – GBat Mar 6 '19 at 6:29

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[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$$ 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$$.

### 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\}$$.

• 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? – hussain sagar Mar 5 '19 at 20:43
• $F$ 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. – John L. Mar 5 '19 at 21:04
• For each chain, its length can be $0, 1, 2, \cdots, L$. There are $L+1$ values. – John L. Mar 5 '19 at 21:05
• 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. – hussain sagar Mar 5 '19 at 21:05
• Please come to collabedit.com/pqagc for a chat. – John L. Mar 5 '19 at 21:08