USACO Broken Necklace Problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
EugeneF
New poster
Posts: 5
Joined: Sun Mar 28, 2004 4:02 am

USACO Broken Necklace Problem

Post by 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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by 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
New poster
Posts: 9
Joined: Sun Jul 11, 2004 10:55 am

Post by 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
New poster
Posts: 5
Joined: Sun Mar 28, 2004 4:02 am

Post by 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
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by 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
New poster
Posts: 5
Joined: Sun Mar 28, 2004 4:02 am

Post by 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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by 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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by 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
Self judging is the best judging!

EugeneF
New poster
Posts: 5
Joined: Sun Mar 28, 2004 4:02 am

Post by EugeneF »

Thank you very much.

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

Thank you very much.

Post Reply

Return to “Algorithms”