You are given a circular necklace containing n beads. Each bead maybe black or white. You have to rearrange the beads so that beads of the same color occur consecutively.
The only operation allowed is to cut the necklace at any point, remove some number of beads from both ends and put them back in any order, and join the cut ends. The cost of this operation is the number of beads removed. Any number of such operations can be used. You have to find a sequence of such operations with minimum total cost for a given initial distribution of beads.
For example, if the initial string is wbwbwb, this can be done by a single operation of cost 4, or two operations of cost 2 as shown.
Describe a polynomial-time algorithm for this problem; with short proof of correctness. You get points only if you match (or better) the judge solution's time complexity.
The only operation allowed is to cut the necklace at any point, remove some number of beads from both ends and put them back in any order, and join the cut ends. The cost of this operation is the number of beads removed. Any number of such operations can be used. You have to find a sequence of such operations with minimum total cost for a given initial distribution of beads.
For example, if the initial string is wbwbwb, this can be done by a single operation of cost 4, or two operations of cost 2 as shown.
Describe a polynomial-time algorithm for this problem; with short proof of correctness. You get points only if you match (or better) the judge solution's time complexity.
No comments :
Post a Comment