Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

  • The element 1 is in position 1, and element N must be at a position >= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
  • Some elements must be within a certain distance from each other on the line.
  • Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

  • The number of elements
  • A withinArray[][] where withinArray[x][y] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
  • An atLeastArray[][] where atLeastArray[x][y] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray1[3] = 10, withinArray[2][4] = 20, and atLeastArray[2][3] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.

share|improve this question

1 Answer 1

up vote 6 down vote accepted
+100

What you describe is a linear program. You can use the following formulation:

Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.

If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set $$ d_i+d_{i+1}+\cdots +d_{j-1} \le \ell^-_{ij}.$$ If they should be at least $\ell^+_{ij}$ away from each other you set $$ d_i+d_{i+1}+\cdots +d_{j-1} \ge \ell^+_{ij}.$$ Then maximize the objective function $\sum_{i=1}^{n-1} d_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.

share|improve this answer
    
But it should be mentioned that it's an integer LP (the variables must take integer values). –  usul Dec 6 '12 at 18:01
    
@usul: It doesnt say that the numbers have to be integers. Just that the solution should be an integer. In this case you just round up the LP solution. –  A.Schulz Dec 6 '12 at 18:06
    
It's not always the case that the rounded solution to an LP is a feasible solution to the integer version. For example, suppose I give as input that dist from A to B is > 10 and dist from B to C is > 10. An LP might place A at position 0, B at position 10.5, and C at position 21. I can't get a feasible solution by rounding. But it might be that here, you always can round to a solution if (for instance) you always use <= rather than <. In that case, we'd be fine. –  usul Dec 6 '12 at 20:01
    
Thank you for the neat formulations. If you can expand on how to get an end-to-end solution to this special case(i.e.,given the number of elements, two constraint matrices, output either -1, -2 or the actual distance), that'll be great. In fact I knew how to formulate the problem this way. I didn't want to use any LP solver, either. I just want someone who can guide me through solving it programmatically :) –  Terry Li Dec 7 '12 at 3:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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