[C/C++] BOJ #1026 - Treasure

The problem “Treasure” (Baekjoon #1026) requires you to find the minimum possible sum of the product of two arrays, A and B.

First, you are given two arrays, A and B, each containing N integers. You can rearrange the elements of A in any order, but the order of B must remain unchanged.

The goal is to compute the sum of element-wise products between A and B such that the result is minimized. That is, you need to minimize the value of:

 

\[S = A_0 \times B_0 + A_1 \times B_1 + \dots + A_{N-1} \times B_{N-1}\]

 

To achieve this, a greedy approach should be considered. By sorting A in ascending order and B in descending order, you can ensure that the smallest numbers in A are paired with the largest numbers in B, leading to the smallest possible sum.

Your task is to implement an efficient solution that reads N, the two arrays A and B, and then calculates the minimized sum S.

---

This problem is easy to solve once you fully understand its intent. Because of this, the number of correct submissions is quite high. As of today, 8,888 people have solved it correctly, with a success rate of 61.5%. The number 8888 appeared in sequence, so I took a screenshot of it.

---

The problem requires us to rearrange the sequence A[*] in an optimal way so that the following sum is minimized:

 

\[\sum_{k} A[k] \cdot B[k]\]

 

A key constraint in the problem is that while we can rearrange A[], we cannot rearrange B[]. This is a crucial detail (a potential trap in the problem).

The problem statement can be found at the following link:

 

https://www.acmicpc.net/problem/1026

---

Let’s assume that B[] contains two elements, a and b, where a > b. Likewise, A[*] contains two elements, c and d, where c > d.

In this case, the following inequality holds:

ac + bd > ad + bc

This can be logically derived as follows:
1. Since a > b, multiply both sides by (c - d).
2. Since (c - d) > 0, the inequality remains in the same direction: a(c - d) > b(c - d)

3. Expanding the equation: ac - ad > bc - bd

4. Rearranging the terms: ac + bd > ad + bc

 

This proves that pairing larger elements of B[*] with smaller elements of A[*] will minimize the total sum.

However, the problem states that B[] cannot be rearranged, which initially seems challenging. But here’s the trick: we can sort A[*] as we wish to achieve the optimal solution.

Ultimately, the problem reduces to a sorting problem:
• Sort A[*] in ascending order.
• Sort B[*] in descending order.
• Compute the sum of their element-wise products.

 

By following this approach, we ensure that the smallest elements in A[*] are paired with the largest elements in B[*], leading to the minimum possible sum.

---

 

Treasure Number

---

Below is my implementation of the solution. Please use it only for reference.

//----------------------------------------------------------
//    baekjoon #1026 - Treasure
//        - by Aubrey Choi
//        - created at 2019-07-06
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
    int n, a[100], b[100], ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    std::sort(a, a + n);
    std::sort(b, b + n);
    for(int i = 0; i < n; i++) ans += a[i]*b[n-i-1];
    printf("%d\n", ans);
}