Hộp Quà (HOPQUA)

Nguồn: Bài tập học viên gửi Độ khó: Trung bình Tham lam Sắp xếp Hai con trỏ

Đề bài

Bài 2 (6 điểm): HỘP QUÀ

Có $N$ hộp quà được đánh số từ $1$ đến $N$, hộp quà thứ $i$ $(i = 1, 2, \ldots, N)$ có giá trị thẩm mỹ là $m_i$. Nếu xếp lần lượt các hộp quà theo số thứ tự $1, 2, \ldots, N$ thì giá trị thẩm mỹ của $N$ hộp quà là

$m_1 + m_2 + \ldots + m_N + \max(0, m_2 - m_1) + \max(0, m_3 - m_2) + \ldots + \max(0, m_N - m_{N-1})$.

Học sinh An được giao nhiệm vụ là tìm ra cách xếp $N$ hộp quà sao cho giá trị thẩm mỹ của $N$ hộp quà là lớn nhất.

Yêu cầu: Cho $N$ và $m_i$, $i = 1, 2, \ldots, N$. Xác định giá trị thẩm mỹ lớn nhất của $N$ hộp quà.

Dữ liệu: Vào từ file văn bản HOPQUA.INP gồm:

• Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^5)$.
• Dòng thứ 2 chứa $N$ số nguyên $m_1, m_2, \ldots, m_N$ $(1 \le m_i \le 10000)$. Các số ghi cách nhau một dấu cách.

Kết quả: Đưa ra file văn bản HOPQUA.OUT giá trị thẩm mỹ lớn nhất của $N$ hộp quà.

Giới hạn thời gian: 1 giây. (Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé.)

HOPQUA.INP

5
5 3 1 7 10

HOPQUA.OUT

39

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề: ta được phép xếp lại thứ tự 5 hộp quà $\{5, 3, 1, 7, 10\}$. Nếu xếp thành $1, 10, 3, 7, 5$ thì giá trị thẩm mỹ là

$(1 + 10 + 3 + 7 + 5) + \max(0, 9) + \max(0, -7) + \max(0, 4) + \max(0, -2) = 26 + 9 + 0 + 4 + 0 = 39$

và không có cách xếp nào cho kết quả lớn hơn, nên đáp án là 39. Nói nôm na: mỗi lần hộp đứng sau "cao hơn" hộp đứng trước thì được thưởng thêm đúng phần chênh lệch, còn thấp hơn thì không bị trừ gì cả (lấy $\max$ với $0$).

Nhắc lại ngưỡng TLE

Với giới hạn 1 giây, tổng số lần lặp của cả bài chỉ nên ở mức $(3 \div 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm, cao lắm là $10^8$ (hên xui). Đó là với C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 3 giây thì nhân 3, 100 ms thì chia 10, cứ thế thôi.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử mọi hoán vị · O(N!·N)Cách 2Tham lam + hai con trỏ · O(N log N)

Cách 1Vét cạn thử mọi cách xếp – O(N!·N)

Cách "làm theo đề" đơn giản nhất: thử hết tất cả các cách xếp (tất cả các hoán vị của dãy), với mỗi cách xếp tính giá trị thẩm mỹ đúng như công thức đề cho, rồi lấy lớn nhất. Trong C++ có sẵn hàm next_permutation để sinh lần lượt mọi hoán vị (nhớ sort tăng dần trước để nó đi qua đủ tất cả), Python thì có itertools.permutations.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    long long best = 0;
    do{
        long long cur = 0;
        for(int i = 0; i < n; ++i){
            cur += a[i];
            if(i > 0) cur += max(0, a[i] - a[i - 1]);
        }
        best = max(best, cur);
    } while(next_permutation(a.begin(), a.end()));
    cout << best;
    return 0;
}

from itertools import permutations

n = int(input())
a = list(map(int, input().split()))
best = 0
for p in permutations(a):
    cur = sum(p)
    for i in range(1, n):
        cur += max(0, p[i] - p[i - 1])
    best = max(best, cur)
print(best)

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$.
• Thời gian: có $N!$ cách xếp, mỗi cách tính mất $O(N)$ ⇒ $O(N! \cdot N)$. Chỉ cần $N = 12$ là đã gần $6 \cdot 10^9$ phép tính rồi, trong khi đề cho $N$ tới $10^5$ ⇒ TLE chắc luôn.

Không gian$O(N)$

Thời gian$O(N! \cdot N)$

Vẫn nên cài đặt

Cách này không dùng để nộp, nhưng rất có ích để làm "trọng tài": sinh các test nhỏ ngẫu nhiên ($N \le 8$) rồi so kết quả với cách tối ưu bên dưới. Mình đã kiểm tra cách 2 đúng bằng chính code này.

Cách 2Tham lam: ghép lớn nhất với bé nhất – O(N log N)

Bài này để giải quyết nó chúng ta sẽ dùng phương pháp tham lam (Greedy). Kể cả bạn nào không biết về tham lam thì thực ra đôi khi các bạn vẫn đang giải quyết vấn đề theo chính tư tưởng của nó mà không biết. Nói nhanh: tham lam nghĩa là đứng trước nhiều lựa chọn thì ta chọn cách tốt nhất ở hiện tại rồi đi theo nó; lại đứng trước nhiều lựa chọn nữa thì lại chọn cái tốt nhất trong số đó – cứ tốt nhất mà triển, vì thế mới gọi là tham lam. Nó không có công thức từng bước cụ thể như mấy thuật toán khác, chỉ là một tư tưởng, còn để hiện thực được thì có thể cần thêm những kỹ thuật bổ trợ khác (như bài này là sắp xếp + hai con trỏ).

Tại sao bài này nhìn ra mùi tham lam? Đọc đề thấy rõ luôn hehe: muốn sắp xếp theo quy luật gì đó để sau cùng đáp án là lớn nhất ⇒ thấy mùi tham lam ngay 😁.

Nhận xét 1: tổng các phần tử không đổi

Giá trị thẩm mỹ $= \underbrace{m_1 + m_2 + \ldots + m_N}_{\text{tổng các phần tử}} + \underbrace{\max(0, m_2 - m_1) + \ldots + \max(0, m_N - m_{N-1})}_{\text{tổng các "bước lên"}}$ (trong bài này quy ước vị trí tính từ 1 nhé).

Phần tổng các phần tử thì dù sắp xếp thế nào sau cùng vẫn cộng đủ các giá trị của tụi nó thôi. Vậy yếu tố quyết định chính là phần thứ hai: sắp xếp sao cho tổng các hiệu "thằng đứng sau trừ thằng đứng trước" là lớn nhất. Hiệu nào âm thì chỉ lấy $0$, coi như không được cộng gì; hiệu nào dương thì chính nó được cộng vô.

Nhận xét 2: lớn nhất trừ bé nhất, lớn nhì trừ bé nhì...

Đến đây tư tưởng tham lam thấy rất rõ ràng: làm sao để mỗi cặp đứng cạnh nhau (thằng sau trừ thằng trước) ra giá trị lớn nhất có thể; càng nhiều kết quả lớn cộng lại thì kết quả sau cùng càng lớn. Chênh lệch lớn nhất là cặp <lớn nhất> − <bé nhất>, sau đó là <lớn 2> − <bé 2>, rồi <lớn 3> − <bé 3>... Tức là xếp dãy theo quy luật:

bé nhất, lớn nhất, bé 2, lớn 2, bé 3, lớn 3, …

Với ví dụ mẫu, dãy sau khi xếp như vậy là $1, 10, 3, 7, 5$, và như đã tính ở trên ra đúng $39$ – khớp với kết quả đề cho, phần nào yên tâm về tư tưởng tham lam này hehe.

Còn các cặp "nối" như <bé 2> − <lớn nhất> hay <bé 3> − <lớn 2> thì kết quả hoặc là $0$ (khi tụi nó bằng nhau) hoặc là âm, mà đề lấy $\max$ với $0$ nên sau cùng cũng chỉ cộng $0$ – coi như không cần cộng luôn. Vậy chỉ cần cộng các hiệu lớn trừ bé là được.

Vì sao không thể làm tốt hơn?

Mỗi "bước lên" $m_{i+1} - m_i \gt 0$ cho phần tử đứng sau hệ số $+1$ và phần tử đứng trước hệ số $-1$. Cộng dồn lại, mỗi phần tử có hệ số tổng là $-1$, $0$ hoặc $+1$ (nó chỉ có tối đa 1 hàng xóm trái và 1 hàng xóm phải), và số phần tử mang $+1$ bằng số phần tử mang $-1$. Có $N$ phần tử nên mỗi loại có không quá $k = \lfloor N/2 \rfloor$ phần tử. Do đó tổng các bước lên $\le$ (tổng $k$ số lớn nhất) − (tổng $k$ số bé nhất) – và cách xếp ở trên đạt đúng bằng giá trị này.

Đừng để đề đánh lừa

Đề chỉ hỏi tổng sau cùng, không bắt in ra dãy sau khi sắp xếp. Vậy ta không cần sắp xếp theo kiểu "bé, lớn, bé, lớn" làm gì, cứ sắp xếp tăng dần thôi, rồi dùng kỹ thuật hai con trỏ (Two Pointers): $L = 1$, $R = N$, cộng $a[R] - a[L]$ vào kết quả, rồi $L{+}{+}$, $R{-}{-}$, lặp lại đến khi $L \ge R$ thì dừng.

Minh hoạ

Em nhập dãy giá trị các hộp quà rồi bấm Tiếp: dãy được sắp tăng dần, hai con trỏ $L$, $R$ chạy từ hai đầu vào giữa; mỗi bước ghép một cặp (bé, lớn) và cộng thêm $a[R] - a[L]$. Hàng dưới là cách xếp hộp quà tương ứng (bé nhất, lớn nhất, bé 2, lớn 2...).

Giá trị m

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int a[n + 1];
    long long sum = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + 1 + n);
    int l = 1, r = n;
    while(l < r){
        sum += a[r] - a[l];
        l++;
        r--;
    }
    cout << sum;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + sorted(map(int, data[1:n + 1]))
s = sum(a)
l, r = 1, n
while l < r:
    s += a[r] - a[l]
    l += 1
    r -= 1
print(s)

Giải thích một số chỗ trong code:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);): hiểu cơ bản là giúp cin/cout của C++ chạy nhanh gần bằng nhập xuất của C. Bài này phải đọc tới $10^5$ số nên thêm 3 dòng này vào cho chắc ăn. Code C++ thì nhớ thêm 3 dòng này vào đầu hàm main nhé.
2. Biến sum tận dụng ngay vòng lặp đọc dữ liệu để cộng từng phần tử vào luôn; khúc sau chỉ cần cộng thêm các hiệu $a[R] - a[L]$.
3. Hàm sort có sẵn trong thư viện của C++ luôn đảm bảo $O(N \log N)$. $N$ tới $10^5$ nên phải dùng nó (hoặc tự cài Quick Sort, Merge Sort, Heap Sort); còn mấy kiểu Interchange Sort, Selection Sort, Bubble Sort $O(N^2)$ thì TLE chắc luôn. Tự cài vừa mất công vừa dễ sai, lỡ xui Quick Sort rơi vào trường hợp xấu nhất cũng thành $O(N^2)$, nên cứ dùng sort có sẵn cho nhanh gọn.
4. sum kiểu long long: tổng các phần tử tối đa $10^5 \cdot 10^4 = 10^9$, cộng thêm các hiệu tối đa khoảng $5 \cdot 10^4 \cdot 10^4 = 5 \cdot 10^8$ ⇒ cỡ $1.5 \cdot 10^9$, đã khá sát giới hạn của int (khoảng $2.1 \cdot 10^9$). Dự kiến kết quả lớn nên để chắc ăn mình để long long (số nguyên 8 byte) cho khỏi lo tràn số.
5. Mảng a có $N + 1$ phần tử: bỏ qua chỉ số 0, chỉ dùng chỉ số $1..N$ cho khớp với đề, tránh bị loạn.

C++▶ Chạy tay từng dòng codeCộng tổng các phần tử, sắp tăng dần rồi hai con trỏ l, r cộng thêm a[r] − a[l].

Dữ liệu vào (stdin) – sửa thoải mái5 5 3 1 7 10

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(false);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 int a[n + 1];

11 long long sum = 0;

12 for(int i = 1; i <= n; ++i){

13 cin >> a[i];

14 sum += a[i];

15 }

16 sort(a + 1, a + 1 + n);

17 int l = 1, r = n;

18 while(l < r){

19 sum += a[r] - a[l];

20 l++;

21 r--;

22 }

23 cout << sum;

24 return 0;

25}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng $a$ ($N$ là số hộp quà).
• Thời gian: $O(N)$ đọc dữ liệu + $O(N \log N)$ sắp xếp + $O(N)$ hai con trỏ. Theo quy tắc cộng Big-O lấy thành phần lớn nhất ⇒ $O(N \log N)$. Trường hợp xấu nhất $N = 10^5$: khoảng $10^5 + 17 \cdot 10^5 + 10^5 \approx 2 \cdot 10^6$ lần lặp, ít hơn ngưỡng $(3 \div 5) \cdot 10^7$ từ 10 đến 20 lần nên yên tâm không bị TLE.

Không gian$O(N)$

Thời gian$O(N \log N)$

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với 400 bộ test ngẫu nhiên ($N \le 8$), so với code vét cạn thử mọi hoán vị ở cách 1 – khớp hết. Với $N = 10^5$: bản C++ chạy khoảng 0.03 giây, bản Python khoảng 0.2 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇