Incorrect Answer in Broken Necklace Problem USACO [closed]
Want to improve this question? Update the question so it focuses on one problem only by editing this post.
Closed 6 years ago.
Improve this questionBroken Necklace
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 开发者_JAVA百科 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 will include 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.
INPUT FORMAT
Line 1: N, the number of beads Line 2: a string of N characters, each of which is r, b, or w
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
Two necklace copies joined here
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb | wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
******|*****
rrrrrb|bbbbb <-- assignments
5xr .....#|##### 6xb
5+6 = 11 total
This is a USACO training problem i'm having trouble with; i keep getting incorrect answers. ...and please don't tell me this is stupid or silly; that's not helping! :D
Heh, I'm up to this one but I haven't been bothered to code it up. Anyway, my ideas are this.
Firstly, you don't need to store all the bead colours (Go Australian spelling!), you just need to store how many beads of the same colour are in a row. So for:
RRBBBWRR
you just need to store:
2R 3B 1W 2R
One thing to note is if the ending and the starting beads are the same colour you have to account for that, so
RRBBBRR
should be stored as
4R 3B
or
3B 4R
Same thing. Note that the reason for this is not to save memory or anything, but to ensure that beads next to each other are different colours. We have done this by combining beads of the same colour.
Next is you go through each one:
- If it's red, you add up all the ones after that till you find a blue and then continue adding until you find another red
- If it's blue, do similarly except reversed
- If it's white, then the next bead will be red or blue. Do as above except with the number of white beads added
Here are some examples. The |'s mark where the sequence begins and ends.
B|RB|R
we find a R then a B then another R. Therefore we have to stop at the B. In
B|RWRB|R
We find an R and then another R but we haven't found a B yet so we continue. Then we find a B and then another R. This time, since we've found a B we have to stop.
B|RBW|R
we find a R then a B but we can continue since the next one is a W, then we find another R so we have to stop. In
B|WRBWB|R
we count the W then we find a R. Therefore we continue till we find a B and then continue till we find another R. This
B|WBRWR|B
is a reverse case.
Now all you have to do is implement it :D. Of course this doesn't take into account the actual number of beads in the the R, B and W and are just examples of single bead sequences. You will have to check all possible sequences. You also have to take care of the sequences which wrap around from the back to the start.
Lastly, you may notice that this algorithm is sometimes wasteful but N < 350 so even an O(N^3) should work in 1 second. Maybe 2. Anyway, I believe this is O(N^2) so you should be able to run this program 350 times in one second. Please comment if something's confusing because I'm not the best explainer. Happy coding.
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int main(){
int numBeads;
char temp1[705];
char temp2[705];
int i,j,k,lim;
int count1 = 0;
int count2 = 0;
int maxcount1 = 0;
char virgin = ' ';
bool flag = false; //flag == true if virgin doesn't match
FILE* fin = fopen("beads.in","r");
FILE* fout = fopen("beads.out","w");
fscanf(fin,"%d",&numBeads);
fscanf(fin,"%s",temp1);
strcpy(temp2,temp1);
strcat(temp1,temp2);
for(i=0,j=numBeads-1;i<numBeads;i++,j++){
count1 =0;
count2 = 0;
flag = false;
virgin = ' ';
for(k=i;flag==false && k < (i+numBeads);k++){
if(temp1[k]=='w'){
count1++;
}
else if(temp1[k]=='r'){
if(virgin==' '){
virgin = 'r';
}
if(virgin=='r')
count1++;
else{
flag = true;
k--;
}
}
else if(temp1[k]=='b'){
if(virgin==' '){
virgin = 'b';
}
if(virgin=='b')
count1++;
else{
flag = true;
k--;
}
}
}
/* Block 2*/
lim = k;
flag = false;
virgin = ' ';
for(k=j;flag==false && k < (j+numBeads) && k>=lim;k--){
if(temp1[k]=='w'){
count2++;
}
else if(temp1[k]=='r'){
if(virgin==' '){
virgin = 'r';
}
if(virgin=='r')
count2++;
else{
flag = true;
k--;
}
}
else if(temp1[k]=='b'){
if(virgin==' '){
virgin = 'b';
}
if(virgin=='b')
count2++;
else{
flag = true;
k--;
}
}
}
if(maxcount1 < (count1+ count2))maxcount1 = count1 + count2;
}
fprintf(fout,"%d\n",maxcount1);
return 0;
}
Here is my code:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
/**
*
* @author Bansari
*/
public class beads {
public static void main(String args[]){
try{
BufferedReader f = new BufferedReader(new FileReader("beads.in"));
// input file name goes above
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("str.txt")));
int len = Integer.parseInt(f.readLine());
String s=f.readLine();
int c1=0,c2=0;
int breakpoint=0;
int max = 0;
for(int i = 1;i<=len;i++){
char before = s.charAt((i-1)%len);
char after = s.charAt(i%len);
if(before != after){
c1=0;
c2=0;
int index = i-1;
while(s.charAt(index)==before || s.charAt(index)=='w'){
char sc = s.charAt(index);
c1++;
if(index==0)
index = len-1;
else
index--;
}
index = i;
while(s.charAt(index%len)==after || s.charAt(index%len)=='w'){
c2++;
if(index == len-1)
index = 0;
else
index++;
}
if(max < (c1 + c2)){
breakpoint=i;
max = c1+c2;
}
}
}
out.println(max);
out.close();
System.exit(0);
}catch(Exception e){
}
}
}
When you're presented with a weird problem in a computing contest, it's odds-on it'll be dynamic programming (the Bellman kind, not the Ruby kind.)
Have a look at this tutorial.
The basic idea of dynamic programming is to build up a "big" answer by answering small subproblems. My first intuitive thought is to think about longer and longer necklaces, starting with, like, one bead, but I'm honestly not particularly good at dynamic programming problems. (I've also noticed that the most common place to run into DP problems in the real world is in computing olympiads and problem sets in computer science classes.)
RETRACTED -- THIS IS WRONG because it does not consider white beads.
i can either see a simpler than the accepted answer, or the explanation is too complex. here's the algorithm in pseudocode (ignoring the case of all same color):
p = position of first bead of different color than bead 0
create array of run-lengths: r={5,15,2,9,13}
create array of sums of adjacents s={20,17,11,22,18} (wrap last)
find index, k, in s[] of max sum: here it is s[3]
position = p + r[0] + r[1] + ... + r[k]
I did this a long long time ago when I was learning programming. I just searched my computer and found the solution that I had submitted. I can provide the code but its all messed up . =P
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
public class beads {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
new beads().go();
}
private void go() throws Exception {
// TODO Auto-generated method stub
BufferedReader bin = new BufferedReader(new FileReader("beads.in"));
PrintWriter pout = new PrintWriter(new BufferedWriter(new FileWriter("beads.out")));
int count = Integer.parseInt(bin.readLine());
String beads = bin.readLine();
int ans = compute(beads);
pout.println(ans);
pout.close();
}
private int compute(String beads) {
// TODO Auto-generated method stub
int length = beads.length();
int maxbeads = 0;
for(int i = 0; i < length; i++){
int left = 0;
int right = 0;
left = computeLeft(beads,i);
if(left == length){ maxbeads = left; break;}
right = computeRigtht(beads,i);
if(right == length){ maxbeads = right; break;}
if((left+right) > maxbeads) maxbeads = left+right;
if(maxbeads == length) break;
}
return maxbeads;
}
private int computeLeft(String beads, int i) {
// TODO Auto-generated method stub
int l = beads.length();
int j = i;
int count = 0;
char ch = beads.charAt(i);
for(; j >=0; j--){
if(ch == 'w'){//Didnt notice this kind of case before
ch = beads.charAt(j);
count++;
}
else if(beads.charAt(j) == ch || beads.charAt(j)== 'w'){
count++;
}
else break;
}
if(j < 0) j = l-1;
for(; j > i; j--){
if(beads.charAt(j) == ch || beads.charAt(j)== 'w'){
count++;
}
else break;
}
return count;
}
private int computeRigtht(String beads, int i) {
// TODO Auto-generated method stub
int l = beads.length();
int j = 0;
if(i == l-1) j = 0;
else j = i+1;
int k = j;
int count = 0;
int ch = beads.charAt(j);
for(; j <l; j++){
if(ch == 'w'){
ch = beads.charAt(j);
count++;
}
else if(beads.charAt(j)== ch || beads.charAt(j)=='w'){
count++;
}
else break;
}
if(j == l) j = 0;
for(; j < k-1; j++){
if(beads.charAt(j) == ch || beads.charAt(j)== 'w'){
count++;
}
else break;
}
return count;
}
}
I used quasiverse's algo and solved it. The USACO server is down and I am not able to test it on their judge, but I think I have solved it.
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<cstdlib>
#define MAXLEN 350
using namespace std;
ofstream fout ("beads.out");
typedef struct node
{
char color;
int times;
int lenMax;
struct node* next;
} nodeList;
nodeList * getnode()
{
nodeList* temp=(nodeList*) malloc (sizeof(nodeList));
temp->next=NULL;
temp->lenMax=0;
return temp;
}
void append(nodeList **head,char tColor,int m)
{
nodeList *p=NULL,*newNode=NULL;
newNode =getnode();
newNode->color=tColor;
newNode->times=m;
newNode->lenMax=0;
if(*head==NULL)
{
*head=newNode;
return;
}
p=*head;
while(p->next)
p=p->next;
p->next=newNode;
}
void shiftNodes(nodeList **head)
{
int mon=0;
nodeList *last=NULL,*p=NULL,*t=NULL;
p=*head;
do
{
//cout<<p->color<<" "<<p->times<<endl;
last=p;
p=p->next;
}
while(p!=NULL);
p=*head;
last->next=*head;
t=*head;
do
{
if(((*head)->color=='w' || (last)->color=='w' ) || (*head)->color==last->color)
{
(*head)=(*head)->next;
last=last->next;
}
else if((*head)->color!=last->color )
{
break;
}
p=p->next;
}
while(p!=t);
}
void computeLenMaxB(nodeList ** head)
{
nodeList *p =NULL,*t=NULL,*s=NULL;
t=p=*head;
bool gotR=false;
int tempLenMax=0;
do
{
if(p->color=='b' && gotR){
break;
}
else if(p->color=='b' && !gotR){
tempLenMax+=p->times;
}
else if(p->color=='r' && !gotR){
tempLenMax+=p->times;
gotR=true;
}
else if(p->color=='r' && gotR){
tempLenMax+=p->times;
}
else if(p->color=='w' ){
tempLenMax+=p->times;
}
p=p->next;
}
while(p!=t);
(*head)->lenMax=tempLenMax;
}
void computeLenMaxR(nodeList ** head)
{
nodeList *p =NULL,*t=NULL,*s=NULL;
t=p=*head;
bool gotR=false;
int tempLenMax=0;
do
{
if(p->color=='r' && gotR){
break;
}
else if(p->color=='r' && !gotR){
tempLenMax+=p->times;
}
else if(p->color=='b' && !gotR){
tempLenMax+=p->times;
gotR=true;
}
else if(p->color=='b' && gotR){
tempLenMax+=p->times;
}
else if(p->color=='w' ){
tempLenMax+=p->times;
}
p=p->next;
}
while(p!=t);
(*head)->lenMax=tempLenMax;
}
void fillLenMax(nodeList ** head)
{
nodeList *p =NULL,*t=NULL,*s=NULL;
t=p=*head;
int wBeads=0;
do
{
s=p;
if(p->color=='b')
{
computeLenMaxB(&p);
}
else if(p->color=='r')
{
computeLenMaxR(&p);
}
else if(p->color=='w')
{
if(p->next->color=='b'){
computeLenMaxB(&p);
}
else if(p->next->color=='r'){
computeLenMaxR(&p);
}
}
p=p->next;
}
while(p!=t);
}
int calcMaxLenMax(nodeList *head)
{
nodeList *p=NULL;
p=head;
int max=0;
do
{
//fout<<p->color<<" "<<p->times<<" "<<p->lenMax<<endl;
max=(max>p->lenMax)?max:p->lenMax;
p=p->next;
}
while(p!=head);
return max;
}
int main()
{
ifstream fin ("beads.in");
char necklace[MAXLEN];
int i,j,max;
fin>>necklace;
nodeList* list=NULL;
int repeat = 0;
i=0;
while(i<strlen(necklace))
{
repeat = 0;
for(j=i; necklace[j]==necklace[i]; j++)
{
repeat++;
}
append(&list ,necklace[i],repeat);
i=i+repeat;
}
shiftNodes(&list);
fillLenMax(&list);
max=calcMaxLenMax(list);
fout<<max<<endl;
return 0;
}
Its an old thread, but might be useful to people learning programming. Here is a simple solution using brute force. The idea is that we make one pass through the data to count colours. In the second loop we perform pairwise comparison of sums from the left and the right part. Code should be easy to follow:
import java.io.*;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;
public class beads {
public static void main(String[] args) throws IOException {
BufferedReader f = new BufferedReader(new FileReader("beads.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("beads.out")));
f.readLine();//length
String s1 = f.readLine();
List<String> counts = new LinkedList<String>();
char[] colors = (s1.concat(s1)).toCharArray();
char previousColor = ' ';
int count = 0;
for (char color : colors) {
if (previousColor != color && count > 0) {
counts.add(count + "-" + previousColor);
count = 0;
}
count++;
previousColor = color;
}
if (counts.isEmpty()) {//special case when there is only one color
out.println(count/2);
out.close();
System.exit(0);
}
TreeSet<Integer> result = new TreeSet<Integer>();
for (int i = 1; i < counts.size(); i++) {
if(counts.get(i).split("-")[1].charAt(0)=='w')continue;
int left = getLeft(counts, i);
int right = getRight(counts, i);
result.add((left+right));
}
out.println(result.last());
out.close();
System.exit(0);
}
private static int getLeft(List<String> counts, int i) {
char start = counts.get(i - 1).split("-")[1].charAt(0);
boolean doContinue = true;
int count = 0;
while (doContinue) {
String[] s = counts.get(--i).split("-");
char color=s[1].charAt(0);
if(start=='w' && color!='w')start=color;
boolean incr = (color == 'w' || color==start);
if(incr)
count += Integer.parseInt(s[0]);
else doContinue=false;
doContinue = doContinue && i > 0;
}
return count;
}
private static int getRight(List<String> counts, int i) {
char start = counts.get(i).split("-")[1].charAt(0);
boolean doContinue = true;
int count = 0;
while (doContinue) {
String[] s = counts.get(i).split("-");
char color=s[1].charAt(0);
if(start=='w' && color!='w')start=color;
boolean incr = (color == 'w' || color == start);
if(incr)
count += Integer.parseInt(s[0]);
else doContinue=false;
doContinue = doContinue && ++i < counts.size()-1;
}
return count;
}
}
This is a teaser! Every time solution is just so, so close! In the meantime the white beads are cause of black despair.
Here is the algorithm (I passed Usaco grader)
1) find first colored bead. say it is at position k in the n bead necklace
2) rearrange necklace: move the section 0-k to the end ,so it starts with true color.
e.g {wwbrwbrb{ becomes {brwbrbww}
3) cut up the necklace into sub-sections (array of strings), so that each section starts with a color e.g. {b rw b r bww}
4) if first and last segment are the same color, join them
e.g. {b rw bw rw bww} becomes {bwwb rw bw rw} (sequence is preserved)
5) Notice!!!! the second last element (bw) ends with white. So white can be joined to rw that follows.
Also notice that following sequence will never starts with white.
6) for each entry in the array of sub sequences add lengths of entry k and k+1.
Then skim the white spaces (if any) from the entry k-1 and add to the above (since this is a circle then k-1 entry may be the last in the array).
if bigger than max then change max.
There is some tricky accounting for less than three sub sequences in the necklace but it is just tedious, no trick to it.
加载中,请稍侯......
精彩评论