Codility Lesson 14

14.1 - Min Max Division

You are given integers K, M and a non-empty array A consisting of N integers. Every element of the array is not greater than M.

You should divide this array into K blocks of consecutive elements. The size of the block is any integer between 0 and N. Every element of the array should belong to some block.

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The large sum is the maximal sum of any block.

For example, you are given integers K = 3, M = 5 and array A such that:

  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2

The array can be divided, for example, into the following blocks:

• [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
• [2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
• [2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
• [2, 1], [5, 1], [2, 2, 2] with a large sum of 6.

The goal is to minimize the large sum. In the above example, 6 is the minimal large sum.

Write a function:

class Solution 
{
  public int solution(int K, int M, int[] A); 
}

that, given integers K, M and a non-empty array A consisting of N integers, returns the minimal large sum.

For example, given K = 3, M = 5 and array A such that:

  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2

the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

• N and K are integers within the range [1..100,000];
• M is an integer within the range [0..10,000];
• each element of array A is an integer within the range [0..M].

using System;
using System.Linq;

/**
 * 14.1 - Min Max Division
 * Paulo Santos
 * 10.Jan.2023
 */
class Solution {
    public int solution(int K, int M, int[] A) {

        var st = A.Max();
        var ed = A.Sum();
        while (st <= ed) {
            var md = (st + ed) / 2;
            if (VerifyBlocks(A, md) < K) 
                ed = md - 1;
            else
                st = md + 1;
        }
        return st;
    }

    private int VerifyBlocks(int[] A, int maxSum) {
        var sm = 0;
        var ct = 0;
        for (var i = 0; i < A.Length; i++) {
            if (sm + A[i] > maxSum) {
                sm = 0;
                ct += 1;
            }
            sm += A[i];
        }
        return ct;
    }
}

---

14.2 - 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].

For example, given arrays A, B such that:

    A[0] = 1    B[0] = 4
    A[1] = 4    B[1] = 5
    A[2] = 5    B[2] = 9
    A[3] = 8    B[3] = 10

four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:

    C[0] = 4
    C[1] = 6
    C[2] = 7
    C[3] = 10
    C[4] = 2

if we use the following nails:

• 0, then planks [1, 4] and [4, 5] will both be nailed.
• 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
• 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
• 0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

Write a function:

class Solution 
{
  public int solution(int[] A, int[] B, int[] C); 
}

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.

If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:

    A[0] = 1    B[0] = 4
    A[1] = 4    B[1] = 5
    A[2] = 5    B[2] = 9
    A[3] = 8    B[3] = 10

    C[0] = 4
    C[1] = 6
    C[2] = 7
    C[3] = 10
    C[4] = 2

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:

• N and M are integers within the range [1..30,000];
• each element of arrays A, B and C is an integer within the range [1..2*M];
• A[K] ≤ B[K].

using System;

/**
 * 14.2 - Nailing Planks
 * Paulo Santos
 * 12.Jan.2023
 */
class Solution {
    public int solution(int[] A, int[] B, int[] C) {

        var start = 0;
        var end = C.Length;
        var midNails = -1;
        while (start <= end) {
            var mid = (start + end) / 2;
            if (CheckNail(A, B, C, mid)) {
                end = mid - 1;
                midNails = mid;
            }
            else
                start = mid + 1;
        }
        return midNails;
    }

    private bool CheckNail(int[] A, int[] B, int[] C, int mid) {
        
        var M = C.Length;
        var prefixSum = new int[2 * M + 1];
        for (var i = 0; i < mid; i++) 
            prefixSum[C[i]] += 1;
        for (var i = 1; i < prefixSum.Length; i ++)
            prefixSum[i] += prefixSum[i - 1];
        for (var i = 0; i < A.Length; i++)
            if (prefixSum[B[i]] == prefixSum[A[i] - 1])
                return false;

        return true;

    }
}