TCO 2016 Round1 Med

ElliSocks.py

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class EllysSocks:
    def getDifference(self, S, P):
        INF = 100000000000
        S = list(S)
        S.append(0)
        S.sort()
    
        N = len(S)
        PAIR = len(S) / 2
    
        dp = [[INF for _ in xrange(PAIR + 1)] for _ in xrange(N)]
        for i in xrange(N):
            dp[i][0] = -1
    
        for i in xrange(2, N):
            for pair in xrange(PAIR):
                # Select
                dp[i][pair + 1] = min(dp[i][pair + 1], max(dp[i - 2][pair], S[i] - S[i - 1]))
    
                # Unselect                
                dp[i][pair] = min(dp[i][pair], dp[i - 1][pair])
    
        return dp[len(S) - 1][P]