This stumped me at first as well however check out the following
explanation:
6 9
/ \ / \
3 3 3 6
/ \
3 3
Here you split three times (=3 minutes), then you wait 3 minutes. In total
6 minutes.
Hope that helps.
On Sun, Apr 12, 2015 at 5:06 PM, Michael Frysztacki <[email protected]>
wrote:
> Hi all,
> I think I found a bug in the google jam 2015 evaluation system, it regards
> task "B" - Pancakes House. I have downloaded three different solutions from
> the top players, who scored max (100/100) and all of their code evaluates
> the given case wrongly:
>
> input:
> There are starting two dinners, first has 9 cakes, second 6, so its just:
> [6,9]
>
> the output of all these players evaluated that the shortest time is 6
> minutes,
> while I have written the simple example on paper and have done over 20
> steps it looks for me that the best time is 7 minutes. My algorithm
> evaluates this as well as 7 seconds, which is as following:
>
> /*
> The general idea is add all diners to PriorityQueue and always
> poll the highest dinner ( because thats most feasible chose ),
> divide it for two portions and add it to the queue again. One every step
> check if the time is better regarding additionaly how many minutes you lost
> ( each step is one minute lost ).
> This is a brute force because this operation is done 500000 * n,
> however I think the pattern when to stop is when the dinners become
> stepwise,
> like this:
>
> #
> ##
> ####
> ####
> #####
> ######
> #######
>
> I have a prove for that, but for now it is not worth mentioning
> */
> public static int startEating(int[] input) {
>
> Comparator<Integer> comp = new Comparator<Integer>() {
> @Override
> public int compare(Integer arg0, Integer arg1) {
>
> return arg1.intValue() - arg0.intValue();
> }
> };
>
> PriorityQueue<Integer> diners = new
> PriorityQueue<Integer>(10,comp);
> for (int i = 0; i < input.length; i++) {
> diners.add(input[i]);
> }
> int limit = diners.size() * 500000;
> int pausa = 0;
> int bestScore = diners.peek();
> while (limit-- != 0) {
>
> Integer max = diners.poll();
> int currentHighestTime = max + pausa;
> int portion = currentHighestTime/2;
> int currentDiner = currentHighestTime - portion;
> diners.add(portion - pausa);
> diners.add(currentDiner - pausa);
> pausa++;
> if (diners.peek() + pausa < bestScore) {
> bestScore = diners.peek() + pausa;
> }
> }
> return bestScore;
> }
>
> I wrote this code after the comptetion, unfortunatelly I didn't pass it
> during the contest. Could you please take a look at it ?
> Thanks.
>
> --
> 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 [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/google-code/580dad74-7e01-420d-8fa8-8e67c211e016%40googlegroups.com
> .
> For more options, visit https://groups.google.com/d/optout.
>
--
Michael E. Walker
--
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 [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/CALnYBXVTjkqwuwut2FK2HToynqH2s-JdLYiMC-0w4rt4%2BSmGBw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
