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):
    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[0], 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()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: