Hi Amir your algorithm generates all possible subsets ...if we look at the limits for small testcase n=15 so total number of subsets pow(2,n)-1=32767 you can handle with this approach ,so it works for the small inputs.But you can generate subsets with much smaller code.
for large testcase n=1000 so total number of subsets pow(2,1000)-1 which consists of a ceil(log10(pow(2,1000)-1))=302 digits .....you cant generate that amount of subsets So this definitely leads to TLE. Contest analysis shows a better approach for this one On May 10, 4:27 pm, Amir Hossein Sharifzadeh <[email protected]> wrote: > 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.
