Introduction

This is an analysis of PROB Broken Necklace, one of USA Computer Olympiad’s training problems.
Just doing some disposal on my old stuff.

Description

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:

            1 2                               1 2
        r b b r                           b r r b
      r         b                       b         b
     r           r                     b           r
    r             r                   w             r
   b               r                 w               w
  b                 b               r                 r
  b                 b               b                 b
  b                 b               r                 b
   r               r                 b               r
    b             r                   r             r
     b           r                     r           r
       r       r                         r       b
         r b r                             r r w
        Figure A                         Figure B
                    r red bead
                    b blue bead
                    w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b’s and r’s, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then 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 (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.

Analysis

Given an input string ‘wwwbbrwrbrbrrbrbrwrwwrbwrwrrb’, we concatenate it with itself, result in ‘wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb’. This trick, working on handling minus or over-length index is easier.

1. Brute force solution.

   For each index $a_i$ as a start, if $a_{i+1}$ can be picked into the longest substring, we pick it then do this again on $a_{i+1}$. Note that, if $a_i$ is w, we must treat it as b and r, one by one. We do N times of picking attempt for each $a_i$. Therefore complexity is O(N²). Just a straight forward solution.

2. DP solution.

   We denote substring composed by successive r, which ends at index $i$ to $t_{i,r}$.

Similarly, we denote substring composed by successive b, which ends at index $i$ to $t_{i,b}$.

On the other hand, we denote substring composed by successive r, which starts at index $i$ to $s_{i,r}$.

And substring composed by successive b, which starts at index $i$ to $t_{i,b}$.

For each index $a_i$, $\max \{s_{i,r}, s_{i,b} \} + \max \{t_{i,r}, t_{i,b} \}$ is the length of longest substring if we break it at index $i$. We do this for N times, the greatest one is the answer. Complexity of this algorithm is O(n).

Source Code of DP Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/*
ID: viennak1
PROB: beads
LANG: C++
*/

// Section 1.1 PROB Broken Necklace

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <numeric>
#include <fstream>
#include <iostream>
#include <utility>
#include <iomanip>
#include <stack>
using namespace std;

int N,res;
int ENDS[700][2],STARTS[700][2];
string s;
int main(){
    ofstream fout ("beads.out");
    ifstream fin ("beads.in");
    fin>>N; fin>>s;
    int L=s.length();
    s=s+s;
    if(s[0]=='r') ENDS[0][0]=1;
    else if(s[0]=='b') ENDS[0][1]=1;
    else ENDS[0][0]=ENDS[0][1]=1;
    for(int i=1;i<L*2;i++){
        if(s[i]=='r') ENDS[i][0]=ENDS[i-1][0]+1;
        if(s[i]=='b') ENDS[i][1]=ENDS[i-1][1]+1;
        if(s[i]=='w') ENDS[i][0]=ENDS[i-1][0]+1,ENDS[i][1]=ENDS[i-1][1]+1;
    }
    if(s[2*L-1]=='r') STARTS[2*L-1][0]=1;
    else if(s[2*L-1]=='b') STARTS[2*L-1][1]=1;
    else STARTS[2*L-1][0]=STARTS[2*L-1][1]=1;
    for(int i=2*L-2;i>=0;i--){
        if(s[i]=='r') STARTS[i][0]=STARTS[i+1][0]+1;
        if(s[i]=='b') STARTS[i][1]=STARTS[i+1][1]+1;
        if(s[i]=='w') STARTS[i][0]=STARTS[i+1][0]+1,STARTS[i][1]=STARTS[i+1][1]+1;
    }
    for(int i=0;i<2*L-1;i++)
        res=max(res, max(ENDS[i][0],ENDS[i][1])+max(STARTS[i+1][0],STARTS[i+1][1]));
    if(res>L) fout<<L<<endl;
    else fout<<res<<endl;
    return 0;
}