I found particularly nice the first problem of the CodeJam competition. You can find the description of the problem Safety in Numbers here. The solution is very elegant if you think about it and I wonder why the time limit was so high (8 minutes).
Starting from the worse player, we count how many votes he needs in order to cover his distance with the second player worst player. Now, all the votes are split between these two until they meet the third one and so on…
Before exposing my solution, here are some useful excerpts of code that I didn’t find somewhere else.
Assume a list which contains a permutation.
For instance a random permutation can be derived by
a = list(range(10)) shuffle(a)
Invert a permutation.
def invert_list(l): """ Assuming list l contains a permutation, return the inverse. """ l2 = [True] * len(l) for i, j in enumerate(l): l2[j] = i return l2
Sort the list but instead of returning the sorted values, return the corresponding mapping of the keys.
def sorted_keys(s): """ Return a list with the indices sorted. """ index_score = list(zip(list(range(len(s))), s)) index_score.sort(key=lambda t: t) sorted_index, sorted_s = zip(*index_score) sorted_index = list(sorted_index) return invert_list(sorted_index)
The rest of my solution
def how_many_votes(s): votes = compute_needed_votes(s) total = sum(s) sorted_index = sorted_keys(s) percentage =  for i in range(len(s)): j = sorted_index[i] try: a = sum(votes[j:]) except IndexError: a = 0 percentage.append(100 *a/total) return percentage def compute_needed_votes(s): remaining_points = sum(s) previous_p = 0 difference =  sorted_s = sorted(s) for i, p in enumerate(sorted_s): # warning: i is 0 based if remaining_points <= 0: break if i == 0: # first player previous_p = p continue if i*(p - previous_p) > remaining_points: difference.append(remaining_points/i) remaining_points = 0 break difference.append(p - previous_p) remaining_points -= i*(p - previous_p) previous_p = p if remaining_points > 0: difference.append(remaining_points/len(s)) return difference def main(): testcases = int(input()) for i in range(1, testcases + 1): a = [int(x) for x in input().split()] N, s = a, a[1:] print('Case #' + str(i) + ': ', end='') votes = how_many_votes(s) for v in votes: print(str(v), end=' ') print() if __name__ == '__main__': main()