Python solution to Code Jam's 'Rounding Error'
1. Review

It is hard to test this code because it gets its data from standard input.

This means that in order to test it or measure its performance you have to write the test case to a file and then run the code with standard input redirected from that file. It would be easier to test if the code were refactored so that the input-reading part of the code was in a separate function from the problem-solving part, like this:

from functools import reduce

def gen_sums(total, freq, remaining):
    """Generate percentages' sums"""
    if not remaining:
        yield reduce(lambda x, y: x + (y*100+total//2)//total, freq, 0)
    else:
        seen = set()
        for i in range(len(freq)):
            if not freq[i] in seen:
                yield from gen_sums(total,
                                    freq[:i] + [freq[i]+1] + freq[i+1:],
                                    remaining-1)
                seen.add(freq[i])
        yield from gen_sums(total, freq+[1], remaining-1)

def max_percentage(total_people, languages_frequency):
    if not 100 % total_people:
        return 100
    not_responded = total_people - sum(languages_frequency)
    return max(gen_sums(total_people, languages_frequency, not_responded))

def main():
    T = int(input())
    for i in range(1, T+1):
        total_people, num_languages = map(int, input().split())
        languages_frequency = [int(x) for x in input().split()]
        result = max_percentage(total_people, languages_frequency)
        print('Case #{}: {}'.format(i, result))


Now it's easy to test the code from the interactive interpreter or from a unit test, for example:

&gt;&gt;&gt; max_percentage(11, [1, 2, 3, 4])
99


and easy to measure its performance:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:max_percentage(14, []), number=1)
8.237278351996792


2. Performance

As demonstrated above, the code in the post takes more than 8 seconds to figure out that when there are 14 voters (and no votes cast yet), the maximum rounded percentage is 101%.

Why does the code in the post take so long to solve this problem? Well, it's because it carries out a search over all possible assignments of votes. But if there are \$n\$ voters then there are of the order of $$\exp{\pi\sqrt {2n \over 3}}$$ possible assignments of votes (see the asymptotic formula for the partition numbers) and so the runtime is exponential in the number of votes.

But in fact the problem is easy to solve by hand with a little bit of mathematics. If there are 14 voters, then each vote is worth \${100 \over 14} = 7{1\over7}\$ percent, and so four votes are worth \$28{4\over7}\$ percent, which rounds up to 29. Fewer than four votes will round down, and more than four will be wasteful since the extra votes over four could be used to contribute to another block of four votes. So the maximum rounded percentage is found when we group as many of the votes as possible into blocks of four votes. In this case there are three such blocks, leaving two votes over, giving a rounded total of \$29·3 + 14 = 101\$.

Similar analysis shows that if there are 19 voters, then each voter contributes \${100\over19} = 5{5\over19}\$ percent, and so it is most efficient to put voters in pairs, because two votes contibute \$10{10\over19}\$ percent, which rounds up to 11. So we have nine pairs of votes and one left over, giving a rounded total of \$11·9 + 5 = 104\$. But it will be a very long time before max_percentage(19, []) returns the result.

So searching over all possible assignments of votes is not going to work even for moderately large problem sizes. Instead, you need to program the kind of mathematical analysis that I carried out in the examples above. I'm not going to spoil the problem for you by giving away my solution, but I'll just show one performance measurement:

&gt;&gt;&gt; timeit(lambda:max_percentage2(14, []), number=1)
0.00011452200124040246


This is more than 70,000 times faster than the code in the post.