Codility NailingPlanks - Using Binary Search on Nail Count Instead of Planks

Question

I have already read through the answers on this question - Codility NailingPlanks. This is not a duplicate, as I'm trying to solve this problem using a different approach - instead of running a binary search on the planks that a given nail can cover, I'm trying to run it on the total number of nails required to cover all the planks.

This is my code:

def solution(A, B, C):
    min_nails = 1
    max_nails = len(C)
    valid = []
    while (min_nails <= max_nails):
        mid_nails = (min_nails + max_nails) // 2
        if (is_valid_nails_amount(mid_nails,A,B,C)):
            max_nails = mid_nails - 1
            valid.append(mid_nails)
        else: 
            min_nails = mid_nails + 1
    return -1 if len(valid) == 0 else min(valid)

def is_valid_nails_amount(nails,A,B,C): 
    candidates=C[0:nails]
    min_cover = min(candidates)
    max_cover = max(candidates)
    isValid = True
    for (a,b) in zip(A,B): 
        if not(min_cover in range(a, b + 1) or max_cover in range(a, b + 1) or a in range(min_cover, max_cover + 1) or b in range(min_cover, max_cover + 1)): 
            isValid = False
            break 
    return isValid

The algorithm begins by checking the first len(C) + 1 / 2 nails in C:

1. First it calculates the smallest and largest value that the nails in this range can cover (min_cover and max_cover).
2. Next, it looks through A & B, and checks whether each plank can be nailed by any of the nails in the range (min_cover, max_cover).
3. If the result is False, we update min_nails to be mid_nails + 1 and repeat. If the result is True, we store the number of nails in the valid array, and attempt to find a smaller amount of nails which would also work, by setting max_nails = mid_nails - 1

This approach scores 100% correctness, however fails on the performance tests because it produces incorrect results - for each of the performance tests, the minimum number of nails obtained is much lower than the expected result. I suspect the error would be in this line: if not(min_cover in range(a, b + 1) or max_cover in range(a, b + 1) or a in range(min_cover, max_cover + 1) or b in range(min_cover, max_cover + 1))

but I can't figure out what it is.

Answer 1

The problem with your if condition can be seen with this sample input:

A = [1,3,5]
B = [2,4,6]
C = [1,5,3]
print(solution(A, B, C))

This will print 2, but the expected output is 3, as all three nails are needed.

Yet, your code will have is_valid_nails_amount(2, A, B, C) return True, despite the fact that the second plank is not nailed by those two nails.

The problem is that neither of these conditions guarantees that a nail hits the plank (a, b):

a in range(min_cover, max_cover + 1)
b in range(min_cover, max_cover + 1)

Your algorithm really needs to check if there is a nail in that min/max range that is available for hitting the plank.