## USACO Broken Necklace Problem

Moderator: Board moderators

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

### USACO Broken Necklace Problem

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:
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
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
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;

int main() {

int largestBreak = 0;

for (int i = 1; i < numBeads; i++) {

cout << endl;
largestBreak = i;
}
}

return 0;
}

for (unsigned int i = 0; i < beads.length(); i++) {
else
break;
}
for (unsigned int i = beads.length() - 1; i >= 0; i--) {
else
break;
}
}

}
/*
else
*/
}

for (unsigned int i = 0; i < beads.length(); i++) {
}
}
return 'w';
}

for (unsigned int i = beads.length() - 1; i >= 0; i--) {
}
return 'w';
}

}

[/cpp]

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
[c]
[/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
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
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
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
Thank you very much.

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

Thank you very much.