Home » programming » Code jam: 1st problem

# Code jam: 1st problem

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[1])
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):
total = sum(s)
sorted_index = sorted_keys(s)
percentage = []
for i in range(len(s)):
j = sorted_index[i]
try:
except IndexError:
a = 0
percentage.append(100 *a/total)

return percentage

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[0], a[1:]
print('Case #' + str(i) + ': ', end='')