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
87%
Correctness
100%
Performance
75%
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:
def solution(a, b, c)
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 Ruby
Total time used 44 minutes
Effective time used 44 minutes
Notes
not defined yet
Task timeline
Code: 02:24:05 UTC,
rb,
verify,
result: Failed
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
Code: 02:45:03 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
do
j = c[j]
total_weight[j] += b[i]
return i-1 if total_weight[j] > a[j]
while c[j] > 0
end
end
User test case 1:
[[5, 3, 6, 3, 3], [2, 3, 1, 1, 2], [-1, 0, -1, 0, 3]]
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
user.rb:20: syntax error, unexpected keyword_do_block, expecting keyword_end
do
^
user.rb:158: syntax error, unexpected $end, expecting keyword_end
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
user.rb:20: syntax error, unexpected keyword_do_block, expecting keyword_end
do
^
user.rb:158: syntax error, unexpected $end, expecting keyword_end
expand all
User tests
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
user.rb:20: syntax error, unexpected keyword_do_block, expecting keyword_end
do
^
user.rb:158: syntax error, unexpected $end, expecting keyword_end
Code: 02:46:25 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
while c[j] > 0
j = c[j]
total_weight[j] += b[i]
return i-1 if total_weight[j] > a[j]
end
end
end
User test case 1:
[[5, 3, 6, 3, 3], [2, 3, 1, 1, 2], [-1, 0, -1, 0, 3]]
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
expand all
User tests
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
Code: 02:46:59 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
while c[j] > 0
j = c[j]
total_weight[j] += b[i]
return i-1 if total_weight[j] > a[j]
end
end
end
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.072 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
Code: 02:47:25 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
while c[j] > 0
j = c[j]
total_weight[j] += b[i]
return i-1 if total_weight[j] > a[j]
end
end
end
User test case 1:
([], [], []),0
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.068 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
expand all
User tests
1.
0.001 s
RUNTIME ERROR,
invalid input, unexpected token at the end of input: 0
Code: 02:47:42 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
while c[j] > 0
j = c[j]
total_weight[j] += b[i]
return i-1 if total_weight[j] > a[j]
end
end
end
User test case 1:
[[], [], []]
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.064 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Invalid result type, Integer expected, Array found
Code: 02:55:33 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
a.each_with_index do |rope, i|
return (i-1) if b[i] > a[i]
total_weight[i] = b[i]
j = i
while c[j] > 0
j = c[j]
total_weight[j] += b[i]
return (i-1) if total_weight[j] > a[j]
end
end
return a.length
end
User test case 1:
([], [], [])22,35,35,3,15,3,1,16,3,1,1
Analysis
expand all
Example tests
1.
0.068 s
WRONG ANSWER,
got 5 expected 3
1.
0.068 s
WRONG ANSWER,
got 3 expected 2
expand all
User tests
1.
0.001 s
RUNTIME ERROR,
invalid input, unexpected token at the end of input: 22
Code: 02:58:46 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return (i-1) if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] > 0
j = c[j]
total_weight[j] += current_weight
return (i-1) if total_weight[j] > a[j]
end
end
return a.length
end
Analysis
expand all
Example tests
1.
0.056 s
WRONG ANSWER,
got 5 expected 3
1.
0.064 s
WRONG ANSWER,
got 3 expected 2
Code: 02:59:27 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return (i-1) if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] > 0
j = c[j]
total_weight[j] += current_weight
return (i-1) if total_weight[j] > a[j]
end
end
return a.length -1
end
Analysis
expand all
Example tests
example1
first example from the problem statement
first example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.060 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
user.rb:27:in `length': wrong number of arguments(1 for 0) (ArgumentError) from user.rb:27:in `solution' from user.rb:158:in `<main>'
example2
second example from the problem statement
second example from the problem statement
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
user.rb:27:in `length': wrong number of arguments(1 for 0) (ArgumentError) from user.rb:27:in `solution' from user.rb:158:in `<main>'
Code: 02:59:43 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return (i-1) if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] > 0
j = c[j]
total_weight[j] += current_weight
return (i-1) if total_weight[j] > a[j]
end
end
return a.count
end
Analysis
expand all
Example tests
1.
0.064 s
WRONG ANSWER,
got 5 expected 3
1.
0.068 s
WRONG ANSWER,
got 3 expected 2
Code: 03:00:24 UTC,
rb,
verify,
result: Failed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return i if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] > 0
j = c[j]
total_weight[j] += current_weight
return i if total_weight[j] > a[j]
end
end
return a.count
end
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 5 expected 3
1.
0.060 s
WRONG ANSWER,
got 3 expected 2
Code: 03:04:28 UTC,
rb,
verify,
result: Passed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return i if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] != -1
j = c[j]
total_weight[j] += current_weight
return i if total_weight[j] > a[j]
end
end
return a.count
end
Analysis
Code: 03:04:35 UTC,
rb,
verify,
result: Passed
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return i if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] != -1
j = c[j]
total_weight[j] += current_weight
return i if total_weight[j] > a[j]
end
end
return a.count
end
Analysis
Code: 03:04:40 UTC,
rb,
final,
score:
87
# you can use puts for debugging purposes, e.g.
# puts "this is a debug message"
#{
# 1 => (:total_weight, :parent, :max)
# }
# a durability
# b weight
# c position attached, if -1 it is hook
def solution(a, b, c)
return 0 if a.length == 0
total_weight = Array.new
b.each_with_index do |current_weight, i|
return i if current_weight > a[i]
total_weight[i] = current_weight
j = i
while c[j] != -1
j = c[j]
total_weight[j] += current_weight
return i if total_weight[j] > a[j]
end
end
return a.count
end
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Performance tests
1.
0.076 s
OK
1.
0.096 s
OK
1.
0.468 s
OK
line
large random trees, N ~= 100,000
large random trees, N ~= 100,000
✘
TIMEOUT ERROR
running time: >13.00 sec., time limit: 7.34 sec.
running time: >13.00 sec., time limit: 7.34 sec.
1.
13.000 s
TIMEOUT ERROR,
running time: >13.00 sec., time limit: 7.34 sec.
stderr:
Error during output processing. Make sure your program returns a value of correct type.