It's just greedy. First of all, if percentage of one language is already rounded up, there is no point to assign any person to it any more.
This is easy to prove. Suppose you have a `best` solution that has ever assign any new persons to it, then it is easy to construct a new solution that assign all these new persons to a new language. The new solution should be no worse than the previous one, so it should also be a `best` solution. Then you can assign the person one by one, giving priorities to the languages that has most round-down because they have better shots to become a round-up. It is very obvious when 100/N is small, say 100/N = 0.01 and one language is at 2.3% and the other one is at 5.4% It is easy to tell that it require more votes to turn 2.3% to 2.5% It become quite different when 100/N is significant large, say 100/N = 0.8 but still, we want to give it to 5.4% 1) if we give it to 5.4%, it becomes 6.2%, so it changes from 0.4% loss to 0.8% gain; 2) if we give it to 2.3%, it becomes 3.1%. so it changes from 0.3% loss to 0.9% gain; you can see there is no difference, we always gain 1.2% no matter which one to assign. in fact, case 2 may still be worse, if after you add the person to it, it still remains in round-down. -- 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/1778633a-a14b-4bbb-8bc8-d25e6ab144cf%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
