TopCoder SRM672 Div2

srm672_div2_a_SetPartialOrder.py

# SRM 672 Div2 Easy
class SetPartialOrder():
    def compareSets(self, a, b):
        seta = set(a)
        setb = set(b)
        if seta == setb:
            return "EQUAL"
        elif seta.issubset(setb):
            return "LESS"
        elif setb.issubset(seta):
            return "GREATER"
        else:
            return "INCOMPARABLE"

srm672_div2_b_SubstitutionCipher.py

# SRM 672 Div2 Medium
import string
class SubstitutionCipher():
    def decode(self, a, b, y):
        substitution_table = {}
        for k in list(string.ascii_uppercase):
            substitution_table[k] = ""
        listb = list(b)
        lista = list(a)
        for k, v in zip(listb, lista):
            substitution_table[k] = v
        if len([i for i in substitution_table.values() if i == ""]) == 1:
            missingkey = [k for k in substitution_table if substitution_table[k] == ""][0]
            missingvalue = list(set(list(string.ascii_uppercase)).difference(set(substitution_table.values())))[0]
            substitution_table[missingkey] = missingvalue
        listy = list(y)
        y_decoded = []
        for k in listy:
            if substitution_table[k] == "":
                return ""
            else:
                y_decoded.append(substitution_table[k])
        return "".join(y_decoded)

srm672_div2_c_Tdetectived2.py

# SRM 672 Div2 Hard
# http://kmjp.hatenablog.jp/entry/2015/10/21/0930
class Tdetectived2():
    def reveal(self, s):
        iss = [0] * (1<<18)
        n = len(s)
        val = [0] * 20
        for i in range(n):
            val[i] = 100
        iss[1] = 1
        for mask in range(1<<n):
            if iss[mask]:
                ma = [0] * 20
                for i in range(n):
                    if mask & (1<<i):
                        for j in range(n):
                            ma[j] = max(int(ma[j]), int(s[i][j]))
                md = -1
                ma2 = 0
                for i in range(n):
                    if (mask & (1<<i)) == 0:
                        if md < ma[i]:
                            md = ma[i]
                            ma2 = 0
                        if md == ma[i]:
                            ma2 |= 1<<i
                for i in range(n):
                    if ma2 & (1<<i):
                        iss[mask | (1<<i)] = 1
                        val[i] = min(val[i], bin(mask).count('1'))
        ret = 0
        for i in range(n):
            ret += i * val[i]
        return ret