Hello Google Code Jammers! Long story sort : I tried to implement a simple solution for the Test set 1 of Bit Party but I always got a "Wrong Answer" even thought I tried as many edge cases I could think of. Then I gave up and read the analysis. I tried to implement the solution given in the analysis but I always got "Wrong Answer" at the Test set 1 again. Maybe it's the same reason than why my own solution failed, maybe not (if not, I might create a new post about my own solution). It might be something really stupid like an simple edge case that I missed, but I couldn't find it and since we don't have the details when getting "Wrong Answer", it's frustrating.
Here it goes, I actually followed the analysis literally : import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; import java.util.stream.IntStream; import java.util.stream.Stream; import static java.util.stream.Collectors.toList; public class Solution { // No need to read this method public static void main(String[] args) { Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in))); int t = Integer.parseInt(in.nextLine()); for (int i = 1; i <= t; ++i) { String[] line = in.nextLine().split(" "); int R = Integer.parseInt(line[0]); int B = Integer.parseInt(line[1]); int C = Integer.parseInt(line[2]); List<Cashier> cashiers = new ArrayList<>(C); for (int j = 0; j < C; j++) { int[] vals = Stream.of(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); cashiers.add(new Cashier(vals[0], vals[1], vals[2])); } System.out.println("Case #" + i + ": " + solve(R, B, cashiers)); } } public static int solve(int R, int B, List<Cashier> cashiers){ int maxTime = 0; for (Cashier cashier : cashiers) { int t = Math.min(cashier.M,B) * cashier.S + cashier.P; if(t > maxTime) maxTime = t; } //Binary search : invariance : test(a) = false, test(b) = true //we look for lowest b int a = 0, b = maxTime; while(b-a>1){ int m = (a+b)/2; if(test(m, R, B, cashiers)){ b = m; } else { a = m; } } return b; } public static boolean test(int T, int R, int B, List<Cashier> cashiers){ Integer[] capacities = new Integer[cashiers.size()]; for (int i = 0; i < cashiers.size(); i++) { Cashier cashier = cashiers.get(i); //the max(0, ...) is not really necessary I think capacities[i] = Math.max(0, Math.min(cashier.M, (T-cashier.P)/cashier.S)); } Arrays.sort(capacities, Collections.reverseOrder()); for (int i = 0; i < R; i++) { B -= capacities[i]; } return B <= 0; } private static class Cashier { public int M, S, P; public Cashier(int m, int s, int p) { M = m; S = s; P = p; } } } -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/f62e3e73-0f91-4f1b-975b-5871fb95af27%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.