Codility NailingPlanks

Question

Tried to understand the solution for Codility NailingPlanks.

Link for the Problem: https://app.codility.com/programmers/lessons/14-binary_search_algorithm/nailing_planks/

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

Link for the solution: https://github.com/ZRonchy/Codility/blob/master/Lesson12/NailingPlanks.java

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int[] B, int[] C) {
        // the main algorithm is that getting the minimal index of nails which
        // is needed to nail every plank by using the binary search
        int N = A.length;
        int M = C.length;
        // two dimension array to save the original index of array C
        int[][] sortedNail = new int[M][2];
        for (int i = 0; i < M; i++) {
            sortedNail[i][0] = C[i];
            sortedNail[i][1] = i;
        }
        // use the lambda expression to sort two dimension array
        Arrays.sort(sortedNail, (int x[], int y[]) -> x[0] - y[0]);
        int result = 0;
        for (int i = 0; i < N; i++) {//find the earlist position that can nail each plank, and the max value for all planks is the result
            result = getMinIndex(A[i], B[i], sortedNail, result);
            if (result == -1)
                return -1;
        }
        return result + 1;
    }
    // for each plank , we can use binary search to get the minimal index of the
    // sorted array of nails, and we should check the candidate nails to get the
    // minimal index of the original array of nails.
    public int getMinIndex(int startPlank, int endPlank, int[][] nail, int preIndex) {
        int min = 0;
        int max = nail.length - 1;
        int minIndex = -1;
        while (min <= max) {
            int mid = (min + max) / 2;
            if (nail[mid][0] < startPlank)
                min = mid + 1;
            else if (nail[mid][0] > endPlank)
                max = mid - 1;
            else {
                max = mid - 1;
                minIndex = mid;
            }
        }
        if (minIndex == -1)
            return -1;
        int minIndexOrigin = nail[minIndex][1];
        //find the smallest original position of nail that can nail the plank
        for (int i = minIndex; i < nail.length; i++) {
            if (nail[i][0] > endPlank)
                break;
            minIndexOrigin = Math.min(minIndexOrigin, nail[i][1]);
            // we need the maximal index of nails to nail every plank, so the
            // smaller index can be omitted    ****
            if (minIndexOrigin <= preIndex) // ****
                return preIndex;            // ****
        } 
        return minIndexOrigin;
    }
}

I don't understand Line 99-102, marked with ****, of the solution.

My question is:

If minIndexOrigin <= preIndex , then it will use preIndex, but how if the preIndex doesn't nail the current plank ?

Is there a bit mistake with the solution ?

Town

Answer 1

The case that is handled in those lines is when you find that there is an index that nails the current plank, which index is less (or equal) to the lowest index we need to be able to nail another (previously analysed) plank. In that case, we don't need to look further for the current plank, since we know that:

• we can nail the plank
• we can use an index that is not greater than an index we really need to use for another plank.

Since we are only interested in the greatest index among the least indexes we need for the different planks (i.e. the index for the "worst" plank), we know that the index we just found now is not important any more: if we already know that we will be using all the nails up to at least preIndex, we know that one nail among that set will nail the current plank. We can just exit the loop and return a "dummy" index that will not influence the result.

Note what the effect is in the calling loop:

result = getMinIndex(A[i], B[i], sortedNail, result); 

After this assignment, result will be equal to what result was before the call: this plank (A[i], B[i]) can be nailed with an earlier nail, but we don't really care which nail that is, as we need to know the worst case, which is up to now reflected by result, and all nails up to that index are already in the set of nails that will be hammered.

You can compare it with alpha-beta pruning.

Streamer

hmm, which part of the code, can ensure, that the earlier nail, can nail the current plank ? – Town

It is not particularly that nail, but since the challenge description clearly says that the nails will be hammered from index 0 up to the index you return, you can know that one nail in that range will nail the current plank. It is just that you don't memorise precisely which nail it will be, as you already know you need to go further for a previous plank, so the nail that nails the current plank will be among the hammered nails. – Streamer

oh, i see, so the nails will be hammered from index 0, up to the index we return, okay, understand now, thank you – Town

Answer 2

Codility Training - 14.2 - Nailing Planks

The planks are zipped into (begin, end) pairs and sorted which supports a binary search. For each nail, that nail is used to remove as many planks as possible before failing the search. When the array of planks is empty, the index of the current nail can be returned representing the count of nailed used.

O((N + M) * log(M))

All code is here:

def find_plank(nail, planks):
    """
    planks is an array of pairs (begin, end) for each plank.
    planks is sorted by start position of planks
    """
    if not planks:
        return -1 # empty planks
    BEGIN_IDX = 0
    END_IDX = 1
    lower = 0
    upper = len(planks)-1
    while lower <= upper:
        mid = (lower + upper) // 2
        if planks[mid][BEGIN_IDX] > nail:
            upper = mid - 1
        elif planks[mid][END_IDX] < nail:
            lower = mid + 1
        else: # nail hits plank[mid]
            return mid # return this plank id so we can pop the plank
    return -1


def solution(A, B, C):
    """
    Strategy is to sort the planks first. Then scan the nails and do the following.
    For each nail perform a binary search for a plank.
        if plank found then pop plank then search again until the nail hits no more planks.
    The plank list should diminish until it hits zero meaning we have found the minimum number of nails needed
    If any planks remain then return -1

    100% https://app.codility.com/demo/results/trainingR7UKQB-9AQ/
    """

    if max(B) < min(C) or max(C) < min(A):
        return -1 # no nail can hit that plank

    planks = sorted(zip(A,B))

    for i in range(len(C)):
        nail = C[i]
        p_idx = find_plank(nail, planks)
        # print(f'idx{i} nail at pos {nail}, matched {p_idx}, in {planks}')
        while p_idx > -1:
            del planks[p_idx]
            p_idx = find_plank(nail, planks)
            # print(f'idx{i} nail at pos {nail}, matched {p_idx}, in {planks}')
        if not planks:
            # print('NO PLANKS', i+1)
            return i+1 # the index of the nail that removed the last plank.

    return -1 # else we couldn't remove all planks

Rath

del planks[p_idx] takes O(N) time, so this is O(N * M) – Delphine

Answer 3

I would like to provide my algorithm and implementation for the desired O(log(M) * (M + N)) runtime complexity.

1. Binary search over the C elements.
2. For each iteration, create a prefix sums of nails up the current binary search iterations. This will require two steps:
   a. Count the occurences of nail positions in C.
   b. Create the proper prefix sums about the available nails at a particular index.
3. If there is no nail in a plank range, then a nail cannot be found there, so there cannot be a solution for the task.
4. If there is no solution in that consecutive array, we need to look for a longer range.
5. If there is a solution in that consecutive sequence, we need to look for a smaller range.
6. The binary search goes on until we eventually find the smallest range.

The runtime complexity of the binary search is log(M) since we are bisecting a range of M. The runtime complexity of the inner iteration comes from three loops:

a. O(mid), where mid < M. So, this is O(M) in worst case.
b. O(2M), which is O(M) as we can leave the constant.
c. O(N), going through the number of elements in A and B.

Therefore, the runtime complexity of the inner loop is O(M + N).

The overall runtime complexity of the algorithm is therefore O(log(M) * (M + N)).

The overall space complexity is O(2 * M) for the prefix sums, so essentially O(M).

bool check(vector<int> &A, vector<int> &B, vector<int> &C, int mid)             
{                                                                               
  const int M = C.size();                                                       
  vector<int> prefix_sums(2 * M + 1, 0);                                        
  for (int i = 0; i < mid; ++i) ++prefix_sums[C[i]];                            
  for (size_t i = 1; i < prefix_sums.size(); ++i) prefix_sums[i] += prefix_sums[i - 1];
  for (size_t i = 0; i < A.size(); ++i) if (prefix_sums[B[i]] == prefix_sums[A[i] - 1]) return false;
  return true;                                                                  
}

int solution(vector<int> &A, vector<int> &B, vector<int> &C)                    
{                                                                               
  int start = 1;                                                                
  int end = C.size();                                                           
  int min_nails = -1;                                                           
  while (start <= end) {                                                        
    int mid = (start + end) / 2;                                                
    if (check(A, B, C, mid)) { end = mid - 1; min_nails = mid; }                
    else start = mid + 1;                                                       
  }                                                                             
  return min_nails;                                                             
}

Fattal

Answer 4

This is the summary of the entire algorithm. I think who understands it won't have any question in mind.

What we are doing?

1- Order the nails without losing their original indexes.

2- For each plank, find the min nail value that can nail the plank by using binary search.

3- Find each nail's min original index between min nail value and the end position of the plank, and take the minimum of these min original indexes.

4- Return the maximum of the min nailing original index of each plank.

Why we are doing it?

1- We don't want to search entire array to find the min index. The original order of the index is what is asked, so we need to store it.

2- We need to find the minimum nail value to limit the number of possible original index needed to be checked. Binary search is required to find the minimum value in logarithmic time complexity.

3- We need to find the original indexes of the candidate nails. The first candidate can be the min nail value, and the last candidate can be the end position of the plank. That's why we check the original indexes only in this interval.

4- We find the min original index of nail for each plank. But the answer will be the maximum of these min indexes since the question asks the index of the last nail we use, when we finish nailing each plank.

Sungod