-------------------------------------------------------------------------------------------------------------------
Ropes and Weights
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 zero-indexed 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 zero-indexed 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
See image below. When the rope breaks(weight, think cumulative weight, attached to it becomes more than its durability) it is shown as dotted line.
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
See image blow.
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).
Assume that:
• 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).
Complexity:
• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
-------------------------------------------------------------------------------------------------------------------
I chose Python as my programming language as it becomes really easy to manipulate the arrays as lists, and many complex tasks of array indexing, and other operations are easily done by various Python idioms and modules.
Here is my Solution which won me a Silver Badge award in the programming challenge(Yeah! Weekend well spent I say)
def solution(A, B, C):
lenC = len(C)
if lenC==0:
return 0
cumwt = [0]*lenC
i=0
lut = [0]*lenC
for v in C:
if v == -1:
cumwt[i] = B[i]
if cumwt[i] > A[i]:
return i
else:
i = i + 1
else:
cumwt[i] = cumwt[i] + B[i]
if cumwt[i] > A[i]:
return i
while v != -1:
idx = v
v =C[idx]
cumwt[idx] = cumwt[idx] + B[i]
if cumwt[idx] > A[idx]:
return i
i = i + 1
return i
#D= [5,3,6,3,3]
#D=[4,3,1]
D=[]
#W=[2,3,1,1,2]
#W=[2,2,1]
W=[]
#P=[-1,0,-1,0,3]
#P=[-1,0,1]
P=[]
print solution(D,W,P)
Below is the complete test report of my solution which was evaluated against various functionality and performance tests.My solution failed 1 large data-set performance test because solution wasn't optimized for speed and outran the stipulated time for that test case.
Analysis
Detected time complexity:
O(N*log(N))
test time result Example tests example1
first example from the problem statement 0.064 s OK example2
second example from the problem statement 0.060 s OK Correctness tests extreme_empty_one
no ropes and only one rope 0.064 s OK tiny
only two ropes 0.060 s OK small
only three ropes 0.068 s OK small_random
small random trees, 10 <= N <= 30 0.064 s OK Performance tests star
tree forms a star, N ~= 5,000 0.084 s OK medium_random
medium random trees, N ~= 10,000 0.104 s OK large_random
large random trees, N ~= 100,000 0.660 s OK line
large random trees, N ~= 100,000 >11.000 s TIMEOUT ERROR
running time: >11.00 sec., time limit: 5.33 sec.
