Tổng Các Số Chẵn Liên Tiếp Lớn Nhất (TONGCHAN)

Nguồn: Đề thi HSG Tin học (bài 2 – 6 điểm) Độ khó: Dễ Mảng Chẵn lẻ Duyệt mảng

Đề bài

Bài 2. (6 điểm) Tổng các số chẵn liên tiếp lớn nhất – TONGCHAN

Cho một dãy $n$ số nguyên.

Yêu cầu: Tìm dãy con liên tiếp các số chẵn có tổng lớn nhất. Dãy con tìm được phải có ít nhất 02 phần tử trở lên.

Input: Gồm hai dòng:

• Dòng đầu ghi một số nguyên dương $n$ $(2 \le n \le 10^6)$ là số lượng phần tử trong dãy;
• Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^6)$ là giá trị từng phần tử trong dãy.

Output: Dãy con tìm được. Nếu có nhiều dãy con tìm được thì chỉ xuất dãy con đầu tiên. Nếu không tìm được dãy con nào thì xuất số $-1$.

Tên file: TONGCHAN.INP / TONGCHAN.OUT (khi chạy thử / chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình như bình thường nhé).

Ví dụ – TONGCHAN.INP

10
3 2 2 4 5 6 8 3 8 4

Ví dụ – TONGCHAN.OUT

6 8

Giải thích (của đề): Có 3 dãy con chứa liên tiếp các số chẵn là: (2 2 4), (6 8) và (8 4). Trong đó, dãy (6 8) có tổng lớn nhất là 14.

Lời mở đầu

Trong quá trình đi comment dạo mình thấy bài tập này cũng hay nên chia sẻ đề lên đây để anh em cùng xem và thử sức nhé. Bạn đăng bài hỏi "thuật toán tối ưu" của bài này – thì cách tối ưu là chỉ cần duyệt qua danh sách các số 1 lần là ra đáp án, độ phức tạp $O(N)$ với $N$ là độ dài của dãy số. Đặc biệt trong bài này mình sẽ chỉ anh em một mẹo nhỏ để code gọn hơn hẳn và không lo bị văng lỗi truy cập ngoài mảng 😉.

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

Hiểu đề qua ví dụ: dãy 3 2 2 4 5 6 8 3 8 4 bị các số lẻ (3, 5, 3) "cắt" thành các khúc toàn số chẵn: (2 2 4) tổng 8, (6 8) tổng 14, (8 4) tổng 12. Như phần giải thích của đề, mỗi khúc chẵn được xét trọn vẹn (từ ngay sau một số lẻ đến ngay trước số lẻ tiếp theo), khúc nào có từ 2 phần tử trở lên và tổng lớn nhất thì in ra – ở đây là 6 8. Nếu không có khúc chẵn nào dài từ 2 trở lên (ví dụ 1 2 3 4) thì in $-1$.

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

Cách 1Duyệt 1 lần: nhận biết đầu – cuối mỗi khúc chẵn, thêm 2 "lính canh" lẻ ở hai đầu mảng – O(N)

Cách 1Duyệt một lần, nhận biết đầu – cuối khúc chẵn – O(N)

Đầu tiên tạo ra 2 biến startMax, endMax mục đích lưu trữ vị trí bắt đầu và vị trí kết thúc của dãy số chẵn liên tiếp có tổng lớn nhất. Ban đầu khởi tạo giá trị 2 biến này là $-1$.

Tư tưởng giải quyết là ta phải nhìn ra được mấu chốt: khi xét phần tử $a[i]$ hiện tại, nếu nó là số chẵn thì:

• Ta phải biết xem liệu nó có là khởi đầu của dãy số chẵn liên tiếp không? Để biết được thì chỉ đơn giản: nếu số liền trước nó $a[i - 1]$ là số lẻ thì chính nó hiện tại là mở đầu của dãy chẵn ⇒ lưu lại vị trí của nó vào biến start.
• Cứ với mỗi giá trị $a[i]$ là chẵn thì ta cộng giá trị của nó vào biến tổng sum.
• Tương tự, nếu đằng sau nó $a[i + 1]$ là số lẻ thì $a[i]$ hiện tại chính là số chẵn cuối cùng của dãy liên tiếp. Có được vị trí mở đầu, vị trí kết thúc ta tính ra được độ dài của dãy bằng công thức: cuối - đầu + 1. Nếu độ dài thỏa mãn $\ge 2$ theo như đề bài yêu cầu thì ta so sánh biến tổng với giá trị Max, nếu lớn hơn Max thì cập nhật lại, đồng thời cập nhật startMax, endMax lưu lại vị trí đầu, cuối của dãy thỏa mãn.
• Khi đã tìm được vị trí kết thúc của dãy thì nhớ reset lại biến tổng = 0 để các lần tiếp theo gặp dãy thỏa mãn thì quy trình lặp lại.

Cứ như thế đến sau cùng ta kiểm tra: nếu startMax vẫn mang giá trị $-1$ như ban đầu thì kết luận không tìm được dãy nào thỏa mãn; nếu khác $-1$ thì in ra các phần tử của dãy từ vị trí startMax đến endMax, đó chính là đáp án.

Lấy dãy đầu tiên: so sánh > chứ không phải >=

Vì đề nói nếu có nhiều dãy có tổng bằng nhau thì chỉ lấy kết quả đầu tiên, nên chỗ này ta chỉ cập nhật khi sum > Max. Còn nếu đề yêu cầu lấy kết quả cuối cùng thì lúc đó ta mới so sánh sum >= Max (lấy luôn trường hợp bằng để đảm bảo nó là kết quả sau cùng).

Giá trị khởi tạo của Max

Biến Max ta khởi tạo với giá trị nhỏ nhất có thể để đảm bảo lần so sánh đầu tiên luôn thỏa lớn hơn nó để mà cập nhật lại. Đề có tối đa $10^6$ phần tử, mỗi phần tử nhỏ nhất là $-10^6$, nên nếu cả dãy đều là $-10^6$ thì tổng sẽ là $-10^{12}$. Vì thế ta khởi tạo Max $= -10^{13}$ để dù tình huống đó có xảy ra thì biến tổng vẫn lớn hơn Max. Và tất nhiên sum, Max phải là long long vì tổng có thể tới $10^{12}$ – int là tràn ngay.

Mẹo "lính canh": mảng n + 2 phần tử

Khi xét $a[i]$ là số chẵn thì phải xét $a[i - 1]$ và $a[i + 1]$. Phải lưu ý nếu $i$ đang là 0 thì gọi $a[i - 1]$ tức là gọi $a[-1]$ thì sẽ bị văng lỗi ngay nhé (index tối thiểu từ 0 chứ không có chuyện âm); tương tự nếu $i$ đang là $n - 1$ thì gọi $a[i + 1]$ tức là gọi $a[n]$ cũng sẽ bị lỗi (mảng $n$ phần tử thì index hợp lệ chỉ là từ 0 đến $n - 1$). Vậy nên cần xét riêng 2 tình huống $i = 0$ và $i = n - 1$ – chỗ này nếu không biết xử lý khéo thì sẽ phải code dài thêm.

Tư tưởng đơn giản hoá vấn đề

Ta chủ động tạo ra mảng có $n + 2$ phần tử, với phần tử đầu (index 0) và cuối (index $n + 1$) là phần tử bất kỳ miễn là phải mang giá trị lẻ (ví dụ 1 chẳng hạn), rồi các phần tử của dãy đọc vào các vị trí từ 1 đến $n$, và làm đúng theo quy tắc ở trên. Nhờ như thế mà nó tự thỏa mãn, không bị rơi vào những tình huống đặc biệt để bị văng lỗi bộ nhớ, và ta cũng không phải mất công xét riêng các trường hợp đó. Hai số lẻ này giống như hai "lính canh" đứng ở hai đầu: khúc chẵn nào chạm đầu/cuối mảng cũng tự nhiên được "cắt" đúng chỗ.

Minh hoạ duyệt mảng

Các bạn nhập dãy rồi bấm Tiếp để xem từng bước (ô viền nét đứt: lính canh; vàng: khúc chẵn đang cộng dồn; xanh: khúc tốt nhất hiện tại):

Dãy a (2..14 số)

Ví dụ nhanh:

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

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int *a = new int[n + 2];
    a[0] = a[n + 1] = 1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    long long Max = -10000000000000;
    int start = -1;
    int startMax = -1, endMax = -1;
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] % 2 == 0) {
            sum += a[i];
            if (a[i - 1] % 2 != 0) {
                start = i;
            }
            if (a[i + 1] % 2 != 0) {
                int cnt = i - start + 1;
                if (cnt >= 2) {
                    if (sum > Max) {
                        Max = sum;
                        startMax = start;
                        endMax = i;
                    }
                }
                sum = 0;
            }
        }
    }
    if (startMax == -1) {
        cout << -1;
    }
    else {
        for (int i = startMax; i <= endMax; ++i) {
            cout << a[i] << " ";
        }
    }
    delete[] a;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [1] + [int(x) for x in data[1:n + 1]] + [1]
Max = -10 ** 13
start = -1
startMax = endMax = -1
s = 0
for i in range(1, n + 1):
    if a[i] % 2 == 0:
        s += a[i]
        if a[i - 1] % 2 != 0:
            start = i
        if a[i + 1] % 2 != 0:
            cnt = i - start + 1
            if cnt >= 2 and s > Max:
                Max = s
                startMax = start
                endMax = i
            s = 0
if startMax == -1:
    print(-1)
else:
    print(' '.join(map(str, a[startMax:endMax + 1])))

Mấy chỗ mình chỉnh khi đưa code lên blog

Code gốc mình soạn trên điện thoại nên dấu nháy kép ở dòng in kết quả là nháy "cong" của điện thoại, copy y nguyên sẽ không chạy – ở đây mình đã sửa lại thành " " chuẩn. Mình thêm 2 dòng ios::sync_with_stdio(false); cin.tie(0); cho đọc $10^6$ số nhanh hơn, còn lại logic giữ nguyên. Bản Python đọc toàn bộ input một lần bằng sys.stdin.buffer cho nhanh.

Khung chạy tay (để dễ theo dõi, giới hạn $n \le 15$):

C++▶ Chạy tay từng dòng codeDuyệt i = 1..n một lần; a[0], a[n+1] là lính canh lẻ; khúc chẵn kết thúc thì so tổng với Max.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false);

5 cin.tie(0);

6 int n;

7 cin >> n;

8 int *a = new int[n + 2];

9 a[0] = a[n + 1] = 1;

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

11 cin >> a[i];

12 }

13 long long Max = -10000000000000;

14 int start = -1;

15 int startMax = -1, endMax = -1;

16 long long sum = 0;

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

18 if (a[i] % 2 == 0) {

19 sum += a[i];

20 if (a[i - 1] % 2 != 0) {

21 start = i;

22 }

23 if (a[i + 1] % 2 != 0) {

24 int cnt = i - start + 1;

25 if (cnt >= 2) {

26 if (sum > Max) {

27 Max = sum;

28 startMax = start;

29 endMax = i;

30 }

31 }

32 sum = 0;

33 }

34 }

35 }

36 if (startMax == -1) {

37 cout << -1;

38 }

39 else {

40 for (int i = startMax; i <= endMax; ++i) {

41 cout << a[i] << " ";

42 }

43 }

44 delete[] a;

45 return 0;

46}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng $n + 2$ phần tử – $O(N)$ (cần lưu lại để cuối cùng in khúc tốt nhất).
• Thời gian: đọc mảng 1 lần, duyệt 1 lần, in 1 lần ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Về số âm

Trong C++ và Python, số chẵn âm vẫn có a % 2 == 0, còn số lẻ âm thì a % 2 là $-1$ (C++) hoặc $1$ (Python) – đều khác 0. Vì vậy mình viết điều kiện "lẻ" là % 2 != 0 chứ không phải % 2 == 1, để số lẻ âm như $-3$ vẫn được nhận đúng là số lẻ.

Ghi chú của mình: code C++ và Python ở trên đã được kiểm tra với 500 bộ test ngẫu nhiên nhỏ (có cả số âm, có trường hợp tổng bằng nhau), so với code vét cạn liệt kê mọi khúc chẵn trọn vẹn – khớp hết; test của đề ra đúng 6 8. Với $n = 10^6$, bản C++ chạy khoảng 0.2 giây, bản Python khoảng 1.2 – 2 giây. Lời giải hiểu "dãy con liên tiếp các số chẵn" là cả khúc chẵn nằm giữa hai số lẻ, đúng như phần giải thích ví dụ của đề.

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 😇