Problem Info
I’m trying to solve Livestock Lineup. What my code does is find all the permutations of the 8 cows, check if it meets our parameters and then replace the answer if it comes first in alphabetical order.
My Work
import java.util.*;
import java.io.*;
public class Livestock_Lineup {
public static ArrayList<String> answer = new ArrayList<>();
public static HashMap<String, String> conditions = new HashMap<>();
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new FileReader("lineup.in"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("lineup.out")));
int condition = Integer.parseInt(br.readLine());
ArrayList<String> animals = new ArrayList<>();
animals.add("Bessie");
animals.add("Buttercup");
animals.add("Belinda");
animals.add("Beatrice");
animals.add("Bella");
animals.add("Blue");
animals.add("Betsy");
animals.add("Sue");
String first = "";
String second = "";
StringTokenizer st = null;
for(int x = 0; x < condition; x++) {
st = new StringTokenizer(br.readLine());
first = st.nextToken();
st.nextToken();
st.nextToken();
st.nextToken();
st.nextToken();
second = st.nextToken();
conditions.put(first, second);
}
permute(new ArrayList<String>(), animals);
for(String x:answer) {
System.out.println(x);
}
}
public static void permute(ArrayList<String> prefix, ArrayList<String> original) {
ArrayList<String> cprefix = new ArrayList<>();
ArrayList<String> coriginal = new ArrayList<>();
if(original.size() == 0) {
if(check(prefix)) {
if(answer.size() == 0) {
answer = prefix;
}
else {
answer = alphabetical(prefix);
}
}
return;
}
else {
for(int x = 0; x < original.size(); x++) {
cprefix = (ArrayList<String>) prefix.clone();
coriginal = (ArrayList<String>) original.clone();
cprefix.add(original.get(x));
coriginal.remove(x);
permute((ArrayList<String>) cprefix.clone(), (ArrayList<String>) coriginal.clone());
}
}
}
public static boolean check(ArrayList<String> permutation) {
String next = "";
int index = 0;
for(String x:conditions.keySet()) {
next = conditions.get(x);
index = permutation.indexOf(x);
if( (index + 1 < permutation.size() && permutation.get(index + 1).equals(next)) ||
(index - 1 > -1 && permutation.get(index-1).equals(next))) {
continue;
}
else {
return false;
}
}
return true;
}
public static ArrayList<String> alphabetical(ArrayList<String> permutation) {
int first = permutation.indexOf("Bessie");
int second = answer.indexOf("Bessie");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Buttercup");
second = answer.indexOf("Buttercup");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Belinda");
second = answer.indexOf("Belinda");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Beatrice");
second = answer.indexOf("Beatrice");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Bella");
second = answer.indexOf("Bella");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Blue");
second = answer.indexOf("Blue");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Betsy");
second = answer.indexOf("Betsy");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
first = permutation.indexOf("Sue");
second = answer.indexOf("Sue");
if(first < second) {
return permutation;
}
if(second < first) {
return answer;
}
return permutation;
}
}
Add explanation of code here
What I’ve Tried
So, when I run this code with the sample input, my output is,
Bessie
Buttercup
Bella
Blue
Belinda
Beatrice
Sue
Betsy,
but the sample output is
Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup
Question
So, I noticed that Buttercup is next to Bella, Blue is next to Bella, and that Sue is next to Beatrice, so this is one possible solution. The thing is, this is more alphabetized than the sample output. Am I wrong? Also is there a way to compare to ArrayList to order them in alphabetical order? The last function is so repetitive and long. Thank you!
Edit: I reread the problem and see that I read the problem wrong. I am confused about the how the ordering works. Could someone explain?
Is it more alphabetized though? Compare the first elements of the array again, and check again. Remember, you know when something is lexicographically smaller once something differs. Take this for example
First array:
abc
aba
zzz
Second array:
abc
abb
aaa
When comparing these arrays, you can stop once you reach the second element of each array, as aba is less than abb. This is sufficient enough to say that the first array is lexicographically smaller than the second one.
As for your second part, I think you can just use the equivalent of a set in C++, although I’m not sure if this would TLE in Java. I think this is a TreeSet in Java? (I don’t use Java idk). Somebody correct me if I’m wrong. Then, you can just print out the first element in the set, and it is guaranteed to be the smallest.
I would recommend looking at the editorial once you solve the problem, because I think you missed something that could have completely removed the requirement to order them in alphabetical order in the end.
Ok, so I figured out lexicographical ordering and my code is,
import java.util.*;
import java.io.*;
public class Livestock_Lineup {
public static ArrayList<String> answer = new ArrayList<>();
public static ArrayList<String> an1 = new ArrayList<String>();
public static ArrayList<String> an2 = new ArrayList<String>();
public static void main(String[] args) throws IOException {
//Use array for the conditions
BufferedReader br = new BufferedReader(new FileReader("lineup.in"));
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader br = new BufferedReader(new FileReader("/Users/youjungkim/DropBox/ryankim/USACO_Bronze_3/lineup_bronze_dec19/5.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("lineup.out")));
int condition = Integer.parseInt(br.readLine());
ArrayList<String> animals = new ArrayList<>();
animals.add("Bessie");
animals.add("Buttercup");
animals.add("Belinda");
animals.add("Beatrice");
animals.add("Bella");
animals.add("Blue");
animals.add("Betsy");
animals.add("Sue");
String first = "";
String second = "";
StringTokenizer st = null;
for(int x = 0; x < condition; x++) {
st = new StringTokenizer(br.readLine());
first = st.nextToken();
st.nextToken();
st.nextToken();
st.nextToken();
st.nextToken();
second = st.nextToken();
an1.add(first);
an2.add(second);
}
System.out.println(an1);
System.out.println(an2);
permute(new ArrayList<String>(), animals);
for(String x:answer) {
System.out.println(x);
pw.println(x);
}
pw.close();
}
public static void permute(ArrayList<String> prefix, ArrayList<String> original) {
ArrayList<String> cprefix = new ArrayList<>();
ArrayList<String> coriginal = new ArrayList<>();
if(original.size() == 0) {
if(check(prefix)) {
if(answer.size() == 0) {
answer = prefix;
}
else {
answer = alphabetical(prefix);
}
}
return;
}
else {
for(int x = 0; x < original.size(); x++) {
cprefix = (ArrayList<String>) prefix.clone();
coriginal = (ArrayList<String>) original.clone();
cprefix.add(original.get(x));
coriginal.remove(x);
permute((ArrayList<String>) cprefix.clone(), (ArrayList<String>) coriginal.clone());
}
}
}
public static boolean check(ArrayList<String> permutation) {
String next = "";
int index = 0;
for(String x:an1) {
next = an2.get(an1.indexOf(x));
index = permutation.indexOf(x);
//next = an2.get(index);
if( (index + 1 < 8 && permutation.get(index + 1).equals(next)) ||
(index - 1 > -1 && permutation.get(index-1).equals(next))) {
continue;
}
else {
return false;
}
}
return true;
}
public static ArrayList<String> alphabetical(ArrayList<String> permutation) {
int compare = 0;
for(int x = 0; x < 8; x++) {
compare = permutation.get(x).compareTo(answer.get(x));
if(compare < 0) {
return permutation;
}
else if(compare > 0) {
return answer;
}
}
return permutation;
}
}
5,6,8,9, and 10 got a wrong answer, but I don’t know why… Could I get a hint?
I tried downloading test data, but I have no clue. I first the most major change I did was changing the HashMap to two ArrayList(). This is necessary because HashMap will eliminate any duplicates. At this point, I think it’s a bug, but I can’t seem to find a it… Could I get some help?
“alphabetically earliest”. check the order of the cows you use to compare.
OMG OMG. Thank you so much! There were two major mistakes that messed up the code.
The first was using HashMap because that would eliminate duplicate keys.
The second was using a for each loop in my check function. This causes the indexOf function to find the index of the first one only when I might want the second index.
I did the problem, but I would like one more question answered. So, lexicographical order is pretty much dictionary order. Then why, is Sue usually before other cows? B is before S. Also, what exactly does the compareTo function do? I did some research, but couldn’t really find an answer…
Thank you again!
So, lexicographical order is pretty much dictionary order.
in this problem, yeah. so prioritize a before b, b before c, …
in some problems, lexicographical order may not be alphabetically, maybe with integers (example: [1, 2, 3, 4] is lexicographically earlier than [1, 2, 3, 5]).
Then why, is Sue usually before other cows?
huh wdym??
Also, what exactly does the compareTo function do? I did some research, but couldn’t really find an answer…
sorry, i don’t really know java. my guess is that it returns -1 if lesser, 0 if same, and 1 if greater
Sorry, everyone is probably annoyed, but I kind of want to understand this.
For example, if we look at the sample output, we see that another possible ordering is
Bessie
Bella
Betsy
Blue
Bella
Buttercup
Beatrice
Sue.
Isn’t this in more alphabetical order?
No; if we look at the first cow in your ordering, it’s Bessie. In the sample output, the first cow is Beatrice. As defined by the problem,
the first cow should have the alphabetically lowest name of all possible cows that could appear first in any valid ordering.
Since Beatrice is alphabetically lower than Bessie, the sample output’s order is alphabetically lower than yours.
Thank you so much! I would like to thank everyone else who also helped me. I now understand the sample output more clearly! Thank you!