Sat 30 November 2013

The Problem

Let's describe the problem briefly here. Given a string a necklace composed with Red, Blue and White beans, we are going to find the maximum number of beans we can collected if we can choose to break the necklace at a certain point. By "maximum number of beans we can collected", I mean starting from the break point, we collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end.

What's special is that when collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color.

The Solution

At first I think I can just use the simple-minded approach which is to try to break the necklace at each point and calculate how much beans I can get at that certain point. When this is done from start to end, we are able to obtain the maximum number of beans we can collected.

However, I have a feeling that a dynamic programming algorithm would be much more challenging and fun. So this is my approach of dynamic programming. The main idea here is to iterate the ring once and we can dynamically sum up the numbers of last two same color collections. Finally, the maximum of the sums is the answer.

We are going to duplicated the necklace string and concatenate one to the other. For instance, if the necklace is rbwwrbbb, it will be made rbwwrbbbrbwwrbbb. The reason for this is that necklace is actually a ring, not a list. By doing this, we provide the illusion for the program that we are iterating in the ring.

Supposing we only have red and blue beans, while iterating the string from head to tail, we accumulate beans with same color, and if we have encountered a different color from what we are collecting now (let's call it a "color change"), we will store the current number of same color beans and start accumulate beans with the other color. In the meanwhile of "color change", we are going to sum up the past two numbers of different color beans collection, and compare it to the maximum number, if the sum is greater, replace the maximum number with the sum.

For instance, when we encounter the 5th bean "r" in rrbbrrrb, we have already stored the number of first 2 "r"s, 2, and the 3rd and 4th beans "b"s, 2, so now we got 2+2=4 to be our maximum. If we encounter the 8th bean "b", this "color change" yields sum=2+3=5, and replace maximum with 5.

Things got more complicated when white color joins. When we are iterating on "w" beans, we add the count to the current collection, assuming we are coloring these "w" beans to the color we are collecting. But when we encounters a "color change" (rw...b or bw...r), after maximum is compared to the sum, we are going the color the before collected white beans into the new color, maximizing the next collection.

For instance, brwwwbr will be viewed as brrrrbr when we are at the 5th bean, but it becomes brbbbbr when we get to the 6th bean.

Conclusion

By sticking to the above three principles, we can dynamically sum up the numbers of last two same color collections, which can find the answer in O(n).

Source Code

#include <stdio.h> 
#define BUF_SIZE 1024 
int main () { 
    FILE fin = fopen ("beads.in", "r"); 
    FILE fout = fopen ("beads.out", "w"); 
    int size; 
    int it_len; 
    int i; 
    int state = 3; 
    char beads[BUF_SIZE]; 
    int answer = 0; 
    int sum1 = 0; 
    int sum2 = 0; 
    int w_combo = 0; 
    int w_walk = 0; 
    if(fin) 
    { 
        fscanf(fin, "%d\n", &size); 
        fgets(beads, BUF_SIZE, fin); 
        it_len = size * 2; 
        memcpy(&beads[size],&beads[0],size); 
        for(i = 0; i < it_len; i++) 
        {
            if(beads[i] == 'r' || beads[i] == 'b')
            {
                sum2 = 1;
                i++;
                break;
            }
            sum2 = size;
        }
        for(; i < it_len; i++) 
        { 
            if(beads[i] == 'w')
            {
                w_walk = 1;
                w_combo = 1; 
                sum2++;
                beads[i] = beads[i-1];
            }
            else if(beads[i] == beads[i-1])
            {
                sum2++;
            }
            else
            {
                if((sum1+sum2) > answer)
                answer = sum1+sum2;
                sum1 = sum2;
                sum2 = 1;
                if(w_walk)
            {
                sum2 += w_combo;
                sum1 -= w_combo;
            }
                w_walk = 0;
                w_combo = 0;
            }
        } 
    } 
    if((sum1+sum2) > answer) 
        answer = sum1+sum2; 
    if(answer > size) 
        answer = size; 
    if(fout) 
        fprintf (fout, "%d\n", answer); 
    return 0;

}

Category: Algorithm Tagged: C USACO Algorithm

Comments