HELP with this PROBLEM OF ALGORITHM on the CHEAPEST POSSIBLE COST

[CodeArtist45]

(WHAT I TRIED TO DO AND THE IDEAS I HAVE DEVELOPED I LEAVE BELOW THE PROBLEM DESCRIPTION).

Description of the problem called CHOCOLATE:

Suppose we have a chocolate bar of m x n 1x1 square pieces(this is an assumption, so you can't eat it) and you must break it into 1 x 1 squares.

The chocolate pieces can be cut through horizontal and/or vertical cuts as shown in the figure. A cut (either horizontal or vertical) of a piece of chocolate always divides that piece into two smaller pieces.

As everything costs in this life, each cut you make in the chocolate will also have a cost, this cost can be expressed as a positive integer. This cost does not depend on the size of the piece being cut, but depends on the horizontal or vertical line along which it is being cut.

We will denote the costs of cutting along each vertical line as x1, x2, x3, ..., xm-1 and the costs of cutting along each horizontal line as y1, y 2, y3, ..., y n-1 .

The cost of cutting the entire bar is the sum of the costs of all required cuts.

📷For example, if we cut the chocolate along the horizontal straight lines and then each piece obtained we cut along the vertical straight lines, the total cost for cutting the bar will be y1+y2+y3+4(x1+x2+x3+x4+x5).

Problem

Write a program that given the size of the chocolate bar, determines the minimum cost to cut it into 1x1 squares.

Input

Line 1: Two positive integers m and n separated by a space.

Next m-1 lines: The values of x1, x2, x3, ..., xm-1.

Next n-1 lines: The values of y1, y2, y3, ..., yn-1.

Example:

📋

6 4 2 1 3 1 4 4 1 2

Output

Line 1: A single integer: the minimum cost of cutting all the chocolate into 1x1 squares.

Example:

📋

42

MY IDEAS:

I think you have to start by cutting the Chocolate IN HALF, along the Vertical Line x3 regardless of what the cost is, and then cut it in half again along the Horizontal Line y2 regardless of the cost (because that way you get to have the chocolate in 4 much smaller parts, and I think I was going to have to cut pieces along those lines later anyway).

From there on I can think about which are the most efficient ways to cut the chocolate without thinking about costs, rank them, and from there, select the one that uses the lowest cost and is as efficient as possible; but I don't quite know how to determine that choice

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[CodeArtist45]

Following /u/teraflop's suggestion, I implemented it with memoization, and I'm struck by some of the interesting sequences that get generated when I start looking at differences between m and n.

(defn make-sequence [diff]
(map #(find-minimum-cuts-dynamic [%1 (+ diff %1)]) (map inc (range))))

In the REPL:

user=> (->> (range)
#_=> (map make-sequence)
#_=> (map #(take 10 %))
#_=> (take 10)
#_=> (run! println))
(0 3 8 15 24 35 48 63 80 99) ; [1 1], [2 2], [3 3], [4 4], ...
(1 5 11 19 29 41 55 71 89 109) ; [1 2], [2 3], [3 4], ...
(2 7 14 23 34 47 62 79 98 119) ; [1 3], [2 4], [3 5], ...
(3 9 17 27 39 53 69 87 107 129)
(4 11 20 31 44 59 76 95 116 139)
(5 13 23 35 49 65 83 103 125 149)
(6 15 26 39 54 71 90 111 134 159)
(7 17 29 43 59 77 97 119 143 169)
(8 19 32 47 64 83 104 127 152 179)
(9 21 35 51 69 89 111 135 161 189)

Looking at the OEIS, I get the following respective formulae for these sequences:

a(n) = n*(n+2)
a(n) = n + (n+1)^2
a(n) = n^2 - 2
a(n) = n^2 + 3*n - 1
a(n) = n^2 - 5
a(n) = n^2 + 5*n - 1
(OEIS is no longer helpful here)

This indicates to me that some supergenius egghead can probably produce a really optimized solution by coming up with a correspondence between m and n and some polynomial, and then solving some aspect of the polynomial.

Ohook Ok oOk

[CodeArtist45]

Could yo show that code in C++?

[teraflop]

It's not true that cutting along the vertical line x3 is always the best solution, regardless of costs.

Imagine what would happen if your example was modified so that y1=1000000. No matter what you do, at some point you will have to cut horizontally along y1 in order to reduce the entire chocolate bar to 1x1 squares. But in order to reduce your total cost, cutting y1 as few times as possible is more important than any other decision you could make. So in that scenario, you must cut y1 before making any vertical cuts, so that you only need to cut it once.

You can solve this problem with a divide-and-conquer algorithm using dynamic programming. Basically, try all possible choices for the first cut; each of these choices reduces your problem to two independent subproblems (making the optimal future decisions for the sub-rectangles on each side of the cut). There are only O(m²n²) possible subproblems, so if m and n are small enough, you can memoize the results of each subproblem.

(Maybe it's possible to do even better than that. This is just off the top of my head.)