Hi guys, I've been trying question 3 from round 2 last year and am not sure whether I am getting a TLE error because I am not fast enough or because of the programming language. I believe the following is O(N^3) - if anybody has any ideas that would be a big help!:
class Graph: def __init__(self, graph): self.graph = graph self.nodes = len(graph) #- number of nodes def dfs_path(self, start, end): #- returns the path from start to end, otherwise returns False queue = [(start, [start])] while queue: (vertex, path) = queue.pop() for neighbour in self.graph[vertex] - set(path): if neighbour == end: return path + [neighbour] else: queue.append((neighbour, path + [neighbour])) return False def reverse_edge(self, v1, v2): #- reverses the edge v1 -> v2 to v2 -> v1 self.graph[v1].remove(v2) self.graph[v2].add(v1) def mcbm(self): n =(self.nodes // 2) count = 0 self.graph["source"] = set(range(n)) #-- row nodes are (0, 1, ..., n-1) self.graph["sink"] = set() for node in range(n, 2*n): self.graph[node].add("sink") #-- column nodes are (n, n+1, ..., 2*n-1) while self.dfs_path("source", "sink"): #-- while there exists a path path = self.dfs_path("source", "sink") length = len(path) L = path[1] #-- L exposed node R = path[length-2] #-- R exposed node count += 1 self.graph["source"].remove(L) #--- disconnect L, R from source, sink self.graph[R].remove("sink") for i in range(1, length-2): #--- reverse all the edges in path between L and R self.reverse_edge(path[i], path[i+1]) return count def coords_to_graph(coords, n): #--- converts set of coordinates on a n by n grid to a graph nodes = [int(x) for x in range(2*n)] #--- nodes are (0, n) for rows and (n, 2n) for cols graph = {} for node in nodes: graph[node] = set() for coord in coords: #--- connect the node for row x to the node for column y (i.e. node y+n) x, y = coord[0], coord[1] graph[x].add(y+n) return graph def solve(): n = int(input()) colour_dict = {} for colour in range(1, 2*n+1): #--- the colours are 1, 2, ..., n and -1, -2, ..., n colour_dict[colour] = set() #--- this corresponds to 1, 2, ..., 2n (mod 2n+1) for row in range(n): cur_row = [int(x) for x in input().split()] for index, value in enumerate(cur_row): colour = value % (2*n+1) #--- basically convert the -ve numbers to n+1, n+2, ..., 2n colour_dict[colour].add((row, index)) for colour in colour_dict: cur_graph = Graph(coords_to_graph(colour_dict[colour], n)) result = (len(colour_dict[colour]) - cur_graph.mcbm()) yield result #------ t = int(input()) for case in range(t): print ("Case #" + str(case + 1) + ": " + str(sum(solve()))) -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/844e156a-7e37-4a6a-b37b-41858fc73187%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.