The goal is (as the official solution says) to round up as many languages as possible, i.e., you should first satisfy the languages that need the fewest additional votes to do so.
E.g., if the total number of votes N equals 13 and the starting votes are 2 2 2. - You need 2 additional votes to round up a language with 2 votes. - You need 1 additional vote to round up a language with 0 votes. So, it would be optimal to create 7 new languages, which amounts in 7 rounded up languages. What my code does, is - If first gives two additional votes to three existing languages: now, the counts are 4 4 4. - It creates a new language with the remaining single vote. In the end, there are 4 rounded up languages, which seems to be suboptimal. But, the sums of rounded percents are 1) 4 4 4 1 ... 3 * 31 + 1 * 8 = 101 2) 2 2 2 1 1 1 1 1 1 1 .... 3 * 15 + 7 * 8 = 101 However, your notes are useful: - to round up a new language, you need at least 0.5% - to round up an existing language, you need less than 0.5%. And this is the probably the real explanation. Since it contradicts the very first claim (round up as many languages as possible), I will have to think about it a bit. Thank you. Dne četrtek, 03. maj 2018 06.34.23 UTC+2 je oseba /dev/joe napisala: > This is actually what the analysis for the large case describes. Because the > percentages all really sum to 100%, you want to make as many of them round up > as possible. Once one has rounded up, it takes more than an addition of 0.5% > to make it round up to the next integer, but it takes only 0.5% to make a new > language round up, and it takes less than 0.5% to make a language which is > currently rounding down to round up. So you will never add votes to a > language which is already rounding up. > > > On Wed, May 2, 2018 at 9:33 PM Matej P <[email protected]> wrote: > My solution for the problem was marked as a correct one, but I somehow doubt > that it is truly correct, since I was a bit careless. The pseudocode for my > solution is the following: > > > > 1) Figure out how many more votes each of the ALREADY MENTIONED languages > would need in order for it to be rounded up. > > 2) Sort those languages increasingly according to 1). > > 3) Satisfy the 1st language, satisfy the 2nd language ... (if possible). > > > > If there are any votes left: > > 4) Find out how many additional votes a language with 0 votes would need in > order for it to be rounded up. > > 5) Create as many new rounded-up languages as possible. > > > > Clearly, this may lead to a suboptimal solution, but I cannot find an example > where this would really happen. Unfortunately, I am also unable to prove that > there aren't any such examples. > > > > Are you able to prove or disprove that? > > > > -- > > 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/ef9dbb04-4e0e-4dbd-873a-a8edbf776e5d%40googlegroups.com. > > For more options, visit https://groups.google.com/d/optout. -- 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/9ae41103-b611-4f1f-b1b0-b483bcf1c8fb%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
