Tasks Details
hard
1.
WireBurnouts
While removing edges from a mesh grid, find the moment when there ceases to be a connection between opposite corners.
Task Score
100%
Correctness
100%
Performance
100%
There is an N × N square mesh-shaped grid of wires, as shown in a figure below. Nodes of the grid are at points (X, Y), where X and Y are integers from 0 to N−1. An electric current flows through the grid, between the nodes at (0, 0) and (N−1, N−1).
Initially, all the wires conduct the current, but the wires burn out at a rate of one per second. The burnouts are described by three arrays of integers, A, B and C, each of size M. For each moment T (0 ≤ T < M), in the T-th second the wire between nodes (A[T], B[T]) and:
- (A[T], B[T] + 1), if C[T] = 0 or
- (A[T] + 1, B[T]), if C[T] = 1
burns out. You can assume that the arrays describe existing wires, and that no wire burns out more than once. Your task is to determine when the current stops flowing between the nodes at (0,0) and (N−1,N−1).
Write a function:
def solution(N, A, B, C)
that, given integer N and arrays A, B and C, returns the number of seconds after which the current stops flowing between the nodes at (0, 0) and (N−1, N−1). If the current keeps flowing even after all M wires burn out, the function should return −1.
For example, given N = 4, M = 9 and the following arrays:
A[0] = 0 B [0] = 0 C[0] = 0 A[1] = 1 B [1] = 1 C[1] = 1 A[2] = 1 B [2] = 1 C[2] = 0 A[3] = 2 B [3] = 1 C[3] = 0 A[4] = 3 B [4] = 2 C[4] = 0 A[5] = 2 B [5] = 2 C[5] = 1 A[6] = 1 B [6] = 3 C[6] = 1 A[7] = 0 B [7] = 1 C[7] = 0 A[8] = 0 B [8] = 0 C[8] = 1your function should return 8, because just after the eighth wire burns out, there is no connection between the nodes at (0, 0) and (N−1, N−1). This situation is shown in the following figure:
Given N = 4, M = 1 and the following arrays:
A[0] = 0 B [0] = 0 C[0] = 0your function should return −1, because burning out a single wire cannot break the connection between the nodes at (0, 0) and (N−1, N−1).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..400];
- M is an integer within the range [0..2*N*(N-1)];
- each element of arrays A and B is an integer within the range [0..N-1];
- each element of array C is an integer that can have one of the following values: 0, 1.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 69 minutes
Notes
not defined yet
Task timeline
Code: 13:01:05 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.048 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:01:18 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
Code: 13:02:59 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = zip(A,B,C)
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:03:35 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set(zip(A,B))
print burnouts
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
set([(0, 1), (3, 2), (1, 3), (2, 1), (0, 0), (2, 2), (1, 1)]) Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
set([(0, 0)]) Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:05:03 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] = 0:
burnouts.add((A[idx], B[idx+1]))
else:
burnouts.add((A[idx], B[idx+1]))
print burnouts
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 70
if C[idx] = 0:
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 70
if C[idx] = 0:
^
SyntaxError: invalid syntax
Code: 13:05:16 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx+1]))
else:
burnouts.add((A[idx+1], B[idx]))
print burnouts
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 180, in <module>
result = solution ( N, A, B, C )
File "user.py", line 73, in solution
burnouts.add((A[idx+1], B[idx]))
IndexError: list index out of range
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 180, in <module>
result = solution ( N, A, B, C )
File "user.py", line 71, in solution
burnouts.add((A[idx], B[idx+1]))
IndexError: list index out of range
Code: 13:05:42 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
print burnouts
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
set([(0, 1), (1, 2), (3, 2), (3, 3), (2, 1), (2, 3), (2, 2), (1, 0), (0, 2)]) Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
set([(0, 1)]) Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:07:02 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = [0] * N * N + 2
print grid
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 182, in <module>
result = solution ( N, A, B, C )
File "user.py", line 75, in solution
grid = [0] * N * N + 2
TypeError: can only concatenate list (not "int") to list
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 182, in <module>
result = solution ( N, A, B, C )
File "user.py", line 75, in solution
grid = [0] * N * N + 2
TypeError: can only concatenate list (not "int") to list
Code: 13:07:17 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = [0] * (N * N + 2)
print grid
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.048 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:07:45 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
print grid
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.048 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:08:14 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1])
print grid
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 79
print grid
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.036 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 79
print grid
^
SyntaxError: invalid syntax
Code: 13:08:20 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1]))
print grid
return
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n'] Invalid result type, int expected, <type 'NoneType'> found.
Code: 13:08:32 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (N * N + 2)
uf.union((grid[0], grid[1]))
print grid
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
Code: 13:09:14 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print grid
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
1.
0.064 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
Code: 13:09:49 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = ['n'] * (grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print uf[grid[0]]
print grid
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
n ['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
n ['n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n', 'n']
Code: 13:10:13 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]+1))
else:
burnouts.add((A[idx]+1, B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
print uf[grid[0]]
print grid
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
1.
0.064 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
Code: 13:16:03 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A && self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.036 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 71
return self.A == other.A && self.B == other.B
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 71
return self.A == other.A && self.B == other.B
^
SyntaxError: invalid syntax
Code: 13:16:13 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add((A[idx], B[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 92
return 0
^
IndentationError: expected an indented block
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 92
return 0
^
IndentationError: expected an indented block
Code: 13:16:47 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 92
return 0
^
IndentationError: expected an indented block
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 92
return 0
^
IndentationError: expected an indented block
Code: 13:17:05 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 195, in <module>
result = solution ( N, A, B, C )
File "user.py", line 81, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
TypeError: unhashable instance
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 195, in <module>
result = solution ( N, A, B, C )
File "user.py", line 81, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
TypeError: unhashable instance
Code: 13:17:58 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash(tuple(self))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 198, in <module>
result = solution ( N, A, B, C )
File "user.py", line 84, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
File "user.py", line 74, in __hash__
return hash(tuple(self))
TypeError: iteration over non-sequence
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 198, in <module>
result = solution ( N, A, B, C )
File "user.py", line 84, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
File "user.py", line 74, in __hash__
return hash(tuple(self))
TypeError: iteration over non-sequence
Code: 13:18:29 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash(tuple(self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 198, in <module>
result = solution ( N, A, B, C )
File "user.py", line 84, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
File "user.py", line 74, in __hash__
return hash(tuple(self.A, self.B))
TypeError: tuple() takes at most 1 argument (2 given)
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 198, in <module>
result = solution ( N, A, B, C )
File "user.py", line 84, in solution
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
File "user.py", line 74, in __hash__
return hash(tuple(self.A, self.B))
TypeError: tuple() takes at most 1 argument (2 given)
Code: 13:18:44 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
1.
0.056 s
WRONG ANSWER,
got 0 expected -1
Code: 13:18:57 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404e094c>, <__main__.Wrapper instance at 0x404e092c>, <__main__.Wrapper instance at 0x404e08cc>, <__main__.Wrapper instance at 0x404e08ec>, <__main__.Wrapper instance at 0x404e090c>])
1.
0.052 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404e08cc>])
Code: 13:19:31 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper:", self.A, self.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df9ec>, <__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df9ac>])
1.
0.056 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df96c>])
Code: 13:20:41 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper:", self.A, self.B
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df9ec>, <__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df9ac>])
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df96c>])
Code: 13:21:20 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B
def __hash__(self):
return hash((self.A, self.B))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df9cc>, <__main__.Wrapper instance at 0x404df9ac>, <__main__.Wrapper instance at 0x404df94c>, <__main__.Wrapper instance at 0x404df96c>, <__main__.Wrapper instance at 0x404df98c>])
1.
0.064 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df94c>])
Code: 13:22:00 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df98c>, <__main__.Wrapper instance at 0x404df94c>, <__main__.Wrapper instance at 0x404df9ac>, <__main__.Wrapper instance at 0x404df92c>, <__main__.Wrapper instance at 0x404df96c>])
1.
0.052 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
set([<__main__.Wrapper instance at 0x404df92c>])
Code: 13:22:41 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
w = Wrapper(A[idx], B[idx], C[idx])
print w
burnouts.add(w)
print burnouts
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 0, b is 0 Wrapper: a is 1, b is 1 Wrapper: a is 2, b is 1 Wrapper: a is 3, b is 2 Wrapper: a is 0, b is 1 set([<__main__.Wrapper instance at 0x404e098c>, <__main__.Wrapper instance at 0x404e094c>, <__main__.Wrapper instance at 0x404e09ac>, <__main__.Wrapper instance at 0x404e092c>, <__main__.Wrapper instance at 0x404e096c>])
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 0, b is 0 set([<__main__.Wrapper instance at 0x404e092c>])
Code: 13:23:13 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s" % (self.A, self.B)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.064 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 3, b is 2 Wrapper: a is 1, b is 1 Wrapper: a is 0, b is 1 Wrapper: a is 0, b is 0 Wrapper: a is 2, b is 1
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 0, b is 0
Code: 13:23:43 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 0, b is 1, c is 0 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 2, b is 1, c is 0
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 0, b is 0, c is 0
Code: 13:24:25 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
if C[idx] == 0:
print "inserting", A[idx], B[idx], C[idx]
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
inserting 0 0 0 inserting 1 1 0 inserting 2 1 0 inserting 3 2 0 inserting 0 1 0 Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 0, b is 1, c is 0 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 2, b is 1, c is 0
1.
0.068 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
inserting 0 0 0 Wrapper: a is 0, b is 0, c is 0
Code: 13:24:51 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
for element in burnouts:
print element
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
pass
return 0
Analysis
expand all
Example tests
1.
0.064 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 3, b is 2, c is 0 Wrapper: a is 1, b is 1, c is 0 Wrapper: a is 2, b is 1, c is 0 Wrapper: a is 2, b is 2, c is 1 Wrapper: a is 0, b is 0, c is 1 Wrapper: a is 1, b is 3, c is 1 Wrapper: a is 0, b is 0, c is 0 Wrapper: a is 1, b is 1, c is 1 Wrapper: a is 0, b is 1, c is 0
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
Wrapper: a is 0, b is 0, c is 0
Code: 13:28:10 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N-1
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != N-1
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != N-1
^
SyntaxError: invalid syntax
Code: 13:28:30 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != (N-1)
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != (N-1)
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != (N-1)
^
SyntaxError: invalid syntax
Code: 13:29:14 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != N
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 95
if (left_right, top_down, 0) not in burnouts and top_down != N
^
SyntaxError: invalid syntax
Code: 13:29:24 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if (left_right, top_down, 0) not in burnouts and top_down != N-1 :
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.036 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 98
return 0
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 98
return 0
^
SyntaxError: invalid syntax
Code: 13:29:38 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and (left_right, top_down, 0) not in burnouts :
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.036 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 98
return 0
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 98
return 0
^
SyntaxError: invalid syntax
Code: 13:30:09 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and (left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 201, in <module>
result = solution ( N, A, B, C )
File "user.py", line 95, in solution
if top_down != N-1 and (left_right, top_down, 0) not in burnouts:
File "user.py", line 71, in __eq__
return self.A == other.A and self.B == other.B and self.C == other.C
AttributeError: 'tuple' object has no attribute 'A'
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 201, in <module>
result = solution ( N, A, B, C )
File "user.py", line 95, in solution
if top_down != N-1 and (left_right, top_down, 0) not in burnouts:
File "user.py", line 71, in __eq__
return self.A == other.A and self.B == other.B and self.C == other.C
AttributeError: 'tuple' object has no attribute 'A'
Code: 13:30:42 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
1.
0.052 s
WRONG ANSWER,
got 0 expected -1
Code: 13:31:16 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[1]))
uf.union((grid[grid_size], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
1.
0.064 s
WRONG ANSWER,
got 0 expected -1
Code: 13:32:16 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[0]
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 100
if uf[0]
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 100
if uf[0]
^
SyntaxError: invalid syntax
Code: 13:32:35 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
1.
0.052 s
WRONG ANSWER,
got 0 expected -1
Code: 13:33:29 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 2 down not in list 1 0 down not in list 1 2 down not in list 2 0 down not in list 2 2 down not in list 3 0 down not in list 3 1 down not in list
1.
0.056 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 1 down not in list 0 2 down not in list 1 0 down not in list 1 1 down not in list 1 2 down not in list 2 0 down not in list 2 1 down not in list 2 2 down not in list 3 0 down not in list 3 1 down not in list 3 2 down not in list
Code: 13:34:05 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 1 right not in list 0 2 down not in list 0 2 right not in list 0 3 right not in list 1 0 down not in list 1 0 right not in list 1 2 down not in list 1 2 right not in list 2 0 down not in list 2 0 right not in list 2 1 right not in list 2 2 down not in list 2 3 right not in list 3 0 down not in list 3 1 down not in list
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 0 right not in list 0 1 down not in list 0 1 right not in list 0 2 down not in list 0 2 right not in list 0 3 right not in list 1 0 down not in list 1 0 right not in list 1 1 down not in list 1 1 right not in list 1 2 down not in list 1 2 right not in list 1 3 right not in list 2 0 down not in list 2 0 right not in list 2 1 down not in list 2 1 right not in list 2 2 down not in list 2 2 right not in list 2 3 right not in list 3 0 down not in list 3 1 down not in list 3 2 down not in list
Code: 13:34:26 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid_size]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16
1.
0.056 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16
Code: 13:34:43 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid_size], uf[grid_size+1]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17
Code: 13:36:56 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print grid[grid_size-1], uf[grid_size], uf[grid_size+1]
if uf[grid_size] == uf[grid_size+1]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
15 16 17
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
15 16 17
Code: 13:38:01 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
1.
0.056 s
WRONG ANSWER,
got 0 expected -1
Code: 13:38:21 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[grid_size]], uf[grid[grid_size+1]]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.048 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17
1.
0.048 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17
Code: 13:39:30 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17 16 17
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 17 16 17
Code: 13:39:46 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 16 17 16 17
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
8 16 17 16 17
Code: 13:40:00 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.068 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 16 17 0 16 17
1.
0.052 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
8 16 17 8 16 17
Code: 13:40:34 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union((grid[0], grid[grid_size]))
uf.union((grid[grid_size-1], grid[grid_size+1]))
print uf[grid[0]], uf[grid[grid_size]]
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 16 0 16 17 0 16 17
1.
0.060 s
WRONG ANSWER,
got 0 expected -1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 16 8 16 17 8 16 17
Code: 13:42:35 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
print uf[grid[0]], uf[grid[grid_size]], uf[grid[grid_size+1]]
print uf[0], uf[grid_size], uf[grid_size+1]
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
16 16 12 16 16 12
1.
0.060 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
8 8 8 8 8 8
Code: 13:42:50 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
return 0
Analysis
Code: 13:43:38 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 107
return 0
^
IndentationError: expected an indented block
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 107
return 0
^
IndentationError: expected an indented block
Code: 13:43:47 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
print idx
return 0
Analysis
expand all
Example tests
1.
0.052 s
WRONG ANSWER,
got 0 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
8 7 6 5 4 3 2 1 0
1.
0.048 s
OK
Code: 13:46:24 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 107
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]])
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 107
uf.union(grid[A[idx]*N+B[idx], grid[(A[idx]+1)*N+B[idx]])
^
SyntaxError: invalid syntax
Code: 13:47:05 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
Analysis
Code: 13:47:38 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
# print left_right, top_down, "down not in list"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
# print left_right, top_down, "right not in list"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
Analysis
Code: 13:48:00 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
Analysis
Code: 13:48:44 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
User test case 1:
[4, [0], [0], [0]]
Analysis
Code: 13:49:05 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+2
return 0
User test case 1:
[4, [0, 0], [0, 0], [0, 1]]
Analysis
Code: 13:49:34 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 0], [0, 0], [0, 1]]
Analysis
Code: 13:50:07 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 13:58:27 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 13:58:37 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 13:58:53 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 1:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 13:59:05 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(left_right, top_down, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(left_right, top_down, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:01:55 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:03:00 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if Wrapper(top_down, left_right, 0) not in burnouts:
assert top_down != N-1
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 216, in <module>
result = solution ( N, A, B, C )
File "user.py", line 96, in solution
assert top_down != N-1
AssertionError
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 216, in <module>
result = solution ( N, A, B, C )
File "user.py", line 96, in solution
assert top_down != N-1
AssertionError
expand all
User tests
1.
0.052 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 216, in <module>
result = solution ( N, A, B, C )
File "user.py", line 96, in solution
assert top_down != N-1
AssertionError
Code: 14:03:26 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx]+1)*N+B[idx]])
else:
uf.union(grid[A[idx]*N+B[idx]], grid[(A[idx])*N+B[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:03:56 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:04:54 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top", did not burn out
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right", did not burn out
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
expand all
Example tests
example1
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.032 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 96
print top_down, left_right, " to top", did not burn out
^
SyntaxError: invalid syntax
example2
example from the problem statement
example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 96
print top_down, left_right, " to top", did not burn out
^
SyntaxError: invalid syntax
expand all
User tests
1.
0.028 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
File "user.py", line 96
print top_down, left_right, " to top", did not burn out
^
SyntaxError: invalid syntax
Code: 14:05:10 UTC,
py,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(A[idx], B[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top did not burn out"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right did not burn out"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
expand all
Example tests
1.
0.064 s
WRONG ANSWER,
got 9 expected 8
stderr:
WARNING: producing output may seriously slow down your code!stdout:
1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to right did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out
1.
0.060 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 0 to right did not burn out 1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to top did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out
expand all
User tests
1.
0.064 s
OK
function result: 3
function result: 3
stderr:
WARNING: producing output may seriously slow down your code!stdout:
1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out
Code: 14:05:44 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
print top_down, left_right, " to top did not burn out"
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
print top_down, left_right, " to right did not burn out"
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
expand all
Example tests
1.
0.052 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out
1.
0.056 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
0 0 to right did not burn out 1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to top did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out
expand all
User tests
1.
0.052 s
OK
function result: 3
function result: 3
stderr:
WARNING: producing output may seriously slow down your code!stdout:
1 0 to top did not burn out 1 0 to right did not burn out 2 0 to top did not burn out 2 0 to right did not burn out 3 0 to right did not burn out 0 1 to top did not burn out 0 1 to right did not burn out 1 1 to right did not burn out 2 1 to top did not burn out 2 1 to right did not burn out 3 1 to right did not burn out 0 2 to top did not burn out 0 2 to right did not burn out 1 2 to top did not burn out 1 2 to right did not burn out 2 2 to top did not burn out 2 2 to right did not burn out 3 2 to right did not burn out 0 3 to top did not burn out 1 3 to top did not burn out 2 3 to top did not burn out
Code: 14:05:57 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:06:11 UTC,
py,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
User test case 1:
[4, [0, 1, 0], [0, 1, 0], [0, 0, 1]]
Analysis
Code: 14:06:16 UTC,
py,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
"""UnionFind.py
Union-find data structure. Based on Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
with significant additional changes by D. Eppstein.
"""
class UnionFind:
"""Union-find data structure.
Each unionFind instance X maintains a family of disjoint sets of
hashable objects, supporting the following two methods:
- X[item] returns a name for the set containing the given item.
Each set is named by an arbitrarily-chosen one of its members; as
long as the set remains unchanged it will keep the same name. If
the item is not yet part of a set in X, a new singleton set is
created for it.
- X.union(item1, item2, ...) merges the sets containing each item
into a single larger set. If any item is not yet part of a set
in X, it is added to X as one of the members of the merged set.
"""
def __init__(self):
"""Create a new empty union-find structure."""
self.weights = {}
self.parents = {}
def __getitem__(self, object):
"""Find and return the name of the set containing the object."""
# check for previously unknown object
if object not in self.parents:
self.parents[object] = object
self.weights[object] = 1
return object
# find path of objects leading to the root
path = [object]
root = self.parents[object]
while root != path[-1]:
path.append(root)
root = self.parents[root]
# compress the path and return
for ancestor in path:
self.parents[ancestor] = root
return root
def __iter__(self):
"""Iterate through all items ever found or unioned by this structure."""
return iter(self.parents)
def union(self, *objects):
"""Find the sets containing the objects and merge them all."""
roots = [self[x] for x in objects]
heaviest = max([(self.weights[r],r) for r in roots])[1]
for r in roots:
if r != heaviest:
self.weights[heaviest] += self.weights[r]
self.parents[r] = heaviest
class Wrapper:
def __init__(self, A, B, C):
self.A = A
self.B = B
self.C = C
def __eq__(self, other):
return self.A == other.A and self.B == other.B and self.C == other.C
def __hash__(self):
return hash((self.A, self.B, self.C))
def __str__(self):
return "Wrapper: a is %s, b is %s, c is %s" % (self.A, self.B, self.C)
def solution(N, A, B, C):
uf = UnionFind()
grid_size = N*N
burnouts = set()
for idx in xrange(len(A)):
burnouts.add(Wrapper(B[idx], A[idx], C[idx]))
grid = range(grid_size + 2)
uf.union(grid[0], grid[grid_size])
uf.union(grid[grid_size-1], grid[grid_size+1])
for left_right in xrange(N):
for top_down in xrange(N):
if top_down != N-1 and Wrapper(top_down, left_right, 0) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[(top_down+1)*N+left_right])
if left_right != N-1 and Wrapper(top_down, left_right, 1) not in burnouts:
uf.union(grid[top_down*N+left_right], grid[top_down*N+(left_right+1)])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return -1
for idx in reversed(xrange(len(C))):
if C[idx] == 0:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx]+1)*N+A[idx]])
else:
uf.union(grid[B[idx]*N+A[idx]], grid[(B[idx])*N+A[idx]+1])
if uf[grid[grid_size]] == uf[grid[grid_size+1]]:
return idx+1
return 0
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N**2*log(N)) or O(N**2*log(log(N)))
expand all
Correctness tests
1.
0.060 s
OK
1.
0.060 s
OK
1.
0.052 s
OK
1.
0.060 s
OK
1.
0.052 s
OK
1.
0.060 s
OK
1.
0.060 s
OK
expand all
Performance tests
1.
0.088 s
OK
1.
0.204 s
OK
1.
0.728 s
OK
1.
1.320 s
OK
1.
2.104 s
OK
1.
5.540 s
OK