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 ?