Tasks Details
hard
1.
CakeFactory
Count the number of cakes consisting of K different layers in the order 1, 2, ..., K that will be created after a sequence of operations of putting a layer on some interval.
Task Score
53%
Correctness
100%
Performance
0%
There is a cake factory producing K-flavored cakes. Flavors are numbered from 1 to K. A cake should consist of exactly K layers, each of a different flavor. It is very important that every flavor appears in exactly one cake layer and that the flavor layers are ordered from 1 to K from bottom to top. Otherwise the cake doesn't taste good enough to be sold. For example, for K = 3, cake [1, 2, 3] is well-prepared and can be sold, whereas cakes [1, 3, 2] and [1, 2, 3, 3] are not well-prepared.
The factory has N cake forms arranged in a row, numbered from 1 to N. Initially, all forms are empty. At the beginning of the day a machine for producing cakes executes a sequence of M instructions (numbered from 0 to M−1) one by one. The J-th instruction adds a layer of flavor C[J] to all forms from A[J] to B[J], inclusive.
What is the number of well-prepared cakes after executing the sequence of M instructions?
Write a function:
def solution(N, K, A, B, C)
that, given two integers N and K and three arrays of integers A, B, C describing the sequence, returns the number of well-prepared cakes after executing the sequence of instructions.
Examples:
1. Given N = 5, K = 3, A = [1, 1, 4, 1, 4], B = [5, 2, 5, 5, 4] and C = [1, 2, 2, 3, 3].
There is a sequence of five instructions:
- The 0th instruction puts a layer of flavor 1 in all forms from 1 to 5.
- The 1st instruction puts a layer of flavor 2 in all forms from 1 to 2.
- The 2nd instruction puts a layer of flavor 2 in all forms from 4 to 5.
- The 3rd instruction puts a layer of flavor 3 in all forms from 1 to 5.
- The 4th instruction puts a layer of flavor 3 in the 4th form.
The function should return 3. The cake in form 3 is missing flavor 2, and the cake in form 5 has additional flavor 3. The well-prepared cakes are forms 1, 2 and 5.
2. Given N = 6, K = 4, A = [1, 2, 1, 1], B = [3, 3, 6, 6] and C = [1, 2, 3, 4],
the function should return 2. The 2nd and 3rd cakes are well-prepared.
3. Given N = 3, K = 2, A = [1, 3, 3, 1, 1], B = [2, 3, 3, 1, 2] and C = [1, 2, 1, 2, 2],
the function should return 1. Only the 2nd cake is well-prepared.
4. Given N = 5, K = 2, A = [1, 1, 2], B = [5, 5, 3] and C = [1, 2, 1],
the function should return 3. The 1st, 4th and 5th cakes are well-prepared.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- M is an integer within the range [1..200,000];
- each element of arrays A and B is an integer within the range [1..N];
- each element of array C is an integer within the range [1..K];
- for every integer J, A[J] ≤ B[J];
- arrays A, B and C have the same length, equal to M.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 43 minutes
Notes
not defined yet
Code: 19:33:37 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int N, int K, int[] A, int[] B, int[] C) {
// write your code in Java SE 8
}
}
Code: 20:09:40 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
for i in range(N):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Analysis
expand all
Example tests
1.
0.036 s
OK
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 10, in solution
start = A[i]
IndexError: list index out of range
1.
0.036 s
WRONG ANSWER,
got 0 expected 1
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 10, in solution
start = A[i]
IndexError: list index out of range
Code: 20:11:42 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
for i in range(K):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Code: 20:11:44 UTC,
py,
verify,
result: Failed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
for i in range(K):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Analysis
expand all
Example tests
1.
0.036 s
WRONG ANSWER,
got 0 expected 3
1.
0.036 s
OK
1.
0.036 s
WRONG ANSWER,
got 0 expected 1
1.
0.036 s
WRONG ANSWER,
got 5 expected 3
Code: 20:14:16 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
for i in range(K):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Code: 20:14:30 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
len_arr =
for i in range(K):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Code: 20:14:41 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
len_arr = len(A)
for i in range(K):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Code: 20:14:48 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
len_arr = len(A)
for i in range(len_arr):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Analysis
Code: 20:15:48 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
len_arr = len(A)
for i in range(len_arr):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Analysis
Code: 20:15:51 UTC,
py,
final,
score:
53
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(N, K, A, B, C):
# write your code in Python 3.6
cakes = {}
for i in range(N):
cakes[i+1] = []
len_arr = len(A)
for i in range(len_arr):
start = A[i]
end = B[i]+1
layer = C[i]
for j in range(start,end):
cakes[j].append(layer)
count = 0
for cake in cakes:
check = 0
l = len(cakes[cake])
if l == K:
for i in range(K):
if cakes[cake][i] != i+1:
check = 1
if check == 0:
count += 1
return count
pass
Analysis summary
The following issues have been detected: runtime errors, timeout errors.
Analysis
Detected time complexity:
O(M*N) or O(M*sqrt(N))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.060 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
6.
0.036 s
OK
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
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
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
4.
0.072 s
OK
5.
0.040 s
OK
expand all
Performance tests
1.
17.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 17.000 sec.
2.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
1.
2.720 s
TIMEOUT ERROR,
running time: 2.720 sec., time limit: 0.512 sec.
2.
2.452 s
OK
3.
2.640 s
OK
4.
8.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 8.000 sec.
5.
2.792 s
OK
1.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
2.
22.800 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 16, in solution
cakes[j].append(layer)
MemoryError
3.
21.824 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 16, in solution
cakes[j].append(layer)
MemoryError
4.
24.232 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 16, in solution
cakes[j].append(layer)
MemoryError
5.
21.372 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 16, in solution
cakes[j].append(layer)
MemoryError
6.
23.588 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 157, in <module>
main()
File "exec.py", line 119, in main
result = solution( N, K, A, B, C )
File "/tmp/solution.py", line 16, in solution
cakes[j].append(layer)
MemoryError