Two Sets (CSES 1092)

Nguồn: CSES Problem Set – 1092 Độ khó: Dễ Toán học Tìm quy luật Tham lam

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

CSES 1092 – Two Sets (Hai tập hợp)

Nhiệm vụ của bạn là chia các số $1, 2, \ldots, n$ thành hai tập hợp có tổng bằng nhau.

Dữ liệu vào: Dòng duy nhất chứa một số nguyên $n$.

Kết quả: In ra YES nếu có thể chia được, ngược lại in NO.

Sau đó, nếu chia được, hãy in ra một cách chia các tập hợp. Đầu tiên in số phần tử của tập thứ nhất, rồi in các phần tử của nó trên một dòng riêng; sau đó in tập thứ hai theo cách tương tự.

Ràng buộc: $1 \le n \le 10^6$.

Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.

CSES 1092 – Two Sets

Time limit: 1.00 s. Memory limit: 512 MB.

Your task is to divide the numbers $1,2,\ldots,n$ into two sets of equal sum.

Input: The only input line contains an integer $n$.

Output: Print YES, if the division is possible, and NO otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints: $1 \le n \le 10^6$

Ví dụ 1 – input

7

Ví dụ 1 – output

YES
4
1 2 4 7
3
3 5 6

Ví dụ 2 – input

6

Ví dụ 2 – output

NO

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

Nhắc lại ngưỡng TLE

Với các hệ thống chấm giới hạn 1 giây, tối đa toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này thì hên xui nhé). Ngưỡng này là cho C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Bài này giới hạn 1 giây.

Đề gốc là tiếng Anh nhưng ngắn gọn, ở trên mình đã dịch sang tiếng Việt rồi. Mình giải thích lại cho bạn nào chưa hiểu: đầu vào cho 1 số nguyên $N$, ta hiểu là có một dãy số từ $1$ đến $N$, ví dụ $N = 7$ thì có dãy 1 2 3 4 5 6 7. Hãy xem có thể chia dãy này thành 2 tập hợp (mỗi số thuộc đúng 1 tập) sao cho tổng 2 tập bằng nhau không?

• Nếu có thể: dòng 1 in YES, dòng 2 in số lượng số của tập 1, dòng 3 in danh sách các số trong tập 1, dòng 4 in số lượng số của tập 2, dòng 5 in danh sách các số trong tập 2.
• Nếu không có cách nào chia: in 1 dòng NO.

Như ví dụ của đề: $N = 6$ thì kết quả là NO, còn $N = 7$ thì chia được thành $\{1, 2, 4, 7\}$ và $\{3, 5, 6\}$, đều có tổng bằng 14.

Đáp án không duy nhất

Với $N = 7$ còn nhiều cách chia khác, ví dụ $\{1, 6, 7\}$ và $\{2, 3, 4, 5\}$ cũng đều có tổng 14. Đề chỉ yêu cầu in một cách chia bất kỳ và CSES có trình chấm kiểm tra cách chia của bạn, nên code bên dưới in ra cách chia khác ví dụ vẫn được chấm đúng nha 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

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

Cách 1Công thức cấp số cộng + gom từ cuối dãy · O(N) thời gian, O(1) bộ nhớ

Cách 1Tìm quy luật: gom từ cuối dãy – O(N), không cần mảng

Trước tiên ta để ý: danh sách chỉ gồm các số từ $1$ đến $N$, tức là dãy số có quy luật, khác hoàn toàn với tình huống danh sách là các số ngẫu nhiên. Khi nhìn thấy mấu chốt này, ta phải tự nhủ trong đầu rằng chắc chắn có quy luật gì đó ở đây, cố gắng tìm ra nó thì sẽ giải quyết ngon lành bài này.

Mình có xem qua một số code các bạn nộp thì thấy các bạn dùng mảng 1 chiều $N$ phần tử để đánh dấu số nào đã được chọn hay chưa, có bạn thì đi tìm kiếm nhị phân trên mảng các kiểu. Nếu giả sử bài này cho $N$ thật lớn hoặc giới hạn bộ nhớ ít lại thì sẽ không thể tạo mảng $N$ phần tử như vậy được. Bài này hoàn toàn có thể giải quyết không cần dùng bộ nhớ phụ, tức là không cần mảng gì cả. Làm sao được thì các bạn xem tiếp nhé.

Bước 1: tổng lẻ thì chắc chắn NO

Tính tổng của dãy: nếu tổng là số lẻ thì chắc chắn không có cách nào chia được, vì muốn chia làm 2 phần bằng nhau thì tổng phải chia hết cho 2. Ví dụ $N = 6$: $1 + 2 + 3 + 4 + 5 + 6 = 21$ là số lẻ nên không thể chia.

Bạn nào không biết công thức cấp số cộng thì phải làm vòng lặp từ 1 đến $N$ cộng dồn, mất $O(N)$. Còn biết công thức thì tính ra ngay trong $O(1)$:

Công thức cấp số cộng

$sum = 1 + 2 + \ldots + N = \dfrac{N \cdot (N + 1)}{2}$
Ví dụ $N = 6$: $\dfrac{6 \cdot 7}{2} = 21$; $N = 7$: $\dfrac{7 \cdot 8}{2} = 28$.

Nhớ dùng long long

Với $N = 10^6$ thì $N \cdot (N + 1) \approx 10^{12}$, vượt xa giới hạn của int (khoảng $2{,}1 \cdot 10^9$). Nên $n$, sum, x, s đều phải khai báo long long, không thì bị tràn số ra kết quả sai.

Từ đây trở xuống ta mặc định tổng là số chẵn và tìm cách chia thành 2 tập hợp.

Bước 2: quy luật chia

Các bạn hãy thử làm nháp các trường hợp $N = 3, 4, 7, 8, 11$, là những trường hợp đầu tiên (tính từ 1) mà có thể chia thành 2 tập hợp được. Ghi ra dãy số của các trường hợp đó các bạn sẽ nhìn thấy quy luật như sau.

Gọi $x = sum / 2$ là tổng mà mỗi tập hợp cần đạt. Đi từ cuối dãy về đầu (từ $N$ về $1$), cứ liên tục cộng dồn vào biến $s$ đến khi nào $s \ge x$ thì dừng:

• Nếu $s = x$ luôn: lưu idx1 = i. Tập 1 gồm các số từ idx1 đến $N$. Ví dụ $N = 3$: $x = 6/2 = 3$, xét $i = 3$ thì $s = 3 = x$ ngay ⇒ idx1 = 3, tập 1 là $\{3\}$, tập 2 là $\{1, 2\}$.
• Nếu $s$ vượt qua $x$: ta không lấy số $i$ vừa cộng, mà lưu idx1 = i + 1 là vị trí trước đó (khi tổng còn nhỏ hơn $x$). Bớt $i$ ra thì tổng còn $s - i < x$; phần còn thiếu là $x - (s - i)$, và số này chắc chắn nằm ở phía trên của dãy, lưu vào idx2 = x - (s - i). Tập 1 gồm số idx2 cùng các số từ idx1 đến $N$.

Cuối cùng duyệt lại dãy từ 1 đến $N$: số nào bằng idx2 hoặc $\ge$ idx1 thì thuộc tập 1; số nào khác idx2 và $<$ idx1 thì thuộc tập 2.

Vì sao số còn thiếu idx2 luôn tồn tại?

Lúc dừng ta có $s - i < x$ (lần trước chưa đủ) và $s > x$ (lần này dư). Nên phần thiếu $idx2 = x - (s - i)$ thoả $1 \le idx2 < i$, tức $idx2$ là một số trong $1..i-1$, chưa bị lấy vào tập 1 (các số đã lấy đều $\ge i + 1$). Vậy lấy thêm đúng số $idx2$ là tập 1 có tổng đúng bằng $x$, phần còn lại tự động cũng có tổng $sum - x = x$.

Ví dụ $N = 8$: dãy 1 2 3 4 5 6 7 8, $sum = 36$, $x = 18$. Cộng từ cuối: $s = 8 < 18$; $s = 8 + 7 = 15 < 18$; $s = 15 + 6 = 21 > 18$ ⇒ dừng, bớt 6 lại còn 15, lưu idx1 = 7, idx2 = 18 - 15 = 3. Tập 1 là $\{3, 7, 8\}$, tập 2 là $\{1, 2, 4, 5, 6\}$, đều có tổng 18.

N	sum	x	idx1	idx2	Tập 1	Tập 2
3	6	3	3	–	3	1 2
4	10	5	4	1	1 4	2 3
6	21	tổng lẻ ⇒ NO
7	28	14	6	1	1 6 7	2 3 4 5
8	36	18	7	3	3 7 8	1 2 4 5 6

Để ý thêm

Tổng $\dfrac{N(N+1)}{2}$ chẵn khi và chỉ khi $N$ chia 4 dư 0 hoặc dư 3 (các giá trị $3, 4, 7, 8, 11, 12, \ldots$), nên đáp án là YES đúng với những $N$ này.

Em nhập $N$ rồi bấm Tiếp để xem quá trình cộng dồn từ cuối dãy, tìm idx1, idx2 và chia 2 tập:

N

Ví dụ nhanh:

Source code để các bạn tham khảo với hướng làm mình trình bày ở trên:

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long sum = (n * (n + 1)) / 2;
    if(sum % 2 != 0){
        cout << "NO";
    }
    else{
        cout << "YES";
        long long x = sum / 2;
        long long s = 0;
        int idx1, idx2 = -1, cnt = 0;
        for(int i = n; i >= 1; --i){
            s += i;
            if(s >= x){
                if(s == x){
                    idx1 = i;
                    cnt = n - idx1 + 1;
                }
                else{
                    idx1 = i + 1;
                    idx2 = x - (s - i);
                    cnt = n - idx1 + 1 + 1;
                }
                break;
            }
        }
        cout << endl << cnt << endl;
        for(int i = 1; i <= n; ++i){
            if(i == idx2 || i >= idx1){
                cout << i << " ";
            }
        }
        cout << endl << n - cnt << endl;
        for(int i = 1; i <= n; ++i){
            if(i != idx2 && i < idx1){
                cout << i << " ";
            }
        }
    }
    return 0;
}

n = int(input())
total = n * (n + 1) // 2
if total % 2 != 0:
    print("NO")
else:
    x = total // 2
    s = 0
    idx1, idx2, cnt = 0, -1, 0
    for i in range(n, 0, -1):
        s += i
        if s >= x:
            if s == x:
                idx1 = i
                cnt = n - idx1 + 1
            else:
                idx1 = i + 1
                idx2 = x - (s - i)
                cnt = n - idx1 + 1 + 1
            break
    set1 = [i for i in range(1, n + 1) if i == idx2 or i >= idx1]
    set2 = [i for i in range(1, n + 1) if i != idx2 and i < idx1]
    print("YES")
    print(cnt)
    print(" ".join(map(str, set1)))
    print(n - cnt)
    print(" ".join(map(str, set2)))

Giải thích 1 số chỗ trong code ở trên:

1. idx2 không phải lúc nào cũng có: nếu cộng từ cuối lên mà tổng bằng đúng $x$ thì không có idx2 (ví dụ $N = 3$). Nên ta khởi tạo idx2 = -1, giá trị chẳng bao giờ nằm trong $1..N$, để nếu không có idx2 thì khi so sánh i == idx2 chẳng ảnh hưởng gì; còn nếu có thì nó đã được cập nhật lại bằng x - (s - i).
2. Biến cnt đếm số phần tử của tập 1, ta tính ngay ở bước tìm idx1, idx2, vì đề yêu cầu phải in số lượng trước danh sách. Các số từ idx1 đến $N$ có $N - idx1 + 1$ số, có thêm idx2 thì cộng thêm 1. Tập 2 có $N - cnt$ số.
3. Có thể tối ưu bước in: in tập 1 thì in idx2 (nếu có) rồi chỉ cần duyệt từ idx1 đến $N$; in tập 2 thì chỉ cần duyệt các số nhỏ hơn idx1, không cần duyệt hết. Tuy nhiên mình muốn code ngắn gọn nên để vậy cho nhanh, vì sau cùng độ phức tạp vẫn là $O(N)$ thôi, mình nói rõ ở đây để các bạn hiểu.
4. Bản Python gom các số vào list rồi in một lần bằng " ".join(...), vì gọi print từng số với $N = 10^6$ sẽ rất chậm.

C++▶ Chạy tay từng dòng codeTính sum bằng công thức, cộng dồn từ N về 1 để tìm idx1, idx2 rồi in 2 tập.

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

Dữ liệu mẫu:

1#include <iostream>

2using namespace std;

3

4int main() {

5 long long n;

6 cin >> n;

7 long long sum = (n * (n + 1)) / 2;

8 if(sum % 2 != 0){

9 cout << "NO";

10 }

11 else{

12 cout << "YES";

13 long long x = sum / 2;

14 long long s = 0;

15 int idx1, idx2 = -1, cnt = 0;

16 for(int i = n; i >= 1; --i){

17 s += i;

18 if(s >= x){

19 if(s == x){

20 idx1 = i;

21 cnt = n - idx1 + 1;

22 }

23 else{

24 idx1 = i + 1;

25 idx2 = x - (s - i);

26 cnt = n - idx1 + 1 + 1;

27 }

28 break;

29 }

30 }

31 cout << endl << cnt << endl;

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

33 if(i == idx2 || i >= idx1){

34 cout << i << " ";

35 }

36 }

37 cout << endl << n - cnt << endl;

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

39 if(i != idx2 && i < idx1){

40 cout << i << " ";

41 }

42 }

43 }

44 return 0;

45}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$, không dùng mảng nào cả.
• Thời gian: trường hợp đẹp nhất là NO thì chỉ $O(1)$ là kết luận được ngay. Trường hợp YES dùng 3 vòng lặp, mỗi vòng tối đa $N$ lần, tổng $O(3N)$, bỏ hằng số theo quy tắc nhân BigO ⇒ $O(N)$.

Không gian$O(1)$

Thời gian$O(N)$

Trường hợp xấu nhất $N = 10^6$ thì tổng số lần lặp khoảng $3 \cdot 10^6$, ít hơn ngưỡng giới hạn 1 giây cả 10 đến 30 lần, nên hoàn toàn không phải lo bị TLE nhé các bạn.

Ghi chú của mình: vì đáp án không duy nhất nên mình viết một chương trình kiểm tra riêng: với mọi $N$ từ 1 đến 1500 (bản Python: 1 đến 300), kiểm tra YES/NO đúng (so với quy hoạch động tổng tập con khi $N \le 60$), 2 tập khác rỗng, gộp lại đúng là $1..N$ và có tổng bằng nhau – đúng hết. Với $N = 10^6$ trên máy mình: bản C++ chạy khoảng 0.06 giây, bản Python khoảng 0.4 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 😇