We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Best I could get in Python, but 6 testcases still timing out:
#!/bin/python3importsysclassTrieNode:def__init__(self):self.children={}self.failure_link=Noneself.output=[]defbuild_ac_table(genes):root=TrieNode()# Build the Triefori,patterninenumerate(genes):node=rootforcharinpattern:ifcharnotinnode.children:node.children[char]=TrieNode()node=node.children[char]node.output.append((pattern,i))# Build failure links using BFSqueue=[root]whilequeue:current_node=queue.pop(0)forkey,child_nodeincurrent_node.children.items():queue.append(child_node)ifcurrent_node==root:child_node.failure_link=rootelse:failure_node=current_node.failure_linkwhilefailure_nodeandkeynotinfailure_node.children:failure_node=failure_node.failure_linkchild_node.failure_link=failure_node.children[key]iffailure_nodeelserootchild_node.output+=child_node.failure_link.outputreturnrootdefsearch_ac_table(text,ac_table,health,first,last):current_state=ac_table#StartattherootoftheAho-CorasickTrietotal_health=0fori,charinenumerate(text):whilecurrent_state!=ac_tableandcharnotincurrent_state.children:current_state=current_state.failure_linkifcharincurrent_state.children:current_state=current_state.children[char]else:current_state=ac_tableforoincurrent_state.output:gene_index=o[1]iffirst<=gene_index<=last:# pattern = o[0]# position = i - len(pattern) + 1total_health+=health[gene_index]returntotal_healthif__name__=='__main__':n=int(input().strip())genes=input().rstrip().split()health=list(map(int,input().rstrip().split()))s=int(input().strip())ac_table=build_ac_table(genes)unhealthiest,healthiest=sys.maxsize,0fors_itrinrange(s):first_multiple_input=input().rstrip().split()first=int(first_multiple_input[0])last=int(first_multiple_input[1])d=first_multiple_input[2]d_total_ghealth=search_ac_table(d,ac_table,health,first,last)unhealthiest=min(d_total_ghealth,unhealthiest)healthiest=max(d_total_ghealth,healthiest)print(unhealthiest,healthiest)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Determining DNA Health
You are viewing a single comment's thread. Return to all comments →
Best I could get in Python, but 6 testcases still timing out: