USACO Broken Necklace Problem

[EugeneF]

Hi. I recently returned to do USACO problems but I am still stumped on the broken necklace one. I don't understand the problem correctly, because my program fails for test 3. For input
77
rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

Please explain this to me. I think that the answer is 72 and that it looks like this rwrwrwrwrwrwrwrwrwrwrwrwbwrw

bwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr

when split. Please explain to me how I am interpreting the problem incorrectly so I can proceed!

[Minilek]

you forgot that the necklace loops around on itself. if you split
it right before the first b, these are the two pieces:

going backwards from the b: wrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrrwrwrwrwrwrwrwrwrwrwrwrw -> break at b (size 72)

going forwards: bw -> break at r (size 2)

so correct output is 74

[doraemon2112]

I suffered this problem when I used an array 1..350 to store the information.
However, I don't know why, when I stored it in a 1..350,1..350 array with rotation, e.g.

1: rbwrbwwbr
2: bwrbwwbrr
3: wrbwwbrrb
e.t.c

then I got accepted. XD

[EugeneF]

Well I am certainly not using an array and I am still just as confused as ever about going backwards.
This problem is really upsetting me a lot because I can't move on!
[cpp]

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
string breakBeads(string beads, int i);
int numberBeads(const string & beads);
int numberBeads(const string & beads, int break);
int numberBeadsF(const string & beads);
int numberBeadsR(const string & beads);
char findOriginalBead(const string & beads);
char findOriginalBeadR(const string & beads);

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

int numBeads;
string beads;

fin >> numBeads;
fin >> beads;

string brokenBeads;

int largestNumBeads = 0;
int largestBreak = 0;
int tempBeads;
int beads1;
int beads2;

for (int i = 1; i < numBeads; i++) {
brokenBeads = breakBeads(beads, i);

beads1 = numberBeads(brokenBeads.substr(0, i));
cout << brokenBeads.substr(0, i) << " - " << beads1;
beads2 = numberBeads(brokenBeads.substr(i + 1, beads.length()));
cout << brokenBeads.substr(i, beads.length()) << " - " << beads2;
cout << endl;
tempBeads = beads1 + beads2;
if (tempBeads > largestNumBeads) {
largestNumBeads = tempBeads;
largestBreak = i;
}
}

cout << largestNumBeads << '\n';
fout << largestNumBeads << '\n';
return 0;
}

int numberBeads(const string & beads) {
int beadsForward = 0;
int beadsBackward = 0;


char searchBead = findOriginalBead(beads);
for (unsigned int i = 0; i < beads.length(); i++) {
if (beads == 'w' || beads == searchBead)
beadsForward++;
else
break;
}
searchBead = findOriginalBeadR(beads);
for (unsigned int i = beads.length() - 1; i >= 0; i--) {
if (beads == 'w' || beads == searchBead)
beadsBackward++;
else
break;
}
//cout << beads << "-" << beadsBackward << "\n";
//cout << beads << "-" << searchBead << "\n";
//cout << beads << "-" << beadsForward << "-" << beadsBackward << "\n";
if (beadsForward > beads.length() || beadsBackward > beads.length()) {
return beads.length();
}

else if (beadsForward > beadsBackward) {
return beadsForward;
}
return beadsBackward;
/*
else if (beadsForward == beads.length() || beadsBackward == beads.length())
return beadsForward;
else if (beadsForward == 1)
return beadsBackward;
else if (beadsBackward == 1)
return beadsForward;
else
return beadsForward + beadsBackward;
*/
}

char findOriginalBead(const string & beads) {
for (unsigned int i = 0; i < beads.length(); i++) {
if (beads != 'w') {
//cout << beads << "-" << beads << "\n";
return beads;
}
}
return 'w';
}

char findOriginalBeadR(const string & beads, int break) {
for (unsigned int i = beads.length() - 1; i >= 0; i--) {
if (beads != 'w')
return beads;
}
return 'w';
}

string breakBeads(string beads, int i) {
string brokenBeads = string(beads);
brokenBeads.insert(i, " ");
return brokenBeads;
}

[/cpp]

[Minilek]

[c]
beads1 = numberBeads(brokenBeads.substr(0, i));
beads2 = numberBeads(brokenBeads.substr(i + 1, beads.length()));
[/c]

This is wrong. You are not accounting for the fact that the necklace is
not a straight line. The necklace is a circle. The first piece of the necklace
is connected to the last piece of the necklace. (I don't mean to say that just these two lines are wrong, but the approach is wrong in general. You'd have to also change the numberBeads method).

When they say rrwbw for example, the necklace configuration looks like

Code: Select all

      r r
    w    w
       b

It doesn't look like

Code: Select all

rrwbw

When they say to count "backwards" they mean counterclockwise; when they say "forwards" they mean clockwise.

do you see what i mean now? you can't just have some loop from 0 to i 'cause it doesn't just start at 0...it's a circle

[EugeneF]

Could someone please explain to me EXACTLY what I have to do?
Do I count clockwise and counterclockwise for each one and then add them? Do I compare which length is longer? It doesn't matter if I say clockwise or counterclockwise because in the end it is the same...unless you meant start from the first bead and go backwards instead of the last and go backwards.

I have no idea.
Could someone please clearly explain this problem to me

[bugzpodder]

In this problem, the necklace size is small enough (350) that we might as well just try breaking the necklace at each point and see how many beads can be collected. This will take approximately O(n^2) time, but n is small enough that it won't matter.

The code is slightly simple-minded in that we might count the same beads twice if they can be taken off either side of the break. This can only happen if all beads can be taken off the necklace, so we just check for that at the end.

/*
* If the whole necklace can be gotten with a good
* break, we'll sometimes count beads more than
* once. this can only happen when the whole necklace
* can be taken, when beads that can be grabbed from
* the right of the break can also be grabbed from the left.
*/

[shanto86]

Hie,
You can solve the problem in this way:
#at first take the whole line in a string
#check whether whole the necklace can be in one color. If yes then output else continue.
#then start from the first stop at each point where is

[EugeneF]

Thank you very much.

I have finished this problem and am on now on the checkers problem.

Thank you very much.