Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
TopCoder SRM672 Div2
# 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"
# 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)
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment