Tasks Details
medium
Calculate the number of slices in which (maximum - minimum <= K).
Task Score
60%
Correctness
Not assessed
Performance
Not assessed
An integer K and a non-empty array A consisting of N integers are given.
A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.
A bounded slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K.
The goal is to calculate the number of bounded slices.
For example, consider K = 2 and array A such that:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3There are exactly nine bounded slices: (0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).
Write a function:
def solution(K, A)
that, given an integer K and a non-empty array A of N integers, returns the number of bounded slices of array A.
If the number of bounded slices is greater than 1,000,000,000, the function should return 1,000,000,000.
For example, given:
A[0] = 3 A[1] = 5 A[2] = 7 A[3] = 6 A[4] = 3the function should return 9, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- K is an integer within the range [0..1,000,000,000];
- each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Total time used 94 minutes
Effective time used 71 minutes
Notes
not defined yet
Task timeline
Code: 16:22:29 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 17 expected 9
Code: 16:23:35 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 17 expected 9
Code: 16:26:04 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 17 expected 9
Code: 16:29:29 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if _diff >=0 and _diff <= K:
_ret_numer += 1
elif _diff < 0 and -_diff <=K:
_ret_numer += 1
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 6 expected 9
Code: 16:30:08 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if _diff >=0 and _diff <= K:
_ret_numer += 1
elif _diff < 0 and -_diff <=K:
_ret_numer += 1
print _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
6 Invalid result type, int expected, <type 'NoneType'> found.
Code: 16:30:27 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if _diff >=0 and _diff <= K:
_ret_numer += 1
elif _diff < 0 and -_diff <=K:
_ret_numer += 1
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 6 expected 9
stdout:
6
Code: 16:31:40 UTC,
py,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 6 expected 9
stdout:
6
Code: 16:33:54 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
import math
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if math.fabs(_diff) <= K:
_ret_numer += 1
print (_inx,_inx2)
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 6 expected 9
stdout:
(0, 1) (0, 4) (1, 2) (1, 3) (1, 4) (2, 3) 6
Code: 16:34:28 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
import math
_ret_numer = 0
print K,AA
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if math.fabs(_diff) <= K:
_ret_numer += 1
print (_inx,_inx2)
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
2
Traceback (most recent call last):
File "user.py", line 92, in <module>
result = solution ( K, A )
File "user.py", line 5, in solution
print K,AA
NameError: global name 'AA' is not defined
Code: 16:34:36 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
import math
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx+1,_count):
_diff = A[_inx] - A[_inx2]
if math.fabs(_diff) <= K:
_ret_numer += 1
print (_inx,_inx2)
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 6 expected 9
stdout:
2 [3, 5, 7, 6, 3] (0, 1) (0, 4) (1, 2) (1, 3) (1, 4) (2, 3) 6
Code: 16:35:07 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
import math
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
for _inx2 in range(_inx,_count):
_diff = A[_inx] - A[_inx2]
if math.fabs(_diff) <= K:
_ret_numer += 1
print (_inx,_inx2)
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 11 expected 9
stdout:
2 [3, 5, 7, 6, 3] (0, 0) (0, 1) (0, 4) (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (3, 3) (4, 4) 11
Code: 17:01:38 UTC,
py,
verify,
result: Failed
def solution(K, A):
# write your code in Python 2.6
import math
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None：
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None：
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
print (_inx,_inx2)
else:
break
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.030 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
File "user.py", line 11 SyntaxError: Non-ASCII character '\xef' in file user.py on line 11, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details
Code: 17:02:09 UTC,
py,
verify,
result: Passed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
print (_inx,_inx2)
else:
break
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
OK
stdout:
WARNING: producing output may seriously slow down your code! 2 [3, 5, 7, 6, 3] (0, 0) (0, 1) (1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3) (4, 4) 9
Code: 17:03:11 UTC,
py,
verify,
result: Passed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
print (_inx,_inx2)
else:
break
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
OK
stdout:
WARNING: producing output may seriously slow down your code! 2 [3, 5, 7, 6, 3] (0, 0) (0, 1) (1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3) (4, 4) 9
expand all
User tests
1.
0.050 s
OK
function result: 7
function result: 7
stdout:
2 [3, -5, 7, 6, 3, -8] (0, 0) (1, 1) (2, 2) (2, 3) (3, 3) (4, 4) (5, 5) 7
Code: 17:03:53 UTC,
py,
verify,
result: Passed
def solution(K, A):
# write your code in Python 2.6
_ret_numer = 0
print K,A
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
print (_inx,_inx2)
else:
break
print _ret_numer
return _ret_numer
pass
Analysis
expand all
Example tests
1.
0.050 s
OK
stdout:
WARNING: producing output may seriously slow down your code! 2 [3, 5, 7, 6, 3] (0, 0) (0, 1) (1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3) (4, 4) 9
expand all
User tests
1.
0.050 s
OK
function result: 7
function result: 7
stdout:
2 [3, -5, 7, 6, 3, -8] (0, 0) (1, 1) (2, 2) (2, 3) (3, 3) (4, 4) (5, 5) 7
1.
0.050 s
OK
function result: 7
function result: 7
stdout:
2 [3, -5, 7, 6, 3, -8] (0, 0) (1, 1) (2, 2) (2, 3) (3, 3) (4, 4) (5, 5) 7
Code: 17:06:14 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:10:11 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
def solution2(K, A):
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:16:32 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
_max_index = None
_min_index = None
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:34:50 UTC,
py,
verify,
result: Failed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
break
return _ret_numer
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 5 expected 9
Code: 17:35:17 UTC,
py,
verify,
result: Failed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
break
return _ret_numer
Analysis
expand all
Example tests
1.
0.050 s
WRONG ANSWER,
got 5 expected 9
Code: 17:36:16 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in range(_count):
_max_int = None
_min_int = None
for _inx2 in range(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:36:39 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:36:59 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:37:15 UTC,
py,
verify,
result: Passed
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis
Code: 17:37:21 UTC,
py,
final,
score:
60
def solution(K, A):
_ret_numer = 0
_count = len(A)
for _inx in xrange(_count):
_max_int = None
_min_int = None
for _inx2 in xrange(_inx,_count):
if _max_int is None:
_max_int = A[_inx2]
else:
if _max_int < A[_inx2]:
_max_int = A[_inx2]
if _min_int is None:
_min_int = A[_inx2]
else:
if _min_int > A[_inx2]:
_min_int = A[_inx2]
if _max_int - _min_int <= K:
_ret_numer += 1
else:
break
return _ret_numer
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N ** 2)
expand all
Assessment tests
1.
0.050 s
OK
1.
0.050 s
OK
1.
0.050 s
OK
1.
0.050 s
OK
1.
0.050 s
OK
medium_random
chaotic medium sequences length = ~3,000
chaotic medium sequences length = ~3,000
✘
TIMEOUT ERROR
running time: >1.01 sec., time limit: 0.24 sec.
running time: >1.01 sec., time limit: 0.24 sec.
1.
1.010 s
TIMEOUT ERROR,
running time: >1.01 sec., time limit: 0.24 sec.
large_range
large range test, length = ~100,000
large range test, length = ~100,000
✘
TIMEOUT ERROR
running time: >3.02 sec., time limit: 2.12 sec.
running time: >3.02 sec., time limit: 2.12 sec.
1.
3.020 s
TIMEOUT ERROR,
running time: >3.02 sec., time limit: 2.12 sec.
1.
0.550 s
OK
large_answer
test with large answer
test with large answer
✘
TIMEOUT ERROR
running time: >1.01 sec., time limit: 0.80 sec.
running time: >1.01 sec., time limit: 0.80 sec.
1.
1.010 s
TIMEOUT ERROR,
running time: >1.01 sec., time limit: 0.80 sec.
large_extreme
all maximal value = ~100,000
all maximal value = ~100,000
✘
TIMEOUT ERROR
running time: >2.02 sec., time limit: 1.40 sec.
running time: >2.02 sec., time limit: 1.40 sec.
1.
2.020 s
TIMEOUT ERROR,
running time: >2.02 sec., time limit: 1.40 sec.