Partitioning a segmented stick 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 ?
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.