the original sample is wrong because you shouldn’t compare two totally different cases and count the number of the rounded up languages.
The correct statement is Given an initial state, the answer must have the most rounded up languages, among all reachable states. So you shouldn’t just try to compare two states without mentioning the initial state. On Mon, May 14, 2018 at 8:55 AM Wing-chung Leung <[email protected]> wrote: > 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. > -- 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/CAGDEU-LsjxTX0EZaTQDZJqwcMW-57REQzOwtPMn5DJ%2B1%2Bg%3Di%3DA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
