Broken Necklace problem from USACO
by Abhijeet Kashnia
My somewhat crappy solution to Broken Necklace problem from USACO.
Only meant as a personal log of solutions.
/*
ID: abhi
LANG: JAVA
TASK: beads
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
public class beads
{
public static void main(String[] args) throws IOException
{
// String beads = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrb";
// String beads = "rrr";
// int count = new beads().getBeadCount(beads);
// if(count>beads.length()) count=beads.length();
// System.out.println(count);
BufferedReader reader = new BufferedReader(new FileReader(new File("beads.in")));
int length = Integer.parseInt(reader.readLine());
String beads = reader.readLine();
int count = new beads().getBeadCount(beads);
if(count>beads.length()) count=beads.length();
PrintWriter out = new PrintWriter(new File("beads.out"));
out.println(count);
out.close();
System.exit(0);
}
private int getBeadCount(String beads) {
beads= beads + beads; // append, now just run the logic.
int maxCount=-1;
int position=0;
for(int i=0;i<(beads.length()+1)/2;i++) {
int state=0; // w not encountered/ w not set.
int counter=i;
while(beads.charAt(counter)=='w') {
counter++;
if(counter==beads.length()) {
return (counter-i);
}
}
state = beads.charAt(counter)=='b' ? 1 : 2;
if(state==1) {
while(counter<beads.length() && (beads.charAt(counter) == 'w' || beads.charAt(counter)=='b')) {
counter++;
}
state=2;
while(counter<beads.length() && (beads.charAt(counter) == 'w' || beads.charAt(counter)=='r') ) {
counter++;
}
state=3;
}
else if (state==2) {
while( counter<beads.length() && (beads.charAt(counter) == 'w' || beads.charAt(counter)=='r') ) {
counter++;
}
state=1;
while( counter<beads.length() && (beads.charAt(counter) == 'w' || beads.charAt(counter)=='b')) {
counter++;
}
state=3;
}
if(maxCount <counter-i) {
maxCount =counter-i;
position =i;
}
}
// System.out.println("At position" + position);
return maxCount;
}
}