USACO - Broken Necklace

I recently completed a mathematical problem "Broken Necklace" on USACO. The abridged problem statement is described below:

We have a necklace that contains n (3 <= n <= 350) beads of 3 colors: red (r), blue (b) and white (w). If we break the necklace at some position i, the necklace will clearly have 2 end points x and y. Starting from each of the end points, we can collect similarly colored consecutive beads from each end point (e.g. blue from one end, red from the other) until we reach a bead of a different color. The only exception is, white beads can take on any color.

Example:

Initially, we have this necklace (sorry for the bad formatting):

x y 

r b b r

r      b

r      r

r      r

b     r

b     b

b     b

b     b

r      r

b     r

b     r

r      r

 r  b  r

We break it at the point between x and y, obtaining the following configuration:

                                                

x brbrrrbbbrrrrrbrrbbrbbbbrrrrb y

In this case, we can only collect 1 blue bead from each end. but if we had this configuration instead:

                                                 

x rbrrrbbbrrrrrbrrbbrbbbbrrrrbb y

We can collect 1 red bead starting from x and 2 blue beads starting from y.

The goal is to maximize the total number of beads collected.

---

My analysis:

Simple (naive) solution:

It does not take an expert to see the naive solution (which is enough in this case). This solution would be, for each break position i (1 <= i <= n), count the number of beads we can collect from its left (starting from x) and right (starting from y) under the given constraints. Then our answer would be the maximum number of beads for all i. The complexity of this solution is O(n^2) which incurs (a constant factor of) 350^2 = 122500 operations. This number seems large but it is peanuts to a modern computer which can execute approximately 1e8 (100 million) operations/sec!

Efficient solution:

The efficient solution requires one to observe that there is repeated/redundant work being done by checking if the same beads have a particular color. In order to avoid this, we need some counting strategies and an algorithmic optimization technique called dynamic programming. Before we jump into the details, it would be easier to divide the problem into 2 parts: counting the beads collected to the left of some position i and counting the beads collected to the right of i.

We define our problem's states as:

dpbleft[i] = Maximum number of blue beads we can collect to the left of some break position i.

dpbright[i] = Maximum number of blue beads we can collect to the right of some break position i.

dprleft[i] = Maximum number of red beads we can collect to the left of some break position i.

dprright[i] = Maximum number of red beads we can collect to the right of some break position i.

Note that we start collecting beads at position i in the necklace. So a more precise way to describe each state would be maximum number of blue/red beads we can collect to the left/right of some break position i (inclusive).

How do we calculate each state?

For simplicity, we assume that we will collect beads to the left first (the same strategy applies collecting beads to the right). Let's partition the counting into 2 parts: maximum number of beads that we can collect assuming that the left adjacent bead is a blue (dpbleft) or red bead (dprleft) (remember that white beads can take on any color). Now we can easily calculate the answer for each case using a simple loop. We will do the same for calculating bead collection to the right.

Now we need to put the states together and get our answer. Merge the states for dpbleft and dprleft into one - what is the maximum number of beads we can collect from the left of some break position i? We do the same for the states that record the right-hand side bead collection.

This reduces the entire problem to the same as that for the naive solution, except that we do not have to keep counting for each position i because we have already pre-computed the answers for each side. So all we need to do is to sum the numbers for each side and return the maximum sum for all i. The complexity of this solution is O(n). Hence, the total number of operations would be simply (a constant factor of) 350. This would work even for n <= 1e6.

Caveat:

A caveat of the above-mentioned solutions would be that we may double-count beads to the left and right (consider the case where all beads are of the same color). So the correct answer would be min(answer, necklace length).

Here is the link to the efficient solution, problem statement and test-cases if you want to try it out yourself. Let me know if you have any questions by posting a comment.

That's all for now! The next time I will probably be writing about algorithmic analysis (using Big O notation) and how to tell if an algorithm can pass a given time limit.