Dãy Chẵn Lẻ (DAYSO)

Nguồn: Đề thi HSG Tin học (học viên gửi) Độ khó: Trung bình Mảng cộng dồn Map Mảng đánh dấu Chẵn lẻ

Đề bài

Bài 3: (7,0 điểm) DÃY CHẴN LẺ

Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò tìm số. Hai bạn lần lượt mỗi người viết một số nguyên dương lên bảng, Nam viết số thứ nhất, Bình viết số thứ hai, rồi đến lượt Nam viết số thứ ba,… Cứ tiếp tục như vậy hai bạn viết được một dãy gồm $n$ số $a_1, a_2, \ldots, a_n$. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẵn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho đoạn đó có nhiều số nhất và số lượng số chẵn trong đoạn bằng số lượng số lẻ trong đoạn đó.

Dữ liệu vào: Cho từ tệp văn bản có tên DAYSO.INP có dạng như sau:

• Dòng đầu tiên ghi số nguyên $n$ $(1 \le n \le 10^6)$.
• Dòng thứ hai ghi dãy $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 1000,\ i = 1..n)$.

Kết quả: Ghi ra tệp văn bản có tên DAYSO.OUT gồm một số nguyên duy nhất là số lượng số của dãy con tìm được.

Giới hạn:

• Có 60% số test tương ứng 60% số điểm có giá trị $1 \le n \le 10^2$.
• Có 20% số test tương ứng 20% số điểm có giá trị $10^2 \lt n \le 10^3$.
• Có 20% số test tương ứng 20% số điểm có giá trị $10^3 \lt n \le 10^6$.

Đề gốc đọc/ghi file DAYSO.INP / DAYSO.OUT; code bên dưới đọc/ghi chuẩn (bàn phím – màn hình), khi đi thi các bạn bỏ dấu // ở 2 dòng freopen là được. Đề không nói trường hợp không có đoạn nào thoả (ví dụ $n = 1$), code trong bài in ra 0.

DAYSO.INP

8
3 4 2 6 5 8 7 2

DAYSO.OUT

4

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải chi tiết để các bạn tham khảo nhen 😇.

Hồi đó mình giải cho em ấy theo 7 cách khác nhau, đi từ $O(N^3)$ tối ưu xuống $O(N^2)$, rồi xuống $O(N \log N)$ và cuối cùng là $O(N)$. Mình còn viết chương trình sinh test ngẫu nhiên để so đáp án của cả 7 cách với nhau, đảm bảo tính CHÍNH XÁC của thuật toán. Trong bài này mình chọn ra 3 cách tiêu biểu nhất để các bạn thấy rõ con đường tối ưu.

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ụ: dãy $3, 4, 2, 6, 5, 8, 7, 2$. Đoạn $6, 5, 8, 7$ (vị trí 4 → 7) có 2 số chẵn ($6, 8$) và 2 số lẻ ($5, 7$) ⇒ thoả, dài 4. Đoạn $5, 8, 7, 2$ cũng thoả và dài 4. Không có đoạn dài 6 hay 8 nào thoả (ví dụ $3, 4, 2, 6, 5, 8$ có tới 4 số chẵn, 2 số lẻ), nên đáp án là $4$. Để ý: đoạn thoả thì số chẵn = số lẻ nên độ dài luôn là số chẵn.

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

Cách 1Mảng cộng dồn, xét mọi đoạn · O(N²) · 80%Cách 2Biến đổi 2p[i] − i + map · O(N log N)Cách 3Mảng đánh dấu thay map · O(N)

Cách 1Mảng cộng dồn, xét mọi đoạn – O(N²)

Cách ngây thơ nhất là xét mọi đoạn $[L, R]$, rồi chạy thêm một vòng lặp đếm số chẵn, số lẻ trong đoạn ⇒ 3 vòng lặp lồng nhau, $O(N^3)$. Với $n \le 100$ (60% số test) thì vẫn chạy kịp.

Để bỏ bớt 1 vòng lặp, ta dùng mảng cộng dồn đếm số chẵn: gọi $p[i]$ là số lượng số chẵn từ $a_1$ đến $a_i$ (với $p[0] = 0$). Khi đó số lượng số chẵn trong đoạn $[L, R]$ là $p[R] - p[L-1]$, tính trong $O(1)$. Đoạn có $R - L + 1$ phần tử, thoả mãn khi số chẵn bằng đúng một nửa số phần tử:

Điều kiện đoạn [L, R] thoả mãn

$2 \cdot (p[R] - p[L-1]) = R - L + 1$

Thêm một mẹo nhỏ: độ dài đoạn thoả luôn chẵn, nên với mỗi $L$ ta cho $R$ chạy từ $L + 1$ và mỗi lần tăng 2 (j += 2), bỏ qua luôn các đoạn có độ dài lẻ, nhanh gấp đôi.

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

#include <iostream>
using namespace std;

int p[1000005]; // p[i] = số lượng số chẵn từ a[1] đến a[i]

int main(){
    // freopen("DAYSO.INP", "r", stdin);
    // freopen("DAYSO.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        p[i] = p[i - 1] + (x % 2 == 0);
    }
    int Max = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; j += 2){
            int even = p[j] - p[i - 1];
            if(even * 2 == j - i + 1){
                Max = max(Max, j - i + 1);
            }
        }
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)  # p[i] = số lượng số chẵn từ a[1] đến a[i]
for i in range(1, n + 1):
    p[i] = p[i - 1] + (int(data[i]) % 2 == 0)
Max = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1, 2):
        even = p[j] - p[i - 1]
        if even * 2 == j - i + 1:
            Max = max(Max, j - i + 1)
print(Max)

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

• Không gian: $O(N)$ cho mảng cộng dồn $p$.
• Thời gian: 2 vòng lặp lồng nhau, khoảng $\frac{N^2}{4}$ lần kiểm tra ⇒ $O(N^2)$.

Không gian$O(N)$

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

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

Với $n \le 10^3$ cách này chạy tức thì, ăn trọn 80% số điểm. Nhưng với $n = 10^6$ thì $\frac{N^2}{4} = 2{,}5 \cdot 10^{11}$ phép tính ⇒ chắc chắn TLE (mình đo thử với $n = 10^5$ code C++ đã mất khoảng 3 giây). Muốn lấy trọn điểm phải bỏ được thêm 1 vòng lặp nữa.

Cách 2Biến đổi 2p[i] − i, tìm bằng map – O(N log N)

Mấu chốt nằm ở việc biến đổi điều kiện ở cách 1 cho hai vế tách bạch $L$ và $R$. Ta có:

Biến đổi

$\dfrac{R - (L-1)}{2} = p[R] - p[L-1]$
$\Leftrightarrow R - (L-1) = 2p[R] - 2p[L-1]$
$\Leftrightarrow 2p[R] - R = 2p[L-1] - (L-1)$ (chuyển vế đổi dấu)

Vậy đặt $key(i) = 2p[i] - i$, đoạn $[L, R]$ thoả mãn khi và chỉ khi $key(R) = key(L-1)$. Nếu $R - (L-1)$ ra số lẻ thì hai vế không thể bằng nhau, nên không lo bị đếm nhầm đoạn độ dài lẻ.

Ý nghĩa của 2p[i] − i

$p[i]$ là số chẵn, $i - p[i]$ là số lẻ trong $i$ phần tử đầu, nên $2p[i] - i = p[i] - (i - p[i])$ = (số chẵn) − (số lẻ) tính từ đầu dãy đến $i$. Hai vị trí có cùng "độ chênh" này thì đoạn kẹp giữa chúng có số chẵn bằng số lẻ – nghe rất tự nhiên đúng không nào 😄.

Bài toán trở thành: với mỗi $L$, tìm vị trí $R$ lớn nhất có $key(R) = key(L-1)$, độ dài đoạn là $R - L + 1$. Cách làm của mình:

1. Duyệt $i$ từ $1$ đến $n$, tính $key = 2p[i] - i$ và lưu vào map: mp[key] = i. Key chính là giá trị $2p[i] - i$, còn value là vị trí $i$. Do $i$ chạy từ nhỏ đến lớn, gặp key trùng thì ghi đè $i$ mới vào ⇒ cuối cùng mỗi key lưu đúng vị trí lớn nhất có key đó.
2. Duyệt lại $i$ (đóng vai trò $L$) từ $1$ đến $n$: tính $2p[i-1] - (i-1)$, tìm trong map ra value $j$ – chính là $R$ xa nhất. Độ dài đoạn là $j - (i-1) = j - i + 1$, so với Max và cập nhật.

Lấy luôn ví dụ của đề $3, 4, 2, 6, 5, 8, 7, 2$: ta có $key(3) = 2 \cdot 2 - 3 = 1$, $key(5) = 2 \cdot 3 - 5 = 1$, $key(7) = 2 \cdot 4 - 7 = 1$. Khi lưu, mp[1] lần lượt được ghi $3$, rồi ghi đè thành $5$, rồi thành $7$ ⇒ cuối cùng mp[1] = 7, đúng là vị trí lớn nhất. Sau đó xét $L = 4$: tính $key(L-1) = key(3) = 1$, tra map ra $R = 7$ ⇒ đoạn $[4, 7] = 6, 5, 8, 7$ dài $7 - 4 + 1 = 4$ – chính là đáp án. Các bạn xem từng bước trong khung minh hoạ bên dưới nhé.

Minh hoạ: bảng key và tra cứu vị trí xa nhất

Em nhập dãy số rồi bấm Tiếp: giai đoạn 1 tính $p[i]$, $key(i) = 2p[i] - i$ và lưu vị trí lớn nhất của mỗi key; giai đoạn 2 với mỗi $L$ tra $key(L-1)$ ra $R$ xa nhất.

Dãy a

Ví dụ nhanh:

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

#include <iostream>
#include <map>
using namespace std;

int p[1000005]; // p[i] = số lượng số chẵn từ a[1] đến a[i]

int main(){
    // freopen("DAYSO.INP", "r", stdin);
    // freopen("DAYSO.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        p[i] = p[i - 1] + (x % 2 == 0);
    }
    map<int, int> mp; // key = 2p[i] - i, value = vị trí i lớn nhất
    for(int i = 1; i <= n; ++i){
        mp[2 * p[i] - i] = i;
    }
    int Max = 0;
    for(int i = 1; i <= n; ++i){
        map<int, int>::iterator it = mp.find(2 * p[i - 1] - (i - 1));
        if(it != mp.end()){
            Max = max(Max, it->second - i + 1);
        }
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)  # p[i] = số lượng số chẵn từ a[1] đến a[i]
for i in range(1, n + 1):
    p[i] = p[i - 1] + (int(data[i]) % 2 == 0)
mp = {}  # key = 2p[i] - i, value = vị trí i lớn nhất
for i in range(1, n + 1):
    mp[2 * p[i] - i] = i
Max = 0
for i in range(1, n + 1):
    key = 2 * p[i - 1] - (i - 1)
    if key in mp:
        Max = max(Max, mp[key] - i + 1)
print(Max)

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

• Không gian: $O(N)$ cho mảng $p$ và map (tối đa $N$ key).
• Thời gian: 2 vòng lặp rời nhau, mỗi vòng $N$ lần, mỗi lần thao tác trên map mất $O(\log N)$ (map cài đặt theo cơ chế cây) ⇒ $O(N \log N)$.

Không gian$O(N)$

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

Bản Python

Python không có map dạng cây sẵn nên mình dùng dict (bảng băm) – tra cứu trung bình $O(1)$, nên bản Python của cách 2 thực chất đã là $O(N)$.

Cách 3Mảng đánh dấu thay cho map – O(N)

Cách 2 tốn $O(\log N)$ cho mỗi lần tra map. Mình thay map bằng mảng đánh dấu để tra trong $O(1)$. Để ý $0 \le p[i] \le i$ nên:

• $2p[i] - i$ cao lắm là $i \le 10^6$ (khi $p[i] = i$, toàn số chẵn);
• nhưng cẩn thận nó có thể âm, thấp nhất là $-10^6$ (khi $p[i] = 0$, $i = 10^6$).

Vậy mình tạo mảng đánh dấu b hơn 2 triệu phần tử, mỗi lần tính $2p[i] - i$ thì cộng thêm 1 triệu (OFFSET) để chỉ số không bị âm: b[2 * p[i] - i + OFFSET] = i. Phần còn lại y hệt cách 2. Key nào chưa từng xuất hiện thì b bằng 0 (mảng toàn cục), khi đó $0 - i + 1 \le 0$ nên không ảnh hưởng gì tới Max.

Vì sao b luôn trả về R xa nhất?

Vòng lặp lưu chạy $i$ từ nhỏ đến lớn, key trùng thì cứ ghi đè $i$ mới vào ⇒ $i$ sau cùng của mỗi key là lớn nhất. Và với mỗi $L$ chỉ cần đúng một $R$ – cái xa nhất – vì ta đang tìm đoạn dài nhất.

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

#include <iostream>
using namespace std;

const int OFFSET = 1000000;
int p[1000005];     // p[i] = số lượng số chẵn từ a[1] đến a[i]
int b[2000005];     // b[key + OFFSET] = vị trí i lớn nhất có 2p[i] - i = key

int main(){
    // freopen("DAYSO.INP", "r", stdin);
    // freopen("DAYSO.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> x;
        p[i] = p[i - 1] + (x % 2 == 0);
    }
    for(int i = 1; i <= n; ++i){
        b[2 * p[i] - i + OFFSET] = i;
    }
    int Max = 0;
    for(int i = 1; i <= n; ++i){
        int j = b[2 * p[i - 1] - (i - 1) + OFFSET];
        Max = max(Max, j - i + 1);
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)  # p[i] = số lượng số chẵn từ a[1] đến a[i]
for i in range(1, n + 1):
    p[i] = p[i - 1] + (int(data[i]) % 2 == 0)
OFFSET = n
b = [0] * (2 * n + 1)  # b[key + OFFSET] = vị trí i lớn nhất có 2p[i] - i = key
for i in range(1, n + 1):
    b[2 * p[i] - i + OFFSET] = i
Max = 0
for i in range(1, n + 1):
    j = b[2 * p[i - 1] - (i - 1) + OFFSET]
    Max = max(Max, j - i + 1)
print(Max)

C++▶ Chạy tay từng dòng codeCách 3: tính p[i], lưu b[2p[i] − i + OFFSET] = i, rồi với mỗi L tra ra R xa nhất.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4const int OFFSET = 1000000;

5int p[1000005]; // p[i] = số lượng số chẵn từ a[1] đến a[i]

6int b[2000005]; // b[key + OFFSET] = vị trí i lớn nhất có 2p[i] - i = key

7

8int main(){

9 // freopen("DAYSO.INP", "r", stdin);

10 // freopen("DAYSO.OUT", "w", stdout);

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13 int n, x;

14 cin >> n;

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

16 cin >> x;

17 p[i] = p[i - 1] + (x % 2 == 0);

18 }

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

20 b[2 * p[i] - i + OFFSET] = i;

21 }

22 int Max = 0;

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

24 int j = b[2 * p[i - 1] - (i - 1) + OFFSET];

25 Max = max(Max, j - i + 1);

26 }

27 cout << Max;

28 return 0;

29}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng $p$ cỡ $10^6$ và mảng đánh dấu $b$ cỡ $2 \cdot 10^6$ phần tử kiểu int – khoảng 12 MB, thoải mái.
• Thời gian: 3 vòng lặp rời nhau, mỗi vòng $N$ lần, mỗi lần $O(1)$ ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Đi nộp bài thì không cần lưu mảng a

Trong code mình đọc từng số vào biến x rồi cộng dồn thẳng vào p, không cần lưu cả mảng $a$. Bản Python thì mình đặt OFFSET = n và tạo mảng $2n + 1$ phần tử cho đỡ tốn bộ nhớ, vì $|2p[i] - i| \le i \le n$.

Ghi chú của mình: code C++ và Python của cả 3 cách đã được kiểm tra với 400 bộ test ngẫu nhiên ($n \le 30$), so với code vét cạn đếm chẵn/lẻ từng đoạn – khớp hết. Với $n = 10^6$: cách 3 (C++) chạy khoảng 0.15 giây, cách 2 (C++) khoảng 0.25–0.5 giây, bản Python của cách 2 và cách 3 khoảng 1.5–1.8 giây; còn cách 1 (C++) với $n = 10^5$ đã mất khoảng 3 giây ⇒ chỉ dùng được cho 80% số test đầu đú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 😇