5
$\begingroup$

Problem :

We are given a stick partitioned into n - equal parts. Each of these parts has a weight, let's say x. Number of times x appears as weight of some part is guaranteed to be even.

For example consider the following stick with 6 parts -

1 2 2 1 3 3

So the stick has n parts, with weight of first part being 1, of second being 2, and likewise. Note that each weight appears even number of times.

Now, we need to cut the stick across these n partitions, and divide the parts into two users, and those two should have same weight in the end.

We divide the parts as follows -

Let's say I made first cut at y1, then from starting till y1 - this part goes to user1. Now, we make another cut at y2. Then from y1 to y2 goes to user 2. And so on alternatively.

So we need to find the minimum number of cuts in which we can do this fair division.

I couldn't find a polynomial time algorithm. And, problem appears to be NP - Hard. So, any good approximation algorithm for this problem ?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ I think the question is stated adequately. It would be nice with some motivation though! $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 5, 2011 at 15:05
  • 1
    $\begingroup$ I agree with Kristoffer, could you please explain why this problem is interesting and what is the motivation behind this problem? $\endgroup$
    – Kaveh
    Jan 6, 2011 at 0:38
  • 5
    $\begingroup$ I cannot understood the precise problem even after I read your additional post (which should not have been an answer). When you say that the two users “should have same weight,” do you mean that they have the same total weight or the same multiset of weights? In the case of latter interpretation, Yoshio’s answer gives a reference to an NP-completeness result. $\endgroup$
    – Tsuyoshi Ito
    Jan 6, 2011 at 0:47
  • 5
    $\begingroup$ By using the appropriate set of weights $(4^i)$, $i=1 \ldots n$, the reference in Yoshio's answer gives an NP-completeness results for the earlier problem, too. $\endgroup$
    – Peter Shor
    Jan 6, 2011 at 17:26
  • $\begingroup$ @Peter: Nice! - $\endgroup$
    – Tsuyoshi Ito
    Jan 7, 2011 at 0:37

3 Answers 3

Reset to default
10
$\begingroup$

I'm not sure if I understand the problem specification correctly, but the problem looks a special case of the paint shop problem. In that context, there is an NP-hardness result.

The main reference is: P. Bonsma, Th. Epping, and W. W. Hochstättler, Complexity results on restricted instances of a paint shop problem for words. Discrete Applied Mathematics 154 (2006) 1335-1343. http://dx.doi.org/10.1016/j.dam.2005.05.033

The abstract says as follows.

We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.

This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.

Improve this answer
$\endgroup$
1
$\begingroup$

This is the partition problem, here's a starting point.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Not Exactly I guess. Sounds like partitioning but I don't think this is any where equivalent to it. Here we know that every weight will come out even number of times. Here it matter how you place the cuts ? While in that it doesn't at all. Here it is all about where to place the cuts. (and how?) $\endgroup$
    – Prof. Cees Duke
    Jan 5, 2011 at 14:44
  • 2
    $\begingroup$ @Daniel: No! For these instances we are guaranteed to be able to patition, since each weight occurs an even number of times. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 5, 2011 at 15:04
  • 1
    $\begingroup$ @Kristoffer, good call! The grammar threw me off. :/ $\endgroup$
    – Daniel Apon
    Jan 5, 2011 at 15:08
0
$\begingroup$

I missed one point in the problem statement perhaps - Yes, the weight should be equal. But, we also add this extra constraint that both should have same number of weighted cuts that is -

consider the given example - 1 1 2 2 3 3

Then it is necessary for both to have stick parts with weight (1,2 and 3) in the end. Weight will automatically be the same.

@Oleksandr - Your algorithm is suboptimal. Let's just consider the example give by Suresh - 2 2 2 2 2 2 4 4 4 4 2 2. Here the greedy algorithm will give 3 cuts , at 4,8, and 10. But it is not optimal. We can solve it in two cuts, one at 2 and other at 8.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Please, add the first part to your post. You mean both players should have the same number of parts of the stick? $\endgroup$
    – Oleksandr Bondarenko
    Jan 5, 2011 at 21:16
  • $\begingroup$ So there should be even number of cuts? $\endgroup$
    – Oleksandr Bondarenko
    Jan 5, 2011 at 21:22
  • 2
    $\begingroup$ I agree. please add this to the problem specification. $\endgroup$
    – Suresh Venkat
    Jan 5, 2011 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.