The proof of the statement in the analysis is likely very complex. I tried for
some time, but didn't get the proof done (or refuted).
Anyway, the statement "We get the maximum answer when as many of these as
possible are rounded up." is different from your post title ("we must maximize
the number of rounded up languages").
Your statement turns out to be false anyway. Consider the percentages (49.5,
49.5, 1) and (49.6, 49.6, 0.8) has the same total rounded percentage. And
(49.5, 49.5, 1) is obviously NOT maximizing the number of rounded up languages.
And this case is possible in the problem when n=1000, known number of votes for
each language = (495, 495, 8). You have only 2 votes to assign, and that has
clearly no effect with the total. But putting that (495, 495, 10) does not
maximizing the number of rounded up languages.
On Sunday, May 13, 2018 at 1:17:35 AM UTC, Ricola wrote:
> Hello all,
>
> In the analysis for test set 3, it's written "We get the maximum answer when
> as many of these as possible are rounded up.".
>
> When I tried to solve it by myself I also thought about maximizing the number
> of rounded up languages but there was no way to prove myself that it would be
> the optimal solution. So I thought that I was taking a wrong direction. Then
> I saw in the analysis that it was but there is no mathematical proof.
>
> For example let's say that I have [49.5 49.5 1], if you round them up you get
> [50 50 1] and the total is 101.
> Now let's say that I have [32.9 32.9 32.9 1.3], if you round them up you get
> [33 33 33 1] and the total is 100.
>
> However in the first case you rounded 2 languages and in the second case you
> rounded 3 languages. (Yes you will tell me that they would correspond to
> different distributions but since the theorem is true, it's normal that I
> cannot find a complete counter-example).
>
> If somebody has some mathematical (or pseudo-mathematical proof) that
> maximising the number of rounded languages maximises the sum that would be
> nice :-)
--
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/0f8da8ce-7fac-46ab-b406-807623f20a07%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
