Hello,
I solved Candy Splitting problem in Java. However I am expert in Java
programming, I am new in Algorithms.
I submitted my code here. Since there is a lot of Top Coders in this group,
I will be grateful for any evaluating on my solution.
Your suggestion will be helpful.
Thanks a lot
-- Amir
My code:
import java.io.*;
import java.util.*;
/**
@author Amir H. Sharifzadeh,
Google Code Jam Contest 2011
*/
public class CandySplitting {
public CandySplitting() {
}
private String addPatrick(String[] pies) {
String sum = "";
for (int i = 0; i < pies[0].length(); i++) {
int m = -1;
for (String pie : pies) {
char p = pie.toCharArray()[i];
if (p == '1')
m = -m;
}
if (m > 0)
sum += "1";
else
sum += "0";
}
return sum;
}
private Integer[] getDecimalPartitions(String[] partitionSet) {
Integer[] decimalValues = new Integer[partitionSet.length];
for (int i = 0; i < decimalValues.length; i++)
decimalValues[i] = Integer.parseInt(partitionSet[i], 2);
return decimalValues;
}
private Integer getMaximumofSeanSummation(List<PartitionSet> equalSets)
{
List<Integer> sums = new ArrayList<Integer>();
for (PartitionSet partition : equalSets) {
Integer[] set1 = getDecimalPartitions(partition.getSet1());
int sum1 = 0;
for (Integer aSet : set1) sum1 += aSet;
sums.add(sum1);
int sum2 = 0;
Integer[] set2 = getDecimalPartitions(partition.getSet2());
for (Integer aSet : set2) sum2 += aSet;
sums.add(sum2);
}
return Collections.max(sums);
}
private List<PartitionSet> getPartitionSets(List<String[]> subSets) {
List<PartitionSet> partitionSets = new ArrayList<PartitionSet>();
int n = subSets.size();
for (int i = 0; i < n / 2; i++) {
String[] set1 = subSets.get(i);
String[] set2 = subSets.get(n - i - 1);
PartitionSet partitionSet = new PartitionSet(set1, set2);
partitionSets.add(partitionSet);
}
return partitionSets;
}
private List<PartitionSet> getEqualPartitions(List<PartitionSet>
partitionSets) {
List<PartitionSet> equalSets = new ArrayList<PartitionSet>();
for (PartitionSet partition : partitionSets) {
String[] set1 = partition.getSet1();
String[] set2 = partition.getSet2();
String sum1 = addPatrick(set1);
String sum2 = addPatrick(set2);
if (sum1.equals(sum2))
equalSets.add(partition);
}
return equalSets;
}
private List<String[]> getSubsets(String set[]) {
List<String[]> subSets = new ArrayList<String[]>();
String[] picks = new String[set.length];
for (int len = 1; len <= set.length; len++)
subset(picks, 0, 0, set, len, subSets);
return subSets;
}
private void subset(String[] picks, int n, int start, String[] set, int
len, List<String[]> subSets) {
if (n == len) {
subSets.add(Arrays.copyOfRange(picks, 0, n));
} else {
for (int i = start; i < set.length; i++) {
picks[n] = set[i];
subset(picks, n + 1, i + 1, set, len, subSets);
}
}
}
private List<String[]> getCandies(String path) throws IOException {
Reader reader = new FileReader(path);
BufferedReader br = new BufferedReader(reader);
int n = Integer.valueOf(br.readLine());
List<String[]> candyList = new ArrayList<String[]>(n);
for (int i = 0; i < n; i++) {
Integer pieNum = Integer.valueOf(br.readLine().trim());
String[] pieArray = new String[pieNum];
String myStr = br.readLine();
Scanner sc = new Scanner(myStr);
Integer[] maxarray = new Integer[pieNum];
for (int j = 0; j < pieNum; j++) {
Integer pie = sc.nextInt();
String binaryPile = Integer.toBinaryString(pie);
int lenght = binaryPile.length();
maxarray[j] = lenght;
pieArray[j] = binaryPile;
}
int max = Collections.max(Arrays.asList(maxarray));
for (int j = 0; j < pieNum; j++)
pieArray[j] = convertTO(pieArray[j], max);
candyList.add(pieArray);
}
return candyList;
}
private String convertTO(String pie, int max) {
String str = "";
for (int i = 0; i < max - pie.length(); i++)
str += "0";
return str + pie;
}
public static void main(String[] args) throws IOException {
CandySplitting candySplitting = new CandySplitting();
List<String[]> candyList =
candySplitting.getCandies("D:\\contest2011\\src\\C-large-practice.in");
FileWriter writer = new
FileWriter("D:\\contest2011\\src\\C-large-practice.out");
PrintWriter out = new PrintWriter(writer);
int count = 1;
for (String[] candies : candyList) {
List<String[]> subSets = candySplitting.getSubsets(candies);
int lenght = subSets.size();
String[] endSet = subSets.get(lenght - 1);
subSets.remove(endSet);
List<PartitionSet> partitionSets =
candySplitting.getPartitionSets(subSets);
List<PartitionSet> equalSets =
candySplitting.getEqualPartitions(partitionSets);
if (equalSets.size() == 0) {
out.println("Case #" + count++ + ": NO");
continue;
}
Integer sumSean =
candySplitting.getMaximumofSeanSummation(equalSets);
out.println("Case #" + count++ + ": " + sumSean);
}
out.flush();
out.close();
}
class PartitionSet {
private String[] set1;
private String[] set2;
PartitionSet(String[] set1, String[] set2) {
this.set1 = set1;
this.set2 = set2;
}
public String[] getSet1() {
return set1;
}
public void setSet1(String[] set1) {
this.set1 = set1;
}
public String[] getSet2() {
return set2;
}
public void setSet2(String[] set2) {
this.set2 = set2;
}
}
}
--
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
