[gcj] Could someone help me to understand why my implementation for Bit Party gives wrong answer? (Java)

[Ricola]

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.