http://code.google.com/codejam/contest/dashboard?c=32016#s=p1
On Tue, Apr 3, 2012 at 7:50 PM, Samuel Jawahar <[email protected]> wrote: > Hi any one solved Milkshaes problem? > I have implemented in DP > don't know why it is failing,can any one review my code > > -------------------------------------------------------------start----------------------------------------------- > import java.io.BufferedReader; > import java.io.FileReader; > import java.io.FileWriter; > import java.io.IOException; > import java.io.PrintWriter; > import java.util.ArrayList; > import java.util.Collections; > import java.util.Comparator; > > public class Milkshakes { > PrintWriter out = null; > BufferedReader in = null; > ArrayList<CustomerChoices> customerChoices = new > ArrayList<CustomerChoices>(); > int numberOfmc = 0; > StringBuilder sb = new StringBuilder(); > String solutionString = ""; > int backtrackState = -1; > > public Milkshakes() { > try { > out = new PrintWriter(new FileWriter("B-small-practice.out")); > in = new BufferedReader(new FileReader("B-small-practice.in")); > } catch (IOException e) { > e.printStackTrace(); > } > } > > public String processSolutionString(String data) { > String output[] = new String[numberOfmc]; > data = data.trim(); > String choices[] = data.split(" "); > int len = choices.length; > String aux[] = new String[2]; > for (int i = 0; i < len; i++) { > aux = choices[i].split(":"); > output[Integer.parseInt(aux[0]) - 1] = aux[1]; > } > StringBuilder sb = new StringBuilder(); > for (int i = 0; i < numberOfmc; i++) { > if (output[i] == null) { > output[i] = "0"; > } > sb.append(output[i]).append(" "); > } > return sb.toString(); > > } > > public void doitIndp(StringAttr canterminate, String previousDecissions, > int currentStage, int numberOfstages) { > CustomerChoices cc = customerChoices.get(currentStage); > ArrayList<Choice> ccl = cc.getChoiceList(); > int size = ccl.size(); > Choice curentChoice = null; > String decissionString = ""; > if (currentStage == numberOfstages - 1) { > // solution state > > for (int i = 0; i < size; i++) { > curentChoice = ccl.get(i); > decissionString = ""; > if (curentChoice.type == 1) { > decissionString = " " + curentChoice.machineNumber + ":" > + 0; > } else { > decissionString = " " + curentChoice.machineNumber + ":" > + 1; > } > if (!previousDecissions.contains(decissionString)) { > decissionString = " " + curentChoice.machineNumber + ":" > + curentChoice.type; > solutionString = processSolutionString(previousDecissions > + decissionString); > canterminate.setCanTerminate("YES"); > return; > } > } > } else { > for (int i = 0; i < size; i++) { > curentChoice = ccl.get(i); > decissionString = ""; > if (curentChoice.type == 1) { > decissionString = " " + curentChoice.machineNumber + ":" > + 0; > } else { > decissionString = " " + curentChoice.machineNumber + ":" > + 1; > } > if (!previousDecissions.contains(decissionString)) { > decissionString = " " + curentChoice.machineNumber + ":" > + curentChoice.type; > doitIndp(canterminate, > previousDecissions + decissionString, > currentStage + 1, numberOfstages); > if (canterminate.getCanTerminate() == "YES") { > return; > } > if (canterminate.getCanTerminate() == "BT") { > if (currentStage == backtrackState) { > backtrackState = 0; > canterminate.setCanTerminate("NO"); > continue; > } else { > return; > } > } > } > } > if (currentStage != 0) { > int backstate = 0; > previousDecissions = previousDecissions.trim(); > String pst[] = previousDecissions.split(" "); > > for (; backstate < pst.length; backstate++) { > if (pst[backstate].trim().equals(decissionString.trim())) { > break; > } > } > canterminate.setCanTerminate("BT"); > backtrackState = backstate; > } > } > } > > /** > * @param args > */ > public static void main(String[] args) { > Milkshakes m = new Milkshakes(); > int stages = 0; > try { > int ntc = Integer.parseInt(m.in.readLine().trim()); > for (int i = 1; i <= ntc; i++) { > m.customerChoices.clear(); > m.solutionString = ""; > m.numberOfmc = Integer.parseInt(m.in.readLine().trim()); > int malted[] = new int[m.numberOfmc]; > for (int l = 0; l < m.numberOfmc; l++) { > malted[l] = -1; > } > stages = Integer.parseInt(m.in.readLine().trim()); > System.out.println("---------------------------------"); > System.out.println(m.numberOfmc + ":" + stages); > System.out.println("---------------------------------"); > for (int j = 0; j < stages; j++) { > m.customerChoices.add(new CustomerChoices(m.in.readLine())); > } > StringAttr sattr = new StringAttr("NO"); > m.doitIndp(sattr, "", 0, stages); > > if (m.solutionString == "") { > m.out.println("Case #" + i + ": IMPOSSIBLE"); > System.out.println("Case #" + i + ": IMPOSSIBLE"); > } else { > m.out.println("Case #" + i + ": " + m.solutionString.trim()); > System.out.println("Case #" + i + ": " + m.solutionString); > } > > } > m.out.close(); > } catch (NumberFormatException e) { > e.printStackTrace(); > } catch (IOException e) { > e.printStackTrace(); > } > > } > > } > > class Choice { > int machineNumber, type; > > public Choice(int machineNumber, int type) { > this.machineNumber = machineNumber; > this.type = type; > } > } > > class CustomerChoices { > ArrayList<Choice> choiceList = new ArrayList<Choice>(); > > public ArrayList<Choice> getChoiceList() { > return choiceList; > } > > public void setChoiceList(ArrayList<Choice> choiceList) { > this.choiceList = choiceList; > } > > public CustomerChoices(String choices) { > String inputRequest = choices.trim(); > String d[] = inputRequest.trim().split(" "); > int nc = Integer.parseInt(d[0]); > for (int l = 1; l <= nc; l++) { > int machineNumber = Integer.parseInt(d[2 * l - 1]); > int type = Integer.parseInt(d[2 * l]); > choiceList.add(new Choice(machineNumber, type)); > } > Collections.sort(choiceList, new ChoiceComparator()); > } > } > > class StringAttr { > public StringAttr(String canTerminate) { > this.canTerminate = canTerminate; > } > > public String getCanTerminate() { > return canTerminate; > } > > public void setCanTerminate(String canTerminate) { > this.canTerminate = canTerminate; > } > > String canTerminate; > } > > class ChoiceComparator implements Comparator<Choice> { > > @Override > public int compare(Choice o1, Choice o2) { > // TODO Auto-generated method stub > if (o1.type > o2.type) { > return 1; > } > if (o1.type < o2.type) { > return -1; > } > return 0; > } > > } > > -------------------------------------------------------------stop------------------------------------------------- > > On Tue, Apr 3, 2012 at 12:06 AM, vivek dhiman <[email protected]>wrote: > >> Hi all smart people. >> >> if there are two set of numbers (both sets are of size 3) >> (a,b,c) and (d,e,f) >> >> given a number k, how will you count all numbers(n) < k that are >> divisible by both x and y >> where x is any number from set (a,b,c) >> and y is any number from set (d,e,f) >> >> remember you should take care of repetitions.. >> >> Thing is I am doing this using sets and iterators which is taking much >> more time ..suggest some better approach .. >> No need to write code... just the approach.. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" 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. >> > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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.
