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
61%
Correctness
100%
Performance
16%
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:
class Solution { public int solution(int N, int K, int[] A, int[] B, int[] 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 Java 21
Time spent on task 21 minutes
Notes
not defined yet
Code: 19:22:31 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: 19:34:40 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: 19:34:54 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
int[] cakes = new int[]
}
}
Code: 19:35:12 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
int[] cakes = new int[C.length];
for(int)
}
}
Code: 19:35:42 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=B[i];)
}
}
}
Code: 19:36:01 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
}
}
}
}
Code: 19:36:31 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] )
}
}
}
}
Code: 19:36:41 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == )
}
}
}
}
Code: 19:37:02 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]
}
}
}
}
}
Code: 19:37:21 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} elses {
cakes[j]=
}
}
}
}
}
Code: 19:37:36 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
}
}
Code: 19:37:55 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
}
}
Code: 19:38:25 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<)
}
}
Code: 19:38:43 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
}
}
}
Code: 19:39:12 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==k)
}
}
}
Code: 19:39:27 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
int[] cakes = new int[C.length];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==k) ans++;
}
return ans;
}
}
Code: 19:39:56 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==k) ans++;
}
return ans;
}
}
Code: 19:40:50 UTC,
java,
verify,
result: Failed
// 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==k) ans++;
}
return ans;
}
}
Analysis
Compile error
Solution.java:14: error: cannot find symbol
cakes[j]=c[i];
^
symbol: variable c
location: class Solution
Solution.java:23: error: cannot find symbol
if(cakes[i]==k) ans++;
^
symbol: variable k
location: class Solution
2 errors
Code: 19:40:57 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=c[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==) ans++;
}
return ans;
}
}
Code: 19:41:08 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=C[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Code: 19:41:10 UTC,
java,
verify,
result: Failed
// 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j] == C[i]-1){
cakes[j]=C[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Analysis
expand all
Example tests
1.
0.008 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 at Solution.solution(Solution.java:13) at Exec.run(exec.java:52) at Exec.main(exec.java:38)
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6 at Solution.solution(Solution.java:13) at Exec.run(exec.java:52) at Exec.main(exec.java:38)
1.
0.004 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3 at Solution.solution(Solution.java:13) at Exec.run(exec.java:52) at Exec.main(exec.java:38)
1.
0.008 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5 at Solution.solution(Solution.java:13) at Exec.run(exec.java:52) at Exec.main(exec.java:38)
Code: 19:41:58 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j-] == C[i]-1){
cakes[j]=C[i];
} else {
cakes[j]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Code: 19:42:09 UTC,
java,
verify,
result: Passed
// 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j-1] == C[i]-1){
cakes[j-1]=C[i];
} else {
cakes[j-1]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Analysis
Code: 19:42:30 UTC,
java,
verify,
result: Passed
// 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j-1] == C[i]-1){
cakes[j-1]=C[i];
} else {
cakes[j-1]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Analysis
Code: 19:42:36 UTC,
java,
final,
score:
61
// 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
int[] cakes = new int[N];
for(int i =0;i<C.length;i++){
for(int j=A[i];j<=B[i];j++){
if(cakes[j-1] == C[i]-1){
cakes[j-1]=C[i];
} else {
cakes[j-1]=-1;
}
}
}
int ans=0;
for(int i=0;i<cakes.length;i++){
if(cakes[i]==K) ans++;
}
return ans;
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(M*N) or O(M*sqrt(N))
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.004 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
4.
0.024 s
OK
5.
0.012 s
OK
expand all
Performance tests
1.
4.572 s
OK
2.
3.960 s
OK
1.
0.484 s
TIMEOUT ERROR,
running time: 0.484 sec., time limit: 0.176 sec.
2.
0.692 s
OK
3.
0.660 s
OK
4.
4.440 s
TIMEOUT ERROR,
running time: 4.440 sec., time limit: 1.136 sec.
5.
0.648 s
OK
1.
9.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 9.000 sec.
2.
17.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 17.000 sec.
3.
19.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 19.000 sec.
4.
18.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 18.000 sec.
5.
17.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 17.000 sec.
6.
17.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 17.000 sec.