HackerRank Cutting Boards problem solution

In this HackerRank Cutting Boards problem solution Alice gives Bob a board composed of 1 x 1 wooden squares and asks him to find the minimum cost of breaking the board back down into its individual squares. To break the board down, Bob must make cuts along its horizontal and vertical lines.

To reduce the board to squares, Bob makes horizontal and vertical cuts across the entire board. Each cut has a given cost, cost_y[i] or cost_x[j] for each cut along a row or column across one board, so the cost of a cut must be multiplied by the number of segments it crosses. The cost of cutting the whole board down into 1 x 1 squares is the sum of the costs of each successive cut.

Can you help Bob find the minimum cost? The number may be large, so print the value modulo 10 to power 9 plus 7.

Problem solution in Python.

import heapq

def cuts_cost(y, x):
    heapq.heapify(y)
    heapq.heapify(x)

    hori_segs = 1
    vert_segs = 1
    total = 0
    while y and x:
        cost_y = heapq.heappop(y)
        cost_x = heapq.heappop(x)

        if (cost_y < cost_x) or (cost_y == cost_x and vert_segs <= hori_segs):
            heapq.heappush(x, cost_x)
            highest = cost_y
            total += hori_segs * highest
            vert_segs += 1
        else:
            heapq.heappush(y, cost_y)
            highest = cost_x
            total += vert_segs * highest
            hori_segs += 1

    total += hori_segs * sum(y)
    total += vert_segs * sum(x)

    return -total % (10**9 + 7)


num_tests = int(input().strip())
for test in range(num_tests):
    m, n = tuple(int(i) for i in input().strip().split(" "))
    costs_y = [-int(i) for i in input().strip().split(" ")]
    costs_x = [-int(i) for i in input().strip().split(" ")]
    print(cuts_cost(costs_y, costs_x))

Problem solution in Java.

import java.util.*;

public class Solution {
    
    static int N;
    static int[] array;
    static long INF = Long.MAX_VALUE;
    static long mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-- != 0) {
            int m = in.nextInt();
            int n = in.nextInt();
            int[] y = new int[m];
            int[] x = new int[n];
            for(int i=1; i<m; i++) y[i] = in.nextInt();
            for(int i=1; i<n; i++) x[i] = in.nextInt();
            Arrays.sort(y);
            Arrays.sort(x);
            int i = 1;
            int j = 1;
            long count = 0;
            while(i < n || j < m) {
                long valX = -1;
                long valY = -1;
                if(i < n) valX = x[n-i];
                if(j < m) valY = y[m-j];
                if(valX > valY) {
                    count = (count + j*valX)%mod;
                    i++;
                } else {
                    count = (count + i*valY)%mod;
                    j++;
                }
            }
            System.out.println(count);
        }
    }
}
 

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long int ulint; 

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int T;
    cin >> T;
    
    for (int t = 0; t < T; t++){
        ulint M, N;
        cin >> M >> N;
        
        vector < ulint > A (M-1, 0);
        vector < ulint > B (N-1, 0);
        
        for (ulint i = 0; i < M - 1; i++){
            cin >> A[i];
        }
        for (ulint i = 0; i < N - 1; i++){
            cin >> B[i];
        }
                
        sort ( A.begin(), A.end() );
        sort ( B.begin(), B.end() );
        reverse ( A.begin(), A.end() );
        reverse ( B.begin(), B.end() );
        
        ulint xFactor = 1, yFactor = 1;
        ulint xi = 0, yi = 0;
        ulint total = 0;
        
        while ( (xi != A.size()) || (yi != B.size()) ){
            if ( xi == A.size() ){
                while ( yi != B.size() ){
                    total += yFactor * B[yi];
                    ++yi;
                }
            } else if ( yi == B.size() ) {
                while ( xi != A.size() ){
                    total += xFactor * A[xi];
                    ++xi;
                }
            } else if (A[xi] > B[yi]){
                total += A[xi] * xFactor;
                ++yFactor;
                ++xi;
            } else {
                total += B[yi] * yFactor;
                ++xFactor;
                ++yi;
            }
        }
        
        cout << total % 1000000007 << endl;
    }
    
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int comp (const void * elem1, const void * elem2) 
{
    int f = *((int*)elem1);
    int s = *((int*)elem2);
    if (f > s) return 1;
    if (f < s) return -1;
    return 0;
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int t;
    scanf("%d", &t);
    for (int t1 = 0; t1 < t; t1++){
        int m, n;
        scanf("%d %d", &m, &n);
        m--;
        n--;
        int i, y[m], x[n];
        for (i = 0; i < m; i++){
            scanf("%d", &y[i]);
        }
        for (i = 0; i < n; i++){
            scanf("%d", &x[i]);
        }
        qsort (y, m, sizeof(*y), comp);
        qsort (x, n, sizeof(*x), comp);
        long sum = 0;
        i = n - 1;
        int j = m - 1;
        long rseg = 1, cseg = 1;
        int p = 1000000007;
        while (j >= 0 && i >= 0){
            if (y[j] <= x[i]){
                sum += (x[i--] * rseg) % p;
                cseg++;
            } else {
                sum += (y[j--] * cseg) % p;
                rseg++;
            }
        }
        while (j >= 0) sum += (y[j--] * cseg) % p;
        while (i >= 0) sum += (x[i--] * rseg) % p;
        printf("%ldn", sum % p);
    }
    return 0;
}