Uva 10364 Tell if it is possible to use sticks of varying lengths to make a square [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 9 years ago.

Improve this question

I have been stuck on this uva problem from a long time now.

Abridged problem statement : Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? There are a maximum of 20 sticks and each stick has a length less than 10000.

There are different solutions possible for this problem. One of them is a backtracking solution explained here. But there exists other dynamic programming solutions explained here, here and here with a better running time. But I can't understand what approach they are using. Please help me understand the dp algorithm.

Answer 1

If you are not familiar with dynamic programming over subsets, I suggest you read about it first. This link can help, but there may be better tutorials out there.

Back to the given problem, since M is no more than 20, the following 2^M×M approach will probably work.

For each of the 2^M subsets of the given sticks, we know the total length of the sticks in that subset. We also know the total length of all the given sticks and thus the length of the square side. We construct the square by laying sticks on its sides. Let us fix the order in which we construct our square: we start at the upper left corner and move along the square border in clockwise direction, laying sticks on the way and leaving no gaps. So, first we fully construct the upper side (from left to right), then the right side (top-down), then the lower one (right-to-left) and finally the left one (bottom-up). Whenever the distance to the next square corner in our traversal is L, we can't lay a stick of length greater than L; at least not until we reach that corner using other sticks. Now, the question is: can we order the sticks in such a way that the square can be constructed by our procedure?

There are M! different orders in which we can try to lay the sticks. But, if we lay sticks one-by-one, when choosing the next stick, all that we are concerned with is the set of sticks already laid, not their particular order. This observation leads us to considering only 2^M subsets which is way smaller than M! orders.

Next we define subproblems of the problem defined before. For each subset of sticks, the question is: can we order the sticks in such a way that all of them can be laid sequentially by the rules of the above procedure? In other words, can we construct a "valid prefix" of the square traversal, as it is defined above?

We will say a subset of sticks is good if the answer to the above question is "yes", and bad otherwise. Sure, the empty subset is good. In the end, we are interested in whether the whole given set of sticks is also good. To find that out, we can process the subsets in natural order (for M=3, that would be 000, 001, 010, 011, 100, 101, 110, 111 where 1s correspond to sticks in the subset). For each new non-empty subset S, it is good if and only if some of its "immediate subsets" T (S without exactly one element - say a stick of length X) is good, and T can be extended by that stick of length X according to the rules of our construction procedure (that is, laying a stick of length X, we won't have to bend it around some corner).

What's left is implementation details. For each subset, either store or calculate the total length of the sticks in it and find the distance to the next corner L. If this subset is good, it can be extended only by sticks having two properties: (1) length no more than L and (2) not already in the subset.