Tasks Details
medium
Given a set of points on a plane, find the largest number of points that can be enclosed within a circle centered on the origin, such that the number of red points and green points inside it is equal.
Task Score
61%
Correctness
100%
Performance
9%
There are N points (numbered from 0 to N−1) on a plane. Each point is colored either red ('R') or green ('G'). The K-th point is located at coordinates (X[K], Y[K]) and its color is colors[K]. No point lies on coordinates (0, 0).
We want to draw a circle centered on coordinates (0, 0), such that the number of red points and green points inside the circle is equal. What is the maximum number of points that can lie inside such a circle? Note that it is always possible to draw a circle with no points inside.
Write a function:
def solution(X, Y, colors)
that, given two arrays of integers X, Y and a string colors, returns an integer specifying the maximum number of points inside a circle containing an equal number of red points and green points.
Examples:
1. Given X = [4, 0, 2, −2], Y = [4, 1, 2, −3] and colors = "RGRR", your function should return 2. The circle contains points (0, 1) and (2, 2), but not points (−2, −3) and (4, 4).
2. Given X = [1, 1, −1, −1], Y = [1, −1, 1, −1] and colors = "RGRG", your function should return 4. All points lie inside the circle.
3. Given X = [1, 0, 0], Y = [0, 1, −1] and colors = "GGR", your function should return 0. Any circle that contains more than zero points has an unequal number of green and red points.
4. Given X = [5, −5, 5], Y = [1, −1, −3] and colors = "GRG", your function should return 2.
5. Given X = [3000, −3000, 4100, −4100, −3000], Y = [5000, −5000, 4100, −4100, 5000] and colors = "RRGRG", your function should return 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of arrays X and Y is an integer within the range [−20,000..20,000];
- string colors is made only of the characters 'R' and/or 'G';
- no point lies on the coordinates (0, 0).
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 2 minutes
Notes
not defined yet
Code: 08:50:31 UTC,
java,
autosave
Code: 08:51:05 UTC,
py,
autosave
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
rCount = 0
gCount = 0
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
Code: 08:51:16 UTC,
py,
autosave
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = 0
gCount = 0
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
Code: 08:51:26 UTC,
py,
autosave
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours
gCount = 0
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
Code: 08:51:39 UTC,
py,
autosave
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours.count('R')
gCount = 0
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
Code: 08:51:49 UTC,
py,
autosave
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours.count('R')
gCount = currentColours.count('G')
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
Code: 08:52:00 UTC,
py,
verify,
result: Passed
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours.count('R')
gCount = currentColours.count('G')
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
return (x**2+y**2)**(1/2)
Code: 08:52:09 UTC,
py,
verify,
result: Passed
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours.count('R')
gCount = currentColours.count('G')
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
return (x**2+y**2)**(1/2)
Code: 08:52:12 UTC,
py,
final,
score:
61
def solution(X, Y, colors):
distances = [distance(X[i],Y[i]) for i in range(len(X))]
colors = list(colors)
colors = ''.join([colors for _, colors in sorted(zip(distances,colors))])[::-1]
distances.sort(reverse=True)
for i in range(len(distances)):
if i>0 and distances[i] == distances[i-1]:
continue
currentColours = colors[i:]
rCount = currentColours.count('R')
gCount = currentColours.count('G')
if rCount == gCount:
return rCount+gCount
return 0
def distance(x,y):
return (x**2+y**2)**(1/2)Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
small_different_distances
Small tests where all points have distinct distances from the origin. N <= 50.
Small tests where all points have distinct distances from the origin. N <= 50.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
small_imbalanced
Small tests where the proportion of color occurences is imbalanced. N <= 50.
Small tests where the proportion of color occurences is imbalanced. N <= 50.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
small_sorted
Small tests where points are given in increasing order of distance from (0, 0). N <= 50.
Small tests where points are given in increasing order of distance from (0, 0). N <= 50.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
expand all
Correctness/performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
expand all
Performance tests
1.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
2.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
3.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
big_different_distances
Big tests where all points have distinct distances from the origin.
Big tests where all points have distinct distances from the origin.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 9.000 sec.
Killed. Hard limit reached: 9.000 sec.
1.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
2.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
3.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
big_imbalanced
Big tests where the proportion of color occurences is imbalanced.
Big tests where the proportion of color occurences is imbalanced.
✘
TIMEOUT ERROR
running time: 7.484 sec., time limit: 3.160 sec.
running time: 7.484 sec., time limit: 3.160 sec.
1.
7.484 s
TIMEOUT ERROR,
running time: 7.484 sec., time limit: 3.160 sec.
2.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
3.
7.564 s
TIMEOUT ERROR,
running time: 7.564 sec., time limit: 3.280 sec.
4.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
big_compact
Big tests where points are very close to the origin.
Big tests where points are very close to the origin.
✘
TIMEOUT ERROR
running time: 3.944 sec., time limit: 2.920 sec.
running time: 3.944 sec., time limit: 2.920 sec.
1.
3.944 s
TIMEOUT ERROR,
running time: 3.944 sec., time limit: 2.920 sec.
2.
3.692 s
TIMEOUT ERROR,
running time: 3.692 sec., time limit: 2.960 sec.
3.
0.520 s
OK
big_sorted
Big tests where points are given in increasing order of distance from (0, 0).
Big tests where points are given in increasing order of distance from (0, 0).
✘
TIMEOUT ERROR
Killed. Hard limit reached: 8.000 sec.
Killed. Hard limit reached: 8.000 sec.
1.
8.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 8.000 sec.
2.
3.756 s
TIMEOUT ERROR,
running time: 3.756 sec., time limit: 3.080 sec.
3.
8.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 8.000 sec.
4.
7.688 s
TIMEOUT ERROR,
running time: 7.688 sec., time limit: 2.960 sec.