Chia Đoạn (SEG)

Nguồn: NTUCoder Độ khó: Trung bình Mảng cộng dồn Tìm kiếm nhị phân Vét cạn Nhận xét

Đề bài

SEG – Chia đoạn · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte

Cho một băng số gồm $n$ số nguyên dương $a_1, a_2, \ldots, a_n$, mỗi số được viết trên một ô. Hãy cắt băng số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau.

Dữ liệu vào:

• Dòng đầu ghi $n$ $(n \le 1000)$.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ ghi một số nguyên dương $a_i$ $(1 \le a_i \le 1000)$.

Dữ liệu ra: Là số lượng đoạn nhiều nhất chia được.

Ví dụ – input

8
10
2
6
2
5
2
1
2

Ví dụ – output

3

Giải thích: Đoạn 1: $10$. Đoạn 2: $2 + 6 + 2 = 10$. Đoạn 3: $5 + 2 + 1 + 2 = 10$.

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 😇.

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

Nhắc lại ngưỡng quen thuộc: với giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++) là an toàn, $10^8$ thì hên xui. Đề này cho đúng 1 giây nên cứ canh theo ngưỡng đó. Và có 2 kinh nghiệm mình muốn chia sẻ với các bạn:

1. Có ý tưởng rồi thì khoan hãy cài đặt, hãy đánh giá độ phức tạp trước: tổng số lần lặp có vượt ngưỡng không? Ổn thì mới cài, không ổn thì đừng mất công (trừ khi không nghĩ ra cách nào tốt hơn và đành vét điểm test nhỏ).
2. Đứng trước mọi bài, đầu tiên hãy nhìn theo cách cơ bản nhất (vét cạn, duyệt trâu). Nhẩm độ phức tạp, nếu AC được thì cài luôn cho nhanh gọn – trong phòng thi giải càng nhanh càng lợi thế, tội gì nặng đầu nghĩ cách tối ưu mà lỡ cài sai thì toang. Còn khi không bị áp lực thời gian thì nghĩ thêm cách tối ưu là điều tốt để rèn tư duy.

Giải thích ví dụ: băng số $10, 2, 6, 2, 5, 2, 1, 2$ có tổng 30. Cắt thành 3 đoạn $[10]$, $[2, 6, 2]$, $[5, 2, 1, 2]$ thì đoạn nào cũng có tổng 10. Không cắt được nhiều hơn: ví dụ muốn 5 đoạn thì mỗi đoạn tổng 6 nhưng ô đầu tiên đã là 10 rồi. Lưu ý các đoạn phải liên tiếp và phủ kín cả băng số. Băng số nào cũng có ít nhất 1 cách là để nguyên cả băng (1 đoạn).

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

Cách 1Thử từng tổng đoạn đầu, cắt tuần tự – O(N²)Cách 2Cải tiến: dừng sớm 2 chỗCách 3Mảng cộng dồn + tìm kiếm nhị phân

Cách 1Thử từng tổng của đoạn đầu tiên – O(N²)

Nếu là mình đang trong phòng thi thì mình sẽ làm theo cách cơ bản nhất như sau. Đề không cho trước tổng mỗi đoạn là bao nhiêu, nhưng đoạn đầu tiên luôn bắt đầu từ ô đầu tiên, nên tổng mỗi đoạn chỉ có thể là tổng của 1, 2, 3, …, $n$ phần tử đầu tiên. Ta thử lần lượt từng giá trị đó làm sum, rồi xem phần còn lại của dãy có gom hết được thành các đoạn liên tiếp có tổng bằng sum không. Nếu được thì đếm số đoạn (tính luôn đoạn đầu) và so sánh với Max.

Kiểm tra phần còn lại

Tạo biến s = 0 rồi cộng dồn lần lượt các phần tử phía sau:

• s < sum: chưa đủ, cộng tiếp phần tử kế.
• s == sum: cắt được 1 đoạn ⇒ tăng biến đếm, reset s = 0, xét tiếp.
• s > sum: vượt rồi ⇒ dừng, không thể cắt với tổng này.

Chỉ khi tất cả phần tử còn lại đều được gom đúng vào các đoạn (kết thúc mà s == 0) thì mới cập nhật Max. Nếu có một đoạn cuối không đủ tổng thì các đoạn cắt trước đó coi như vô nghĩa.

Chạy tay với ví dụ của đề, $a = \{10, 2, 6, 2, 5, 2, 1, 2\}$ (đánh số từ 0):

• Đoạn đầu là $a[0]$, sum = 10, cnt = 1. Từ $a[1]$: $s = 2$, rồi $s = 8$, rồi $s = 10 = sum$ ⇒ cắt, cnt = 2, reset $s = 0$. Tiếp $s = 5, 7, 8, 10$ ⇒ cắt, cnt = 3. Hết phần tử, $s = 0$ ⇒ Max = 3.
• Đoạn đầu là $a[0..1]$, sum = 12: $a[2] + a[3] = 8 \lt 12$, cộng thêm $a[4]$ thành $13 \gt 12$ ⇒ không cắt được.
• Đoạn đầu là $a[0..2]$, sum = 18: tổng toàn bộ phần còn lại chỉ là $12 \lt 18$ ⇒ không cắt được. Đoạn đầu càng dài thì sum càng lớn, phần còn lại càng nhỏ, nên từ đây không còn cách nào nữa (trừ để nguyên cả băng).

Vậy đáp án là 3. Các bạn nhập dãy vào khung dưới và bấm Tiếp để xem từng bước cắt nhé (mỗi đoạn đã cắt được tô một màu, ô cam là đoạn đang gom dở, ô đỏ là chỗ bị vượt tổng):

Dãy a (tối đa 14 số)

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(){
    int n, sum = 0, Max = -1;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        sum += a[i];
        int s = 0, cnt = 1;
        for(int j = i + 1; j < n; ++j){
            s += a[j];
            if(s > sum){
                break;
            }
            else if(s == sum){
                cnt++;
                s = 0;
            }
        }
        if(s == 0){
            Max = max(Max, cnt);
        }
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1:1 + n]]
total, Max = 0, -1
for i in range(n):
    total += a[i]
    s, cnt = 0, 1
    for j in range(i + 1, n):
        s += a[j]
        if s > total:
            break
        elif s == total:
            cnt += 1
            s = 0
    if s == 0:
        Max = max(Max, cnt)
print(Max)

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

1. Trong vòng for j, nếu s > sum thì break: đó là dấu hiệu không thể chia phần còn lại thành các đoạn có tổng sum, khỏi xét tiếp.
2. Sau vòng for j (vẫn trong for i), chỉ cập nhật Max khi s == 0: nghĩa là đã duyệt tới phần tử cuối cùng và đoạn cuối cũng vừa đủ tổng nên s được reset về 0. Nếu s != 0 thì đoạn cuối không bằng sum, các đoạn cắt trước đó cũng vô nghĩa.

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

• Không gian: $O(N)$ cho mảng $a$.
• Thời gian: hai vòng lặp lồng nhau ⇒ $O(N^2)$. Với $N \le 10^3$ thì chỉ khoảng $10^6$ lần lặp, an toàn, không sợ TLE.

Không gian$O(N)$

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

Cách 2Cải tiến: dừng sớm ở 2 chỗ – vẫn O(N²) nhưng nhanh hơn

Nếu đang trong phòng thi thì mình chỉ code Cách 1 thôi, còn khi có thêm thời gian thì nhìn ra thêm 2 chỗ có thể kết thúc sớm:

Dừng sớm thứ 1: phần còn lại không đủ

Nhìn lại khúc cuối của phần chạy tay: khi tổng đoạn đầu đã lớn hơn toàn bộ phần còn lại thì càng nạp thêm phần tử vào đoạn đầu, đoạn đầu càng lớn, phần còn lại càng nhỏ ⇒ không bao giờ chia được nữa. Trong code, sau vòng for j mà cnt == 1 && s < sum (chưa cắt được đoạn nào và s lúc này chính là tổng của cả phần còn lại) thì break luôn vòng for i.

Dừng sớm thứ 2: cách chia đầu tiên tìm được chính là đáp án

Nếu với tổng $k$ phần tử đầu, phần còn lại chia được thành các đoạn tổng bằng nhau thì đó là đáp án luôn. Vì nếu thử đoạn đầu $k + 1$ phần tử thì sum lớn hơn, các đoạn còn lại phải nạp thêm phần tử để đủ tổng, nên số đoạn chỉ có thể giảm. Ví dụ $a = \{2, 2, 2, 2\}$: đoạn đầu 1 phần tử ⇒ $|2|2|2|2|$ được 4 đoạn; đoạn đầu 2 phần tử ⇒ $|2, 2|2, 2|$ chỉ còn 2 đoạn. Vậy chỉ cần thêm break ngay sau chỗ cập nhật Max.

Một chỗ cần sửa trong code gốc

Khi dùng "dừng sớm thứ 1" mà ngay lần thử đầu tiên đã phải dừng (ví dụ $a = \{6, 1, 1\}$: đoạn đầu $6$ lớn hơn phần còn lại $1 + 1 = 2$), code sẽ thoát vòng lặp trước khi kịp thử trường hợp để nguyên cả băng, và nếu khởi tạo Max = -1 như bản gốc thì sẽ in ra $-1$, trong khi đáp án đúng là 1. Cách sửa đơn giản: khởi tạo Max = 1 (cả băng luôn là 1 đoạn hợp lệ). Code dưới đây đã sửa chỗ này.

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, sum = 0, Max = 1;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i){
        sum += a[i];
        int s = 0, cnt = 1;
        for(int j = i + 1; j < n; ++j){
            s += a[j];
            if(s > sum){
                break;
            }
            else if(s == sum){
                cnt++;
                s = 0;
            }
        }
        if(s == 0){
            Max = max(Max, cnt);
            break;
        }
        else if(cnt == 1 && s < sum){
            break;
        }
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.read().split()
n = int(data[0])
a = [int(x) for x in data[1:1 + n]]
total, Max = 0, 1
for i in range(n):
    total += a[i]
    s, cnt = 0, 1
    for j in range(i + 1, n):
        s += a[j]
        if s > total:
            break
        elif s == total:
            cnt += 1
            s = 0
    if s == 0:
        Max = max(Max, cnt)
        break
    elif cnt == 1 and s < total:
        break
print(Max)

Đánh giá độ phức tạp: chạy nhanh hơn nhiều trong thực tế, nhưng trường hợp xấu nhất vẫn là $O(N^2)$ thời gian, $O(N)$ không gian.

Không gian$O(N)$

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

Cách 3Mảng cộng dồn + tìm kiếm nhị phân – O(N log² N)

Giả sử $N$ lên đến $10^6$ thì các cách trên đều TLE hết. Muốn tối ưu hơn thì phải nhìn ra cái dở của cách hiện tại: với phần còn lại, ta cứ phải đi tuần tự (vòng for j) cộng dồn rồi so sánh. Có cách gì tốt hơn không?

Sẽ tốt hơn nếu ngay từ đầu ta lưu mảng $a$ là mảng cộng dồn: $a[i]$ là tổng các phần tử từ đầu đến chính vị trí $i$. Với ví dụ của đề:

i	0	1	2	3	4	5	6	7
giá trị	10	2	6	2	5	2	1	2
cộng dồn a[i]	10	12	18	20	25	27	28	30

Vì các phần tử đều dương nên mảng cộng dồn tăng dần – à há, các bạn nhìn ra rồi chứ? Ta có thể tìm kiếm nhị phân thay cho tìm kiếm tuyến tính! Chia được thành các đoạn tổng $a[i]$ nghĩa là các giá trị $2a[i], 3a[i], \ldots$ phải lần lượt xuất hiện trong mảng cộng dồn, và giá trị cuối cùng tìm thấy phải nằm ở phần tử cuối mảng.

Quy trình với mỗi i

Khởi tạo cnt = 1, x = 2 * a[i]. Tìm nhị phân $x$ trong phần mảng phía sau vị trí vừa tìm được. Thấy thì cnt++, x += a[i] rồi tìm tiếp; không thấy thì cách chia này hỏng. Tìm được tới phần tử cuối mảng thì đó là đáp án (theo nhận xét "dừng sớm thứ 2" ở trên).

Với ví dụ: $i = 0$, $a[0] = 10$, tìm $x = 20$ từ vị trí 1 ⇒ thấy ở $j = 3$, cnt = 2, $x = 30$. Tìm $30$ từ vị trí 4 ⇒ thấy ở $j = 7$ là phần tử cuối, cnt = 3. Kết luận đáp án 3.

Vì $a_i \ge 1$ nên mảng cộng dồn tăng ngặt, không có 2 giá trị trùng nhau, cứ yên tâm tìm nhị phân. Hàm binary_search có sẵn của STL chỉ cho biết có tồn tại hay không chứ không trả về vị trí, nên ta dùng lower_bound: trả về vị trí phần tử đầu tiên $\ge x$. Nếu vị trí đó có giá trị $== x$ thì tìm thấy, còn $\gt x$ (hoặc vị trí $== n$) thì không tồn tại $x$. Bạn nào chưa biết lower_bound thì nên tìm hiểu thêm nhé, nó rất hữu ích.

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;
    int a[n], sum = 0, x, Max = -1;
    for(int i = 0; i < n; ++i){
        cin >> x;
        sum += x;
        a[i] = sum;
    }
    for(int i = 0; i < n; ++i){
        int cnt = 1, j = i, check = 1;
        x = 2 * a[i];
        while(j + 1 < n){
            j = lower_bound(a + j + 1, a + n, x) - a;
            if(j != n && a[j] == x){
                cnt++;
                x += a[i];
            }
            else{
                check = 0;
                break;
            }
        }
        if(check == 1){
            Max = max(Max, cnt);
            break;
        }
    }
    cout << Max;
    return 0;
}

import sys
from bisect import bisect_left

data = sys.stdin.read().split()
n = int(data[0])
a = []
total = 0
for i in range(n):
    total += int(data[1 + i])
    a.append(total)
Max = -1
for i in range(n):
    cnt, j, check = 1, i, True
    x = 2 * a[i]
    while j + 1 < n:
        j = bisect_left(a, x, j + 1, n)
        if j != n and a[j] == x:
            cnt += 1
            x += a[i]
        else:
            check = False
            break
    if check:
        Max = max(Max, cnt)
        break
print(Max)

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

1. Tạo mảng cộng dồn ngay lúc đọc: đọc vào x, cộng vào sum, rồi gán a[i] = sum, không cần thêm vòng lặp riêng.
2. j = lower_bound(a + j + 1, a + n, x) - a: lần tìm sau bắt đầu từ ngay sau vị trí tìm được lần trước. Vì vậy ban đầu khởi tạo j = i (lần đầu tìm từ $i + 1$), và điều kiện while(j + 1 < n) đảm bảo vị trí bắt đầu tìm còn hợp lệ.
3. Không tìm thấy thì lower_bound trả về đúng n, nên phải kiểm tra j != n trước rồi mới xét a[j] == x – để ngược lại mà lỡ j == n thì truy cập ngoài mảng, có thể văng lỗi đó nha.
4. Cờ check ban đầu bằng 1, gặp chỗ không tìm thấy thì gán 0 và thoát. Sau cùng nếu check == 1 thì cập nhật Max và break luôn vì đó là đáp án lớn nhất. (Với $i = n - 1$ vòng while không chạy, check vẫn là 1, nên chắc chắn luôn có đáp án ít nhất là 1.)

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

C++▶ Chạy tay từng dòng codeCách 3: mảng cộng dồn, với mỗi i tìm nhị phân lần lượt 2a[i], 3a[i], ... cho tới phần tử cuối.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 int a[n], sum = 0, x, Max = -1;

8 for(int i = 0; i < n; ++i){

9 cin >> x;

10 sum += x;

11 a[i] = sum;

12 }

13 for(int i = 0; i < n; ++i){

14 int cnt = 1, j = i, check = 1;

15 x = 2 * a[i];

16 while(j + 1 < n){

17 j = lower_bound(a + j + 1, a + n, x) - a;

18 if(j != n && a[j] == x){

19 cnt++;

20 x += a[i];

21 }

22 else{

23 check = 0;

24 break;

25 }

26 }

27 if(check == 1){

28 Max = max(Max, cnt);

29 break;

30 }

31 }

32 cout << Max;

33 return 0;

34}

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 cộng dồn.
• Thời gian: vòng for i duyệt tuần tự, với mỗi $i$ ta tìm nhị phân trên phần còn lại của mảng, mỗi lần tìm $O(\log N)$. Với mỗi $i$ thì số lần tìm thành công không quá số đoạn tổng $a[i]$ có thể có, cỡ $N / (i + 1)$ trong trường hợp xấu (các phần tử nhỏ), cộng lại theo chuỗi điều hòa $N(1 + \frac{1}{2} + \frac{1}{3} + \ldots) \approx N \ln N$ lần tìm. Vậy xấu nhất khoảng $O(N \log^2 N)$, còn thực tế thường chỉ cỡ $O(N \log N)$ – rất nhanh.

Không gian$O(N)$

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

Cái hay của giải thuật

Từ $O(N^2)$ ta rút xuống còn cỡ $N \log N$ (nhân thêm một log nữa trong trường hợp xấu). Như thế dù $N$ lên tới $10^6$ cũng không sợ TLE, chứ như các cách trước, kể cả bản cải tiến, thì $N$ cỡ $10^5$ là đã TLE rồi chứ đừng nói $10^6$.

Ghi chú của mình: code C++ và Python của cả 3 cách đã được kiểm tra với 1000 bộ test ngẫu nhiên ($n \le 12$, có nhiều bộ được dựng sẵn để chia được nhiều đoạn), so với code vét cạn thử mọi số đoạn $k$ – khớp hết sau khi đã sửa Max = 1 ở Cách 2 (bản gốc khởi tạo Max = -1 in sai $-1$ với test như $6, 1, 1$). Với $n = 1000$ cả 3 cách C++ đều chạy dưới 0.03 giây, Python dưới 0.3 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 😇