Even if I phrased it wrongly, I still don't get how we can affirm that "Given an initial state, the answer must have the most rounded up languages, among all reachable states. "
Because what we want to maximize is the sum. Or equally, maximize the value "diff" with diff = sum - 100. What is diff? diff is the sum of all of the rounding errors (taken positive if rounded up, negative if rounded down). But when you round up a number like 1.5 to 2, you add 0.5 to diff. When you round up a number like 1.9 you only add 0.1 to diff. So the quantity of the rounding error is important. I guess it has something to do with the value of the percentages that are all a multiple of the minimum increment (being 100/N), but I still can't explain it clearly. (for example, you would never have to chose between adding 0.5 to 1.0 or to 1.4 to get to either 1.5 or 1.9 because if your increment is 0.5 (which mean N = 200), you will never have an existing percentage of 1.4). @Wing-chung Leung : I don't understand your example. I said that we must we must maximize the number of rounded up languages to get the maximum sum, and you proved me that you can maximize the sum without maximizing the number of rounded up languages. To prove that "A implies B" is false you must find an example of A not implying B but you gave an example of not A that still implies B. -- 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/ee3ea633-9dda-486d-a14c-7a93b8d9cfed%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.