solution to codility challenge https://codility.com/programmers/challenges/magnesium2014
def solution(N, A, B, C): | |
edges = [(C[i],A[i],B[i]) for i in xrange(len(A))] | |
edges.sort(key=lambda e: e[0]) | |
maxLenAt = [0]*N | |
costAt = [0]*N | |
def updatePath(u,costu,lenu, v,costv, lenv, cost): | |
if costu < cost and lenu+1 > lenv: | |
maxLenAt[v] = lenu+1 | |
costAt[v] = cost | |
elif costu == cost and lenv == 0: | |
maxLenAt[v] = 1 | |
costAt[v] = cost | |
for cost,u,v in edges: | |
cost_u,cost_v = costAt[u], costAt[v] | |
len_u, len_v = maxLenAt[u], maxLenAt[v] | |
updatePath(u,cost_u,len_u, v, cost_v, len_v,cost) | |
updatePath(v, cost_v, len_v, u,cost_u,len_u,cost) | |
return max(maxLenAt) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment