hard

1.
WireBurnouts

While removing edges from a mesh grid, find the moment when there ceases to be a connection between opposite corners.
100%

100%

100%

Task description

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:

your 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:

your 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, 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–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Solution

Programming language used Python

Total time used 69 minutes

Effective time used 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

✘

tested program terminated unexpectedly

1.

0.048 s

stdout:

Invalid result type, int expected, <type 'NoneType'> found.

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.052 s

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

1.

0.048 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

stdout:

Invalid result type, int expected, <type 'NoneType'> found.

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.056 s

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

✘

tested program terminated unexpectedly

1.

0.056 s

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

✘

tested program terminated unexpectedly

1.

0.056 s

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

✘

tested program terminated unexpectedly

1.

0.032 s

stderr:

File "user.py", line 70 if C[idx] = 0: ^ SyntaxError: invalid syntax

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.032 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

✘

tested program terminated unexpectedly

1.

0.056 s

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

✘

tested program terminated unexpectedly

1.

0.056 s

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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.048 s

[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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.048 s

['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

✘

tested program terminated unexpectedly

1.

0.032 s

stderr:

File "user.py", line 79 print grid ^ SyntaxError: invalid syntax

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.036 s

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

✘

tested program terminated unexpectedly

1.

0.056 s

['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

✘

tested program terminated unexpectedly

1.

0.056 s

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

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

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

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

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

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

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

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

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

✘

tested program terminated unexpectedly

1.

0.036 s

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

✘

tested program terminated unexpectedly

1.

0.032 s

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

✘

tested program terminated unexpectedly

1.

0.032 s

stderr:

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

stderr:

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.032 s

stderr:

File "user.py", line 92 return 0 ^ IndentationError: expected an indented block

Code: 13:17:05 UTC,
py,
verify,
result: **Failed**

```
"""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

✘

tested program terminated unexpectedly

1.

0.060 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

1.

0.056 s

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

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

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

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

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

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

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

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

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**

```
"""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

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

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

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

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

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

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

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

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

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

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**

```
"""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

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

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.032 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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**

```
"""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

✘

tested program terminated unexpectedly

1.

0.036 s

stderr:

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.028 s

stderr:

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

Code: 13:29:38 UTC,
py,
verify,
result: **Failed**

```
"""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

✘

tested program terminated unexpectedly

1.

0.036 s

stderr:

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.032 s

stderr:

File "user.py", line 98 return 0 ^ SyntaxError: invalid syntax

Code: 13:30:09 UTC,
py,
verify,
result: **Failed**

```
"""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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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**

```
"""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

1.

0.052 s

Code: 13:31:16 UTC,
py,
verify,
result: **Failed**

```
"""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

1.

0.064 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

stderr:

File "user.py", line 100 if uf[0] ^ SyntaxError: invalid syntax

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.028 s

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

1.

0.052 s

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

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

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

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

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

16

1.

0.056 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

16 17

1.

0.048 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

15 16 17

1.

0.060 s

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

1.

0.056 s

Code: 13:38:21 UTC,
py,
verify,
result: **Failed**

```
"""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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

16 17

1.

0.048 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

16 17 16 17

1.

0.060 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

0 16 17 16 17

1.

0.060 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

0 16 17 0 16 17

1.

0.052 s

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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

0 16 0 16 17 0 16 17

1.

0.060 s

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**

```
"""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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

16 16 12 16 16 12

1.

0.060 s

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**

```
"""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

✘

tested program terminated unexpectedly

1.

0.028 s

stderr:

File "user.py", line 107 return 0 ^ IndentationError: expected an indented block

example2

example from the problem statement

example from the problem statement

✘

tested program terminated unexpectedly

1.

0.028 s

stderr:

File "user.py", line 107 return 0 ^ IndentationError: expected an indented block

Code: 13:43:47 UTC,
py,
verify,
result: **Failed**

```
"""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

stderr:

WARNING: producing output may seriously slow down your code!stdout:

8 7 6 5 4 3 2 1 0

1.

0.048 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

✘

tested program terminated unexpectedly

1.

0.032 s

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**

```
"""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**

```
"""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**

```
"""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**

```
"""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**

```
"""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**

```
"""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**

```
"""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

✘

tested program terminated unexpectedly

1.

0.052 s

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

✘

tested program terminated unexpectedly

1.

0.060 s

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

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**

```
"""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**

```
"""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**

```
"""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

✘

tested program terminated unexpectedly

1.

0.032 s

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

✘

tested program terminated unexpectedly

1.

0.028 s

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

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**

```
"""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

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

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

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**

```
"""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

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

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

function result: 3

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**

```
"""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**

```
"""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
**

```
"""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

1.

0.060 s

1.

0.052 s

1.

0.060 s

1.

0.052 s

1.

0.060 s

1.

0.060 s

expand all
**Performance tests**

1.

0.088 s

1.

0.204 s

1.

0.728 s

1.

1.320 s

1.

2.104 s

1.

5.540 s