Official

F - Bread Editorial by en_translator

First, let us constrain the problem: consider finding the minimum cost when \(L=A_1+A_2+\ldots +A_N\).
By reversing the operations, this can be seen as a problem in which you are allowed to concatenate a piece of bread of length \(x\) and another of \(y\) for a cost of \(x+y\), starting from those of length \(A_1\), \(\ldots\), \(A_N\).

Here, the minimum cost in the original problem is equal to the sum of costs of repeating the following operation \((N-1)\) times on a multiset initialized with \(S=\{ A_1,A_2,\ldots,A_N \}\):

  • Let \(s_1\) and \(s_2\) be the smallest elements of \(S\). Concatenate a piece of bread of length \(s_1\) and another of \(s_2\) for a cost of \(s_1+s_2\). Then, remove \(s_1\) and \(s_2\) from \(S\) and insert \(s_1+s_2\) to \(S\).

Since the number of elements of \(S\) decreases by \(1\) every time the operation is performed, it is obvious that it is possible to do so. The following is the proof that this sequence of operations minimizes the cost.

The proof that the algorithm above minimizes the cost

The following proof is almost the same to the proof that Huffman coding is a compact coding.

Preparation

Consider a rooted tree whose vertices are the pieces of bread that appear during the concatenations (including the initial and final ones), leaves corresponding the initial pieces and the root to the final whole piece, and the parent of piece of bread other than the root is the resulting bread after the concatenation of the piece and another. Then, every vertex in this rooted tree, except for the leaves, has exactly two children.

Also, define the weight of each vertex by the length of the corresponding piece of bread, then the cost of whole process of concatenations is represented by the sum of weights of vertices other than the leaves. Here, note that each vertex except for leaves has the weight equal to the sum of children's weights. Moreover, considering how many times the weight of each leave are added, we can see that the sum can be considered as the sum of (weight)$\times$(the depth in the rooted tree).

Therefore, in the tree corresponding to the process of concatenations that minimizes the cost, we may assume that the two leaves with the smallest weights have the maximum depths in the tree. (Note that the tree always has two or more vertices with the maximum depth, since each non-leaf vertex has two children) This is because, if it is no the case, we can swap the weights of the leaves so that the total cost is reduced. Moreover, we may assume that these have the same parent, because swapping the leaves with the same depths does not change the total cost.

Proof

We proof by induction on $N$.

i ) If $N=2$

It is obvious because there is only one way to concatenate.

ii ) If $N=N_0+1$, supposing that it is true for $N=N_0$

Let $C'$ be the minimum cost when concatenating $A_1,A_2, \ldots, A_{N_0+1}$. Here, without loss of generality, we can assume that $A_1$ and $A_2$ are the smallest two elements of $A_1,A_2, \ldots, A_{N_0+1}$. Let $C'$ be the minimum cost to concatenate $A_1,A_2, \ldots, A_{N_0+1}$, then the total cost of concatenating by the algorithm above is, by induction, $C+A_1+A_2$. Therefore, $C'\leq C+A_1+A_2$. On the other hand, considering the tree corresponding to the process of concatenations that minimizes the cost for concatenating $A_1,A_2, \ldots, A_{N_0+1}$, as described in the Preparation above, there exists a vertex whose children have weights $A_1$ and $A_2$. By removing these two leaves, we obtain the tree corresponding to the process of concatenating $A_1+A_2, A_3,A_4,\ldots, A_{N_0+1}$. The cost corresponding to this tree is $C'-A_1-A_2$, so since $C\leq C'-A_1-A_2$, we have $C'\geq C+A_1+A_2$. Therefore, $C'=C+A_1+A_2$, which is achieved by the algorithm above. Hence, it has been proved.

We have now shown the minimum value for \(L=A_1+A_2+\cdots+A_N\).
For \(L>A_1+A_2+\cdots+A_N\), we have to find the minimum cost of concatenating pieces of bread of lengths \(A_1, A_2,\ldots,A_N, B_1,B_2,\ldots, B_M\) for all integer tuples \((B_1,B_2,\ldots, B_M)\) such that \(B_1+B_2+\cdots+B_M=L-(A_1+A_2+\cdots+A_N)\) and \(B_i>0\).

In conclusion, the cost is minimized when \(M=1\) and \(B_1=L-(A_1+A_2+\cdots+A_N)\).

Proof

In order to show this, it is sufficient to show that the minimum cost required to concatenate \(A_1,A_2,\ldots, A_N\) is no less than that for \(A_1+A_2,A_3,A_4, \ldots, A_N\).

Consider the tree corresponding to the former.

  • Choose the shallower of \(A_1\) and \(A_2\) (if they have the same depth, either can be chosen) and replace the weights of its leaves with \(A_1+A_2\). Replace the weights of its ancestors accordingly.
  • Remove the other leaf, and let \(X\) be the weight of the other child of its parent. Remove the other child and replace the weight of the parent with \(DX\). Replace the weights of its ancestors accordingly.

Now we have a tree with the cost no greater than that of the original. On the other hand, it is greater than or equal to the minimum cost required to concatenate \(A_1+A_2,A_3,A_4, \ldots, A_N\), so we have shown what we want to prove.

This algorithm can be implemented in a total of \(O(N\log N)\) time. Therefore, the problem has been solved sufficiently fast.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	priority_queue<long long, vector<long long>, greater<long long> >pq;
	long long x, y, l;
	long long ans = 0;

	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		cin >> x;
		l -= x;
		pq.push(x);
	}

	if (l > 0) {
		pq.push(l);
		n++;
	}
	for (int i = 0; i < (n - 1); i++) {
		x = pq.top();
		pq.pop();
		y = pq.top();
		pq.pop();
		ans += x + y;
		pq.push(x + y);
	}

	cout << ans << endl;
	return 0;
}

posted:
last update: