Luxury Hampers
This problem is quite difficult. My first code runs for a couple of minutes to get the answer. After I read the discussion, I found I missed an important fact from those five integer pairs given in the problem.
I optimized my code using this important and obvious fact, my code's run time is reduced to 16 seconds. Still too slow! Finally, I realized that it really matters how you search the space. By changing the search order, the search space can be greatly reduced. After this important optimization, it only take 0.6 second to get the answer!
public class LuxuryHampers {
ReplyDelete/**
*
*/
public LuxuryHampers() {
}
/**
* @param args
*/
public static void main(String[] args) {
int N = 3;
int[] P1 = { 10, 8, 6 };
int[] P2 = { 2, 9, 9 };
solution(N, P1, P2);
/**
* A = [p 10,8,6(24) ] [ s 9,4,3 (16) ] *16/24=2/3* B = [p 2,9,9(20) ] [ s 2,5,5
* (12) ] *12/20=3/5*
*
* A = m*B 2/3 = m*(3/5) m = (2/3) / (3/5) = (2/3) * (5/3) = 10/9
*
*
*/
}
private static void solution(int n, int[] p1, int[] p2) {
int[][] spoilage = new int[n][n];
spoilage[0][0] = 9;
spoilage[0][1] = 4;
spoilage[0][2] = 3;
spoilage[1][0] = 2;
spoilage[1][1] = 5;
spoilage[1][2] = 5;
double spoilage1ArrySum = 0, spoilage2ArrySum = 0;
spoilage1ArrySum = arraySum(spoilage[0]);
spoilage2ArrySum = arraySum(spoilage[1]);
double prod1ArrySum = 0, prod2ArrySum = 0;
prod1ArrySum = arraySum(p1);
prod2ArrySum = arraySum(p2);
int n1 = (int) (spoilage1ArrySum * prod2ArrySum);
int n2 = (int) (spoilage2ArrySum * prod1ArrySum);
System.out.println(reduce(n1, n2));
}
private static String reduce(int num1, int num2) {
if (num1 % 2 == 0 && num2 % 2 == 0) {
return reduce(num1 / 2, num2 / 2);
}
return num1 + "/" + num2;
}
/**
*
* @param arr
* @return
*/
private static double arraySum(int[] arr) {
double sum = 0;
int i = 0;
while (i < arr.length) {
sum += arr[i];
i++;
}
return sum;
}
}