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.
