HackerRank Cutting Boards Problem Solution
In this post, we will solve 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 [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 109 +7.
For example, you start with a 2 x 2 board. There are two cuts to be made at a cost of cost y[1] = 3 for the horizontal and cost_x[1]= 1 for the vertical. Your first cut is across 1 piece, the whole board. You choose to make the horizontal cut between rows 1 and 2 for a cost of 1 x 3 = 3. The second cuts are vertical through the two smaller boards created in step 1 between columns 1 and 2. Their cost is 2 x 1 = 2. The total cost is 3 + 2 = 5 and 5%(109 +7)=5.
Function Description
Complete the boardCutting function in the editor below. It should return an integer.
boardCutting has the following parameter(s):
- cost_x: an array of integers, the costs of vertical cuts
- cost_y: an array of integers, the costs of horizontal cuts
Input Format
The first line contains an integer q, the number of queries.
The following a sets of lines are as follows:
- The first line has two positive space-separated integers m and n, the number of rows and columns in the board.
- The second line contains m – 1 space-separated integers cost_y[i], the cost of a horizontal cut between rows [i] and [i+1] of one board.
- The third line contains n – 1 space-separated integers cost_x[j], the cost of a vertical cut between columns [j] and [j+1] of one board.
Output Format
For each of the q queries, find the minimum cost (minCost) of cutting the board into 1 x 1 squares and print the value of minCost % (10 power 9 +7).
Sample Input 0
1
2 2
2
1
Sample Output 0
4Explanation 0
We have a 2 x 2 board, with cut costs cost y[1] = 2 and cost_x[1] = 1. Our first cut is horizontal between y[1] and y[2], because that is the line with the highest cost (2). Our second cut is vertical, at [1]. Our first cut has a total Cost of 2 because we are making a cut with cost cost y[1] = 2 across 1 segment, the uncut board. The second cut also has a total Cost of 2 but we are making a cut of cost cost_x[1]= 1 across 2 segments. Our answer is minCost = ((2 x 1) + (1 x 2)) % (10 power 9 +7)= 4.
Cutting Boards C Solution
#include <stdio.h>
#define MAX_N 1000000
#define MODULUS 1000000007
int x[MAX_N];
int y[MAX_N];
int cmp(int *a, int *b)
{
return *b - *a;
}
int main()
{
int M, N;
int i, j;
unsigned long long ans;
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &M, &N);
--M, --N;
for (i = 0; i < M; ++i)
{
scanf("%d", &x[i]);
}
for (j = 0; j < N; ++j)
{
scanf("%d", &y[j]);
}
qsort(x, M, sizeof(int), cmp);
qsort(y, N, sizeof(int), cmp);
i = j = 0;
ans = 0;
while (i < M && j < N)
{
if (x[i] > y[j])
{
ans += x[i++] * (j + 1LLU);
ans %= MODULUS;
}
else
{
ans += y[j++] * (i + 1LLU);
ans %= MODULUS;
}
}
while(i < M)
{
ans += x[i++] * (j + 1LLU);
ans %= MODULUS;
}
while(j < N)
{
ans += y[j++] * (i + 1LLU);
ans %= MODULUS;
}
printf("%llu\n", ans);
}
return 0;
}Cutting Boards C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int cases;
cin >> cases;
while (cases-- > 0) {
int m, n;
cin >> m >> n;
vector<long int> m_costs(--m);
vector<long int> n_costs(--n);
for (auto & cost : m_costs) {
cin >> cost;
}
for (auto & cost : n_costs) {
cin >> cost;
}
sort(m_costs.rbegin(), m_costs.rend());
sort(n_costs.rbegin(), n_costs.rend());
int m_index = 0;
int n_index = 0;
long long int cost = 0;
while (m_index < m && n_index < n) {
if (m_costs[m_index] > n_costs[n_index]) {
cost += (m_costs[m_index] * (n_index + 1)) % 1000000007;
++m_index;
} else {
cost += (n_costs[n_index] * (m_index + 1)) % 1000000007;
++n_index;
}
}
if (m_index < m) {
++n_index;
while (m_index < m) {
cost += (m_costs[m_index++] * n_index) % 1000000007;
}
} else if (n_index < n) {
++m_index;
while (n_index < n) {
cost += (n_costs[n_index++] * m_index) % 1000000007;
}
}
cout << cost % 1000000007 << endl;
}
return 0;
}Cutting Boards C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static ulong[] val;
static bool[] hor;
static void Main(String[] args) {
int tc = Convert.ToInt32(Console.ReadLine());
for(int ti=0;ti<tc;ti++)
{
int[] mn = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int m = mn[0];
int n = mn[1];
int i,j;
ulong[] x = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), UInt64.Parse);
ulong[] y = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), UInt64.Parse);
val = new ulong[x.Length + y.Length];
hor = new bool[x.Length + y.Length];
for(i=0;i<x.Length;i++)
{
val[i] = x[i];
hor[i] = true;
}
for(i=0;i<y.Length;i++)
{
val[i+x.Length] = y[i];
hor[i+x.Length] = false;
}
Array.Sort(val,hor);
Array.Reverse(val);
Array.Reverse(hor);
ulong v=0;
ulong h=0;
ulong cost=0;
for(i=0;i<val.Length;i++)
{
if(hor[i])
{
cost=(cost+(val[i]*(v+1))%1000000007)%1000000007;
h++;
}
else
{
cost=(cost+(val[i]*(h+1))%1000000007)%1000000007;
v++;
}
}
Console.WriteLine(cost);
}
}
}Cutting Boards Java Solution
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);
}
}
}Cutting Boards JavaScript Solution
// KG: adding mod
function cuttingBoards(M,N,m,n) {
var mod = Math.pow(10,9) + 7;
[m,n].forEach(array => array.sort((a,b) => b - a));
var cost = 0;
var mIndex = 0;
var nIndex = 0;
while (mIndex < m.length || nIndex < n.length) {
if (mIndex === m.length) {
cost += n[nIndex++] * (1+mIndex);
cost = cost % mod;
} else if (nIndex === n.length) {
cost += m[mIndex++] * (1+nIndex);
cost = cost % mod;
} else if (m[mIndex] >= n[nIndex]) {
cost += m[mIndex++] * (1+nIndex);
cost = cost % mod;
} else {
cost += n[nIndex++] * (1+mIndex);
cost = cost % mod;
}
}
return cost % mod;
}
function processData(input) {
var [T,...data] = input.split('\n');
T = parseInt(T);
data = data.map(line => line.split(' ').map(Number));
var i = 0;
var next = () => data[i++];
for (var _ = 0; _ < T; _++) {
var [M,N] = next();
var m = next();
var n = next();
console.log(cuttingBoards(M,N,m,n));
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Cutting Boards Python Solution
from fileinput import input
def find():
lines = input()
noc = [int(x) for x in lines[0].strip().split()][0]
for i in range(noc):
m,n = [int(x) for x in lines[3*i+1].strip().split()]
y = [int(x) for x in lines[3*i+2].strip().split()]
x = [int(x) for x in lines[3*i+3].strip().split()]
print(helper(y,x), end='\n')
def helper(y, x):
m, n = len(y)+1, len(x)+1
xc = yc = 1
cost = 0
a = []
for i in y:
a.append([i, 0])
for i in x:
a.append([i,1])
a.sort(key=lambda x:-x[0])
for c, d in a:
if d == 0:
xc +=1
cost = (cost + c*yc)%1000000007
else:
yc += 1
cost = (cost+c*xc)%1000000007
return cost
find()
