Trung Bình Cộng Lớn Nhất (CSLOJ 1404) (Bồi dưỡng HSGQG Hải Phòng 2020)

Nguồn: Bồi dưỡng HSGQG Hải Phòng 2020 (CSLOJ 1404) Độ khó: Khá Chặt nhị phân đáp án Mảng cộng dồn Số thực

Đề bài

Nguồn: Bài tập Bồi dưỡng HSGQG, Hải Phòng, T11/2020, Thái BK.

Cho dãy số nguyên $a_1, a_2, \ldots, a_n$ và một số nguyên dương $k$. Hãy tìm một đoạn con của $a$, có ít nhất $k$ phần tử và có trung bình cộng lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương $n, k$;
• Dòng tiếp theo chứa dãy $a$.

Dữ liệu ra:

• Ghi trung bình cộng lớn nhất tìm được, quy tròn đến số thập phân thứ năm.

Giới hạn:

• $1 \le k \le n \le 10^5$, $-10^5 \le a_i \le 10^5$;
• Có $50\%$ số test với $n \le 5000$.

Ví dụ – input

7 3
2 4 5 1 3 4 1

Ví dụ – output

3.66667

Lời mở đầu

Bữa giờ LeetCode hoài sợ anh em ngán 😅. Nay mình đi comment dạo trong một nhóm lập trình, thấy có bạn hỏi bài này, mình thấy bài cũng hay nên đăng để anh em thử sức nhé. Bài này là một ví dụ rất "kinh điển" cho kỹ thuật chặt nhị phân đáp án kết hợp mảng cộng dồn, anh em nào chưa biết kỹ thuật này thì đây là dịp tốt để học luô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 đề: với $k = 3$, ta chỉ được chọn các đoạn liên tiếp có từ 3 phần tử trở lên. Thử vài đoạn:

• $[2, 4, 5]$ có trung bình $\dfrac{11}{3} \approx 3.66667$;
• $[4, 5, 1]$ có trung bình $\dfrac{10}{3} \approx 3.33333$; $[2, 4, 5, 1]$ có trung bình $\dfrac{12}{4} = 3$;
• $[4, 5, 1, 3, 4]$ có trung bình $\dfrac{17}{5} = 3.4$; cả dãy có trung bình $\dfrac{20}{7} \approx 2.85714$...

Không đoạn nào vượt quá $\dfrac{11}{3}$, nên đáp án là 3.66667.

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

Cách 1Duyệt mọi đoạn + mảng cộng dồn · O(n²) · 50%Cách 2Chặt nhị phân đáp án · O(n log) · 100%

Cách 1Duyệt mọi đoạn với mảng cộng dồn – O(n²)

Cách tự nhiên nhất: thử hết tất cả các đoạn $[j+1, i]$ có độ dài $i - j \ge k$, tính trung bình cộng rồi lấy lớn nhất. Để tính tổng một đoạn trong $O(1)$ thì ta dùng mảng cộng dồn:

Mảng cộng dồn

$S_0 = 0,\ S_i = S_{i-1} + a_i$. Khi đó tổng đoạn $a_{j+1} + \ldots + a_i = S_i - S_j$, trung bình cộng là $\dfrac{S_i - S_j}{i - j}$.

Vậy chỉ cần 2 vòng lặp: $i$ chạy từ $k$ đến $n$ (điểm cuối đoạn), $j$ chạy từ $0$ đến $i - k$ (đoạn bắt đầu ở $j + 1$, đảm bảo đủ ít nhất $k$ phần tử).

Bẫy: chỉ xét đoạn đúng k phần tử là SAI

Nhiều bạn nghĩ "đoạn càng ngắn càng dễ có trung bình lớn" nên chỉ xét các đoạn đúng $k$ phần tử. Phản ví dụ: $k = 2$, $a = [5, 1, 5]$. Các đoạn 2 phần tử đều có trung bình $3$, nhưng cả đoạn 3 phần tử có trung bình $\dfrac{11}{3} \approx 3.66667$ lớn hơn.

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 n, k;
long long S[100005];

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        long long x;
        cin >> x;
        S[i] = S[i - 1] + x;
    }
    double best = -1e18;
    for(int i = k; i <= n; i++){
        for(int j = 0; j <= i - k; j++){
            double tb = (double)(S[i] - S[j]) / (i - j);
            best = max(best, tb);
        }
    }
    printf("%.5f", best);
    return 0;
}

import sys

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
S = [0] * (n + 1)
for i in range(1, n + 1):
    S[i] = S[i - 1] + int(data[i + 1])

best = -1e18
for i in range(k, n + 1):
    for j in range(0, i - k + 1):
        tb = (S[i] - S[j]) / (i - j)
        if tb > best:
            best = tb
print("%.5f" % best)

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

• Không gian: mảng cộng dồn $S$ có $n + 1$ phần tử ⇒ $O(n)$.
• Thời gian: số cặp $(j, i)$ cỡ $\dfrac{n^2}{2}$ ⇒ $O(n^2)$. Với $n \le 5000$ thì khoảng $1.25 \cdot 10^7$ phép tính, C++ chạy tức thì; nhưng với $n = 10^5$ thì lên tới $5 \cdot 10^9$ ⇒ TLE.

Không gian$O(n)$

Thời gian$O(n^2)$

Chỉ được 50% điểm

Cách này chỉ ăn được subtask $n \le 5000$. Bản Python của cách này còn chậm hơn nhiều (với $n = 5000$ mất khoảng 5 giây), anh em dùng Python thì nên đi thẳng tới cách 2.

Cách 2Chặt nhị phân đáp án – O(n · log)

Thay vì hỏi "trung bình lớn nhất là bao nhiêu?", ta đổi sang câu hỏi dễ hơn: "có đoạn nào (ít nhất $k$ phần tử) có trung bình cộng $\ge x$ hay không?"

Biến đổi trung bình thành tổng

Đoạn $a_{j+1}, \ldots, a_i$ (độ dài $L = i - j$) có trung bình $\ge x$ khi và chỉ khi:

Mẹo trừ x

$\dfrac{a_{j+1} + \ldots + a_i}{L} \ge x \iff (a_{j+1} - x) + (a_{j+2} - x) + \ldots + (a_i - x) \ge 0$
Tức là: trừ $x$ vào mọi phần tử, rồi hỏi có đoạn nào dài ít nhất $k$ mà tổng $\ge 0$ không.

Gọi $P_i = (a_1 - x) + \ldots + (a_i - x)$ là mảng cộng dồn của dãy đã trừ $x$. Đoạn kết thúc tại $i$ có tổng $P_i - P_j$ với $j \le i - k$. Muốn tổng này lớn nhất thì $P_j$ phải nhỏ nhất ⇒ ta chỉ cần giữ $mn = \min(P_0, P_1, \ldots, P_{i-k})$, cập nhật dần khi $i$ tăng. Một vòng lặp $O(n)$ là trả lời xong câu hỏi.

Vì sao chặt nhị phân được?

Nếu có đoạn trung bình $\ge x$ thì đoạn đó cũng có trung bình $\ge x'$ với mọi $x' \lt x$. Nghĩa là câu trả lời "có/không" theo $x$ có dạng: có, có, ..., có, không, không, ... ⇒ đúng điều kiện để chặt nhị phân. Đáp án luôn nằm giữa $\min(a)$ và $\max(a)$, nên ta khởi tạo $lo = \min(a)$ (chắc chắn "có"), $hi = \max(a)$ và chặt:

• $mid = \dfrac{lo + hi}{2}$; nếu check(mid) đúng thì đáp án $\ge mid$ ⇒ $lo = mid$;
• ngược lại đáp án $\lt mid$ ⇒ $hi = mid$;
• dừng khi $hi - lo \le 10^{-7}$ (đủ chính xác để làm tròn 5 chữ số thập phân), in $lo$.

Minh hoạ chặt nhị phân

Em nhập $k$ và dãy $a$ rồi bấm Tiếp. Mỗi bước là một lần thử $mid$: dòng $a - mid$ là dãy sau khi trừ, dòng $P$ là mảng cộng dồn, ô xanh là đoạn có tổng $\ge 0$ mà check tìm được (nếu có).

k dãy a

Ví dụ nhanh:

Quan sát

Với ví dụ đề, $lo$ tiến dần lên $3.66667$ còn $hi$ lùi dần xuống: mọi lần thử $mid \le \frac{11}{3}$ đều tìm được đoạn (thường là chính $[2, 4, 5]$), còn mọi lần $mid \gt \frac{11}{3}$ thì không. Khoảng $[lo, hi]$ co lại một nửa sau mỗi lần thử.

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 n, k;
double a[100005], P[100005];

bool check(double x){
    P[0] = 0;
    double mn = 1e18;
    for(int i = 1; i <= n; i++){
        P[i] = P[i - 1] + (a[i] - x);
        if(i >= k){
            mn = min(mn, P[i - k]);
            if(P[i] - mn >= 0) return true;
        }
    }
    return false;
}

int main(){
    cin >> n >> k;
    double lo = 1e9, hi = -1e9;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        lo = min(lo, a[i]);
        hi = max(hi, a[i]);
    }
    while(hi - lo > 1e-7){
        double mid = (lo + hi) / 2;
        if(check(mid)) lo = mid;
        else hi = mid;
    }
    if(fabs(lo) < 5e-6) lo = 0; // tránh in ra "-0.00000"
    printf("%.5f", lo);
    return 0;
}

import sys
from itertools import accumulate
from operator import sub

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [int(x) for x in data[2:2 + n]]


def check(x):
    # P[i] = tổng (a[j] - x) của i phần tử đầu
    P = list(accumulate((v - x for v in a), initial=0))
    # M[t] = min(P[0..t]) – tiền tố nhỏ nhất có thể "cắt bỏ"
    M = list(accumulate(P[:n - k + 1], min))
    # đoạn kết thúc tại i (i >= k): P[i] - min(P[0..i-k])
    return max(map(sub, P[k:], M)) >= 0


lo, hi = min(a), max(a)
while hi - lo > 1e-7:
    mid = (lo + hi) / 2
    if check(mid):
        lo = mid
    else:
        hi = mid
if abs(lo) < 5e-6:  # tránh in ra "-0.00000"
    lo = 0.0
print("%.5f" % lo)

Về bản Python

Bản Python dùng itertools.accumulate để tính mảng cộng dồn và min tiền tố, ý tưởng y hệt hàm check của C++ nhưng chạy nhanh hơn nhiều so với vòng for thuần (mỗi lần check đi qua $10^5$ phần tử, mà phải gọi vài chục lần).

C++▶ Chạy tay từng dòng codeCách 2: chặt nhị phân đáp án, check bằng mảng cộng dồn + min tiền tố.

Dữ liệu vào (stdin) – sửa thoải mái7 3 2 4 5 1 3 4 1

Dữ liệu mẫu:

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

2using namespace std;

3

4int n, k;

5double a[100005], P[100005];

6

7bool check(double x){

8 P[0] = 0;

9 double mn = 1e18;

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

11 P[i] = P[i - 1] + (a[i] - x);

12 if(i >= k){

13 mn = min(mn, P[i - k]);

14 if(P[i] - mn >= 0) return true;

15 }

16 }

17 return false;

18}

19

20int main(){

21 cin >> n >> k;

22 double lo = 1e9, hi = -1e9;

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

24 cin >> a[i];

25 lo = min(lo, a[i]);

26 hi = max(hi, a[i]);

27 }

28 while(hi - lo > 1e-7){

29 double mid = (lo + hi) / 2;

30 if(check(mid)) lo = mid;

31 else hi = mid;

32 }

33 if(fabs(lo) < 5e-6) lo = 0; // tránh in ra "-0.00000"

34 printf("%.5f", lo);

35 return 0;

36}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng $a$ và $P$ ⇒ $O(n)$.
• Thời gian: mỗi lần check là $O(n)$; số lần chặt là $\log_2 \dfrac{\max(a) - \min(a)}{10^{-7}} \le \log_2 \dfrac{2 \cdot 10^5}{10^{-7}} \approx 41$ lần ⇒ tổng cỡ $41 \cdot n \approx 4 \cdot 10^6$ phép tính, rất nhanh.

Không gian$O(n)$

Thời gian$O\left(n \log \dfrac{V}{\varepsilon}\right)$

Cẩn thận với số thực

• Đáp án là số thực nên không chặt nhị phân kiểu lo + 1 như số nguyên được, mà chặt tới khi $hi - lo$ đủ nhỏ ($10^{-7}$). Đừng để sai số quá lớn (như $10^{-3}$) vì sẽ làm tròn sai chữ số thứ 5.
• Khi đáp án đúng bằng $0$, $lo$ có thể là một số âm rất nhỏ như $-0.00000003$ và printf("%.5f") sẽ in ra -0.00000. Vì thế code có thêm dòng gán $lo = 0$ khi $|lo| \lt 5 \cdot 10^{-6}$ (đáp án khác 0 luôn có trị tuyệt đối $\ge 10^{-5}$ vì mẫu số $\le 10^5$, nên dòng này không làm sai trường hợp nào).

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 600 bộ test ngẫu nhiên nhỏ ($n \le 12$, có cả test toàn số âm, giá trị tới $10^5$), so với code vét cạn tính bằng phân số chính xác – cả 4 chương trình in ra giống hệt nhau và đúng đáp án. Với $n = 10^5$: cách 2 chạy khoảng 0.15 giây (C++) và khoảng 1.1 giây (Python); cách 1 (C++) với $n = 10^5, k = 5 \cdot 10^4$ đã mất khoảng 2 giây, $k$ nhỏ còn lâu hơn ⇒ TLE đúng như phân tích.

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 😇