How to solve the Broken Necklace Problem where we have to iterate forwards and backwards

Question

This problem has been asked here but that's not what I am looking for.

Greetings everybody! I was solving the broken necklace problem which is a USACO Problem. Here is the problem:

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.

Example: For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. 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 string that represents this configuration can include any of the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.

Actually I tried to solve the problem using C++. However, I seem to be getting a wrong answer in case 3 which is

77 rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

My code outputs 72 but the answer is 74. I can't even see how the answer is 74 (don't we have to subtract that 5 b block to get 77-5=72) How do we get 74? How is my code wrong and which cases am I missing? I can't seem to be able to debug this code...

Any helps would be appreciated. Thank You.

#include <bits/stdc++.h>
using namespace std;

int main(){
//For faster I/O
ios::sync_with_stdio(0);
cin.tie(0);
//read and write files
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
//get as input all the bead colors
int N; cin >> N;
char beads[N]; for(int i=0;i<N;i++) cin >> beads[i];

//the max amount of stuff we can get
int maxCount = INT_MIN;
//some helper variables we'll need later
int currCount = 0; int counter1 = 0; int counter2 = 0; char currColor = 'w';

for(int i=0;i<N;i++){
    //set counter1 and counter2 both to 0
    counter1 = 0; counter2 = 0;
    //the iterator
    int j;

    //First loop - forwards
    //---------------------
    j = i;
    currColor = beads[i];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==N-1) j=0;
        else j++;
        counter1++;
        if(counter1 > N) break;
    }

    //Second loop - backwards
    //-----------------------
    j = (i>0) ? i-1 : N-1;
    currColor = (i>0) ? beads[i-1] : beads[N-1];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==0) j=N-1;
        else j--;
        counter2++;
        if(counter2 > N) break;
    }

    //get the current count and get max value
    currCount = counter1 + counter2;
    maxCount = max(currCount,maxCount);
}

if(maxCount > N) cout << N;
else cout << maxCount;

cout << "\n";

return 0;
}

Answer 1

I have solved this problem myself using C++ (my solution is available here).

I won't give debug your code for you, but I'll give you some hints of how to approach this problem.

• You have the right idea that you need to traverse the necklace both forwards and backwards. It might be helpful to create two helper functions that traverse cyclically to the left and to the right (use modular arithmetic)

• But where do you start collecting beads from? Just try all possible starting points. Since the bounds on N are relatively small, in your main, you can just have another for-loop that runs through i = 0, 1, ... N - 1, where i denotes the starting point of your bead-collection process. Of course this means that your two helper functions will need to take in a starting index from which beads will begin to be collected.

• Now what exactly do the left/right traversal functions do? Given a start index and the beads, we should first determine which bead we're collecting (so increment the starting point until we're no longer at a white bead). Then we can just use another while-loop and increment count until we cannot go any further. Be careful for infinite loops here (consider a necklace with all beads of the same color).

Let me know if you have any questions.

Answer 2

For your code, I fixed it up a bit. But there is no guarantee that it will work for all cases. The reason why 74 is the correct answer is because you are allow to have the color change from "r to b" or "b to r" one. So for example, with "rrrrbbb", you can grab all 7 beads. Now when it come "w", it could be either "r" or "b". Thus, with this string.

rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

You can grab either b and the w behind it or in front of it but not the r. If you grab the first b then neither can you grab the second b. Thus, if grabbing either way, you will have left 1r, 1w, and 1b.

For why your code did not work, you did not allow the color to change from r to b for one. I fixed your forward code, test your code, but I have not test your backward code. It will work for the string below, but who know about all the other strings.

With this, I give you a spoiler code. For my code, it passed the submission but I am still trying to efficient it so I may modify it in the future.

Nonetheless, for my code. Think of the end of your string like a portal. One you step into the portal. You will appear at the beginning. Nonetheless, if you step through the portal one and then reaching to the space where you started, the portal is gone. Thus, that mean you are done.

Also, remember, what you can get searching backward, can also be obtain going forward with some help from a teleportation device.

Update:

Although the teleportation code looked cool, it is not the most efficient code. I came up with a second solution to solve the problem. That is to compress the beads into blocks and add the blocks of beads together. In that method, I grouped the bead to only two types 'r' and 'b'. For the 'w' beads if they preceding a block, their count will not be added to that block but we keep track of their count. However, if they are succeeding a block they will be added into a block. For the 'w' bead that are like rwr or bbwwbb, they become the count of that block or simply we converted them to r or b, respectively. In the end we only have to calculate the count of each beads block that are next to each other. Thus, saving the nested loop. That is spoiler code number 2. Spoiler 2 also passed submission. It looked like c code but spoiler 2 can be submitted as either c or cpp code.

Your Code With Some Fixed:

#include <bits/stdc++.h>
using namespace std;

int main(){
//For faster I/O
ios::sync_with_stdio(0);
cin.tie(0);
//read and write files
freopen("beads.in", "r", stdin);
freopen("beads.out", "w", stdout);
//get as input all the bead colors
int N; cin >> N;

char beads[N]; for(int i=0;i<N;i++) cin >> beads[i];

//the max amount of stuff we can get
int maxCount = INT_MIN;
//some helper variables we'll need later
int currCount = 0; int counter1 = 0; int counter2 = 0; char currColor = 'w';

for(int i=0;i<N;i++){
    //set counter1 and counter2 both to 0
    counter1 = 0; counter2 = 0;
    //the iterator
    int j; 
    bool changeOne = 0;

    //First loop - forwards
    //---------------------
    j = i;
    currColor = beads[i];
    while(1){
        // The color allow to change one 
        // For example
        // rrrrbbbb is perfectly 8 beads you can get. 
        // Nonetheless bbbrrrrbr you can only get the first 3b and 4 r to make the longesth.
        // Now when it come to w, it can be either. Thus with this string below.
        // rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrw
        // you can get either one b with the w behind it or one b with the w before it.
        if ( beads[j] != currColor ){
           if ( beads[j] != 'w' && changeOne ) break;

           // if we start with 'w'
           // and the color haven't change
           // we better change it
           if ( currColor == 'w' ) 
             currColor = beads[j];
           else 
             changeOne = true;
        }

        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];

        if(j==N-1) j=0;
        else j++;

        counter1++;
        if(counter1 == N) break;
    }

    //Second loop - backwards
    //-----------------------
    j = (i>0) ? i-1 : N-1;
    currColor = (i>0) ? beads[i-1] : beads[N-1];
    while(beads[j]==currColor || beads[j]=='w'){
        if(currColor == 'w' && beads[j] != 'w') currColor = beads[j];
        if(j==0) j=N-1;
        else j--;
        counter2++;
        if(counter2 == N) break;
    }

    //get the current count and get max value
    currCount = counter1 + counter2;
    maxCount = max(currCount,maxCount);
}

if(maxCount > N) cout << N;
else cout << maxCount;

cout << "\n";

return 0;
}

Spoiler Code:

#include <fstream>

using namespace std;

int main () {
    ifstream fin("beads.in");
    ofstream fout("beads.out");

    int totalBeads, len, thisCount, j;
    int maxL = 0,
        changeOne = 0;

    // Read into char array instead of 
    // string for faster performance    
    char beads[350], thisChar, lookFor;

    fin >> len; 
    fin >> beads;

    // lastIndex is made so that this 
    // doesn't have to be computed for every loop.
    const int lastIndex = len - 1;

    for (int i = 0; i < len; i++ ){
      thisCount = 1;
      lookFor = beads[i];
      j = i + 1;
      while(1) {
        // If we reach the end 
        // we start again at the beginning.
        if ( j > lastIndex ) j = 0;
        // If we reach where we use to be
        // we are done for this nested loop
        if ( j == i ) goto makeLength;

        thisChar = beads[j];

        if ( thisChar != lookFor ){
          if ( lookFor == 'w' ){
            lookFor = thisChar;
          } else if ( thisChar != 'w' ){
            lookFor = thisChar;
            // If bead already change between
            // r and b one we are done.
            if ( changeOne == 1 ){
              makeLength:
              if ( thisCount > maxL ) maxL = thisCount;
              changeOne = 0;
              break;
            }
            // We are allow one change.
            changeOne++;
          }
        }
        thisCount++; 
        j++;
      }
    }

    fout << maxL << endl;

    return 0;
}

Spoiler 2 (Block Compressing):

#include <stdio.h>

typedef struct beadBlock{
    int preW;
    int count;
    char type;
} beadBlock;

int main () {
    FILE *fin  = fopen ("beads.in", "r");
    FILE *fout = fopen ("beads.out", "w");

    int len;
    int maxL = 0,
        thisCount = 0,
        wCount = 0,
        pos = 0,
        blockLen = 0;

    // For this algorithm we compress the beads to blocks of beads.
    // At worst there is the same amount of block as bead. 
    // For example, rbrbrbrb.

    // We never need to keep track of the white beads that are
    // behind a block. This, method, included their count into the 
    // a block count.
    beadBlock blocks[351]; 
    char beads[351], thisChar, lookFor;

    fscanf(fin, "%d", &len);
    fscanf(fin, "%s", beads);

    // Discard all white beads at the beginning of the string.
    while ( beads[pos] == 'w' ){
        pos++;
        wCount++;
    }

    // If pos == len, it is all w
    // lookFor's value can be of anything
    // because it won't be used.
    if ( pos != len ) lookFor = beads[pos];
    blocks[blockLen].preW = wCount;
    for ( ; pos < len; pos++ ){
        thisChar = beads[pos];

        // If it is w we just increase 
        // the white count.
        if ( thisChar == 'w' ) {
            wCount++;
        } else {

          if ( thisChar != lookFor ){
            blocks[blockLen].count = thisCount;
            blocks[blockLen].type = lookFor;
            blockLen++;

            // Preparing the wCount for next block.
            blocks[blockLen].preW = wCount;
            thisCount = 0;
            lookFor = thisChar;
          }
          // For anything that is not a 'w', we turn wCount to zero.
          wCount = 0;
        }

        thisCount++;
    }

    blocks[blockLen].count = thisCount;
    blocks[blockLen].type = lookFor;
    blockLen++;

    if ( blockLen < 3 ){
        // If there are less than 3 block, it is easy.
        // If there is just www, the w count will be added
        // by doing block[0].preW.
        maxL = blocks[0].preW;
        maxL += blocks[0].count;
        if (blockLen == 2) maxL += blocks[1].count;
    } else {
        int lastBlock = blockLen - 1;
        // If there were more than 3 blocks,
        // we calculate the count of the border blocks first
        // and use the length of the higher count.

        // If block[0] and block[last] are the same type
        // we need to add an additional block.
        if ( blocks[0].type == blocks[lastBlock].type){
          int maxL2;
          // block[last] + block[0] + block[1]
          // block[last] + block[last - 1] + block[0]
          maxL = blocks[lastBlock].count;
          // When calculating a block, any white
          // succeeding a block will be inclusive in the count of
          // that block but not the white beads proceeding it.
          // Thus, when adding two block together that are next
          // to each other we do not need to add the
          // posW value to the count. However, we have to add preW
          // to the value of the block that does not
          // have any other block on the left of it.
          maxL += blocks[lastBlock].preW;
          maxL += blocks[0].preW;
          maxL += blocks[0].count;
          maxL += blocks[1].count;

          maxL2 = blocks[lastBlock - 1].preW;
          maxL2 += blocks[lastBlock - 1].count;
          maxL2 += blocks[lastBlock].count;
          maxL2 += blocks[0].preW;
          maxL2 += blocks[0].count;
          if ( maxL2 > maxL) maxL = maxL2;
        } else {
          // If last block and first block are not the same type,
          // just add block[last] to block[0]
          maxL = blocks[lastBlock].preW;
          maxL += blocks[lastBlock].count;
          maxL += blocks[0].preW;
          maxL += blocks[0].count;
        }
        // Then we loop.to calculate the length of all
        // blocks that are next to each other.
        for ( int i = 0; i < lastBlock; i++ ){
           // Reusing this count.
           thisCount = blocks[i].preW;
           thisCount += blocks[i].count;
           thisCount += blocks[i+1].count;
           if ( thisCount > maxL ) maxL = thisCount;
        }
    }

    fprintf(fout, "%d\n", maxL );

    return 0;
}