Tasks Details
hard
1.
SpeedCameras
Position speed cameras so as to minimize the lengths of unmonitored paths.
Task Score
100%
Correctness
100%
Performance
100%
Recently, more and more illegal street races have been spotted at night in the city, and they have become a serious threat to public safety. Therefore, the Police Chief has decided to deploy speed cameras on the streets to collect evidence.
There are N+1 intersections in the city, connected by N roads. Every road has the same length of 1. A street race may take place between any two different intersections by using the roads connecting them. Limited by their budget, the police are able to deploy at most K speed cameras on these N roads. These K speed cameras should be installed such that the length of any possible street race route not covered by speed cameras should be as short as possible.
You are given a map of the city in the form of two arrays, A and B of length N, and an integer K:
- For each J (0 ≤ J < N) there is a road connecting intersections A[J] and B[J].
The Police Chief would like to know the minimum length of the longest path out of surveillance after placing at most K speed cameras.
Write a function:
def solution(A, B, K)
that, given arrays A and B of N integers and integer K, returns the minimum length of the longest path unmonitored by speed cameras after placing at most K speed cameras.
For example, given K = 2 and the following arrays:
A[0] = 5 B[0] = 1 A[1] = 1 B[1] = 0 A[2] = 0 B[2] = 7 A[3] = 2 B[3] = 4 A[4] = 7 B[4] = 2 A[5] = 0 B[5] = 6 A[6] = 6 B[6] = 8 A[7] = 6 B[7] = 3 A[8] = 1 B[8] = 9
the function should return 2. Two speed cameras can be installed on the roads between intersections 1 and 0 and between intersections 0 and 7. (Another solution would be to install speed cameras between intersections 0 and 7 and between intersections 0 and 6.) By installing speed cameras according the first plan, one of the longest paths without a speed camera starts at intersection 8, passes through intersection 6 and ends at intersection 3, which consists of two roads. (Other longest paths are composed of intersections 5, 1, 9 and 7, 2, 4).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..50,000];
- each element of arrays A and B is an integer within the range [0..N];
- K is an integer within the range [0..N];
- the distance between any two intersections is not greater than 900.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 13 minutes
Notes
not defined yet
Code: 07:26:06 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A, B, K):
"""
The solution is as follows:
step 0: represent the graph as a directional tree
step 1: iterate over on the possible diameter of the graph (using binary search)
step1.1: calculate what should be the minimal number of cameras to get this diameter
(see count_cameras for more information)
step1.2: in case a diameter can be achieved using less cameras than we are given, it should be considered
as an alternative
step 2: out of all alternative, pick the longest diameter"""
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
Analysis
expand all
Example tests
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 129, in <module>
main()
File "user.py", line 106, in main
result = sol.solution ( A, B, K )
File "/tmp/solution.py", line 19, in solution
q = deque([0])
NameError: global name 'deque' is not defined
Code: 07:27:01 UTC,
py,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
"""
recursive function:
stoping condition: if 'root' if a leaf
in case it is not a leaf:
step1: calculate the number of needed cameras in order to keep his tree with diameter at most allowed_diameter,
and the depth of each son
step2: for each of sons (ordered by depth): if the path the nodes creates between the sons (d1+d2+2) is greater
than the diameter - break the edge to d1. count the number of breaks
step3: for his last son (or the only one) - in case the path from root to his leaf is greater allowed_diameter,
break the edge from root to son. count this break
step4: set the depth of root as the maximum depth of his (remaining) sons, plus 1.
step5: return the number of broken edges
"""
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
"""
The solution is as follows:
step 0: represent the graph as a directional tree
step 1: iterate over on the possible diameter of the graph (using binary search)
step1.1: calculate what should be the minimal number of cameras to get this diameter
(see count_cameras for more information)
step1.2: in case a diameter can be achieved using less cameras than we are given, it should be considered
as an alternative
step 2: out of all alternative, pick the longest diameter"""
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
Code: 07:28:07 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
Code: 07:31:22 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
Code: 07:32:05 UTC,
py,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([7, 3, 5, 8, 1, 2, 0, 0, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
expand all
Example tests
1.
0.073 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Traceback (most recent call last):
File "user.py", line 129, in <module>
main()
File "user.py", line 89, in main
sol = __import__('solution')
File "/tmp/solution.py", line 64, in <module>
assert solution(*test) == 2
AssertionError
Code: 07:32:39 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
Code: 07:32:48 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis
Code: 07:32:52 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
from collections import deque
def count_cameras(edges, depth_tree, root, allowed_diameter):
if len(edges[root]) == 0:
depth_tree[root] = 0
return 0
sons = edges[root].copy()
counter = sum([count_cameras(edges, depth_tree, son, allowed_diameter) for son in sons])
sons_depths = sorted([(son,depth_tree[son]) for son in sons], key=lambda x:x[1],reverse=True)
for i in xrange(len(sons_depths)-1):
if sons_depths[i][1] + sons_depths[i+1][1] + 2 > allowed_diameter:
sons.remove(sons_depths[i][0])
counter += 1
if sons_depths[-1][1] + 1 > allowed_diameter:
sons.remove(sons_depths[-1][0])
counter += 1
if len(sons)== 0 :
depth_tree[root] = 0
else:
depth_tree[root] = max([depth_tree[son] for son in sons])+1
return counter
def solution(A, B, K):
N = len(A)
edges = [set() for _ in xrange(N+1)]
for i in xrange(N):
edges[A[i]].add(B[i])
edges[B[i]].add(A[i])
q = deque([0])
while len(q) > 0: #after this loop we end up with edges as a rooted tree
node = q.popleft()
for son in edges[node]:
edges[son].remove(node)
q.append(son)
depth_tree = [0] * (N+1)
first = 0
last = min(900, N)
res = []
while first<=last :
midpoint = (first + last)//2
cameras = count_cameras(edges, depth_tree,0, midpoint)
if cameras > K:
first = midpoint+1
else:
res.append(midpoint)
last = midpoint-1
return min(res)
#some simple tests you can use
test = ([5, 1, 0, 2, 7, 0, 6, 6, 1], [1, 0, 7, 4, 2, 6, 8, 3, 9], 2) #2
sroch = ([0,1,2,3,4],[1,2,3,4,5],1) # 2
simple = ([0,0,0,3],[1,2,3,4],2) # 1
simple2 = ([0,0,1,2,2,5],[1,2,3,4,5,6],2) #2
simple3 = ([0,0,1,1,2,2],[1,2,3,4,5,6],2) #2
assert solution(*test) == 2
assert solution(*sroch) == 2
assert solution(*simple) == 1
assert solution(*simple2) == 2
assert solution(*simple3) == 2
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N*log(N)**2)
expand all
Correctness tests
1.
0.074 s
OK
2.
0.074 s
OK
3.
0.075 s
OK
4.
0.074 s
OK
1.
0.074 s
OK
2.
0.073 s
OK
3.
0.074 s
OK
4.
0.074 s
OK
1.
0.074 s
OK
2.
0.074 s
OK
3.
0.074 s
OK
4.
0.074 s
OK
5.
0.074 s
OK
1.
0.074 s
OK
2.
0.074 s
OK
3.
0.075 s
OK
4.
0.075 s
OK
5.
0.075 s
OK
6.
0.074 s
OK
7.
0.074 s
OK
8.
0.074 s
OK
1.
0.075 s
OK
2.
0.075 s
OK
3.
0.077 s
OK
1.
0.079 s
OK
2.
0.081 s
OK
3.
0.081 s
OK
4.
0.083 s
OK
1.
0.305 s
OK
2.
0.309 s
OK
3.
0.312 s
OK
4.
0.226 s
OK
expand all
Correctness/performance tests
1.
2.099 s
OK
2.
2.031 s
OK
1.
0.664 s
OK
2.
0.673 s
OK
1.
1.611 s
OK
2.
1.510 s
OK
3.
1.609 s
OK
1.
1.520 s
OK
2.
1.458 s
OK
1.
1.610 s
OK
2.
1.583 s
OK