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.
