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.
