Tasks Details
hard
1.
BreakTheRope
Find the maximum number of ropes that can be attached in order, without breaking any of the ropes.
Task Score
100%
Correctness
100%
Performance
100%
In a room there are N ropes and N weights. Each rope is connected to exactly one weight (at just one end), and each rope has a particular durability − the maximum weight that it can suspend.
There is also a hook, attached to the ceiling. The ropes can be attached to the hook by tying the end without the weight. The ropes can also be attached to other weights; that is, the ropes and weights can be attached to one another in a chain. A rope will break if the sum of weights connected to it, directly or indirectly, is greater than its durability.
We know the order in which we want to attach N ropes. More precisely, we know the parameters of the rope (durability and weight) and the position of each attachment. Durabilities, weights and positions are given in three arrays A, B, C of lengths N. For each I (0 ≤ I < N):
- A[I] is the durability of the I-th rope,
- B[I] is the weight connected to the I-th rope,
- C[I] (such that C[I] < I) is the position to which we attach the I-th rope; if C[I] equals −1 we attach to the hook, otherwise we attach to the weight connected to the C[I]-th rope.
The goal is to find the maximum number of ropes that can be attached in the specified order without breaking any of the ropes.
Write a function:
int solution(int A[], int B[], int C[], int N);
that, given three arrays A, B, C of N integers, returns the maximum number of ropes that can be attached in a given order.
For example, given the following arrays:
A[0] = 5 B[0] = 2 C[0] = -1 A[1] = 3 B[1] = 3 C[1] = 0 A[2] = 6 B[2] = 1 C[2] = -1 A[3] = 3 B[3] = 1 C[3] = 0 A[4] = 3 B[4] = 2 C[4] = 3
the function should return 3, as if we attach a fourth rope then one rope will break, because the sum of weights is greater than its durability (2 + 3 + 1 = 6 and 6 > 5).
Given the following arrays:
A[0] = 4 B[0] = 2 C[0] = -1 A[1] = 3 B[1] = 2 C[1] = 0 A[2] = 1 B[2] = 1 C[2] = 1
the function should return 2, as if we attach a third rope then one rope will break, because the sum of weights is greater than its durability (2 + 2 + 1 = 5 and 5 > 4).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [1..1,000,000];
- each element of array B is an integer within the range [1..5,000];
- each element of array C is an integer such that −1 ≤ C[I] < I, for each I (0 ≤ I < N).
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C
Total time used 5 minutes
Effective time used 5 minutes
Notes
not defined yet
Task timeline
Code: 06:43:50 UTC,
c,
verify,
result: Failed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i] - weight;
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
Analysis
expand all
Example tests
1.
0.004 s
WRONG ANSWER,
got 1 expected 3
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
WRONG ANSWER,
got 1 expected 2
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
Code: 06:45:05 UTC,
c,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
Analysis
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
Code: 06:45:24 UTC,
c,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
User test case 1:
[[1], [1], [-1]]
Analysis
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
expand all
User tests
1.
0.004 s
OK
function result: 1
function result: 1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
Code: 06:46:06 UTC,
c,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
User test case 1:
[[2], [3], [-1]]
User test case 2:
[[2, 2], [1, 1], [-1, -1]]
Analysis
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
expand all
User tests
1.
0.004 s
OK
function result: 0
function result: 0
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
OK
function result: 2
function result: 2
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
Code: 06:46:37 UTC,
c,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
User test case 1:
[[2], [3], [-1]]
User test case 2:
[[2, 2], [1, 1], [-1, -1]]
User test case 3:
[[4], [3], [-1]]
Analysis
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
expand all
User tests
1.
0.004 s
OK
function result: 0
function result: 0
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
OK
function result: 2
function result: 2
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
function result: 1
function result: 1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
Code: 06:47:15 UTC,
c,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}
User test case 1:
[[2], [3], [-1]]
User test case 2:
[[2, 2], [1, 1], [-1, -1]]
User test case 3:
[[4], [3], [-1]]
Analysis
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
expand all
User tests
1.
0.004 s
OK
function result: 0
function result: 0
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
OK
function result: 2
function result: 2
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
function result: 1
function result: 1
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
Code: 06:47:21 UTC,
c,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768
int solutionLine(int durs[], int weights[], int parents[], int N) {
int i=0;
int minDur = 100000; // stated max durability
for (i=0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
if (parent != i-1) {
// not a single-line case, fall back to tree solution
return -2;
}
minDur = dur<minDur?dur:minDur;
minDur -= weight;
if (minDur < 0) {
return i;
}
}
return N;
}
int solutionTree(int durs[], int weights[], int parents[], int N) {
int i = 0;
for ( i = 0; i<N; i++) {
int parent = parents[i];
int weight = weights[i];
int dur = durs[i];
int remDur = dur - weight;
// can dur[i] < weight[i]?
if (remDur < 0) {
return i;
}
durs[i] = remDur;
while (parent != -1) {
durs[parent] -= weight;
if (durs[parent] < 0) {
return i;
}
//printf("%d: n=[%d] w=[%d] dur=[%d]\n", i, parent, weight, durs[parent]);
parent = parents[parent];
}
}
return N;
}
int solution(int durs[], int weights[], int parents[], int N) {
printf("line\n");
int res = solutionLine(durs, weights, parents, N);
if ( res != -2 ) return res;
printf("tree\n");
return solutionTree(durs, weights, parents, N);
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Example tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
expand all
Correctness tests
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line
1.
0.004 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
expand all
Performance tests
1.
0.008 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.016 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.108 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line tree
1.
0.104 s
OK
stderr:
WARNING: producing output may seriously slow down your code!stdout:
line