Chèn Phép Toán

Nguồn: CLUE OJ Độ khó: Khá Toán học Tìm quy luật Chẵn lẻ Vét cạn

Đề bài

Chèn phép toán
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 512 megabyte

Cho tập $N$ số nguyên $A = \{1, 2, 3, \ldots, N\}$ và một số nguyên $S$.

Yêu cầu: Tìm cách điền mỗi phép toán '+' hoặc '-' vào giữa các cặp liên tiếp nhau của $A$ sao cho kết quả của biểu thức thu được sau khi đã điền hết các phép toán là bằng đúng $S$.

Dữ liệu vào: Dòng đầu chứa một số nguyên $T \le 20$ là số lượng bộ test, mỗi dòng tiếp theo mô tả một bộ test bao gồm hai số nguyên $N$ và $S$.

Kết quả: Mỗi dòng trong số $T$ dòng ghi ra 1 nếu có cách chèn cho bộ test tương ứng, còn ghi ra 0 nếu ngược lại.

Subtask:

• Subtask 1 (20% điểm): $1 \le N \le 20$, $|S| \le 210$.
• Subtask 2 (30% điểm): $1 \le N \le 500$, $|S| \le 125250$.
• Subtask 3 (50% điểm): $1 \le N \le 10^9$, $|S| \le 500{,}000{,}000{,}500{,}000{,}000$.

Ví dụ – input

2
9 5
5 6

Ví dụ – output

1
0

Lời mở đầu

Bài này là một ví dụ rất điển hình cho kinh nghiệm mà mình hay nhắc các bạn: đề càng "có quy luật" thì càng phải làm nháp. Thoạt nhìn thì chỉ có cách thử hết, nhưng khi chịu khó viết ra các trường hợp nhỏ, sắp xếp lại, thì quy luật hiện ra rõ mồn một và mỗi test chỉ cần vài phép so sánh là xong 😎.

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

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Lưu ý số 1 luôn đứng đầu và không được đặt dấu trước nó, ta chỉ điền dấu vào $N - 1$ khoảng trống giữa các số.

• Test 1: $N = 9$, $S = 5$. Có cách điền, ví dụ $1 + 2 + 3 + 4 - 5 + 6 - 7 - 8 + 9 = 5$ ⇒ in 1.
• Test 2: $N = 5$, $S = 6$. Thử hết 16 cách điền dấu (mình liệt kê đầy đủ ở phần dưới) thì không cách nào ra 6 ⇒ in 0.

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

Cách 1Vét cạn 2^(N-1) cách điền dấu · chỉ subtask 1 (20%)Cách 2Làm nháp tìm quy luật · O(1) mỗi test · 100%

Cách 1Vét cạn mọi cách điền dấu – O(2^(N-1)·N)

Một tư tưởng vét cạn rất dễ nhìn ra: cứ xét tất cả các trường hợp điền dấu có thể có, với mỗi trường hợp tính ra kết quả rồi kiểm tra có bằng $S$ không. Bằng thì dừng lại kết luận 1, không bằng thì tính tiếp trường hợp sau; đến cuối mà vẫn không có trường hợp nào bằng $S$ thì kết luận 0.

• $N = 1$: chỉ có 1 số, không có khoảng trống nào để điền dấu, kết quả là $1$.
• $N = 2$: có 1 khoảng trống, mỗi khoảng trống có 2 lựa chọn ($+$ hoặc $-$) ⇒ $2^1 = 2$ trường hợp: $1 - 2 = -1$, $1 + 2 = 3$.
• $N = 3$: có 2 khoảng trống ⇒ $2^2 = 4$ trường hợp: $1 - 2 - 3 = -4$, $1 - 2 + 3 = 2$, $1 + 2 - 3 = 0$, $1 + 2 + 3 = 6$. Nếu đề cho $N = 3$ thì $S$ thuộc một trong 4 giá trị $-4, 0, 2, 6$ là kết luận 1, khác thì 0.

Vì sao liệt kê được hết các trường hợp? Vì nó giống hệt dãy nhị phân: $N$ số có $N - 1$ khoảng trống, ta liệt kê các dãy nhị phân độ dài $N - 1$, tức các số từ $0$ đến $2^{N-1} - 1$. Bit $0$ ứng với dấu $-$, bit $1$ ứng với dấu $+$. Trong code bên dưới, bit thứ $k - 2$ của mask quyết định dấu đứng trước số $k$.

Source code để các bạn tham khảo nếu làm theo hướng này (bài gốc của mình chỉ phân tích ý tưởng, code này mình viết thêm theo đúng ý đó để các bạn chạy thử):

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        long long n, s;
        cin >> n >> s;
        int ans = 0;
        for(long long mask = 0; mask < (1LL << (n - 1)); ++mask){
            long long sum = 1;
            for(int k = 2; k <= n; ++k){
                if(mask >> (k - 2) & 1){
                    sum += k;
                }
                else{
                    sum -= k;
                }
            }
            if(sum == s){
                ans = 1;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

t = int(input())
for _ in range(t):
    n, s = map(int, input().split())
    ans = 0
    for mask in range(1 << (n - 1)):
        total = 1
        for k in range(2, n + 1):
            if mask >> (k - 2) & 1:
                total += k
            else:
                total -= k
        if total == s:
            ans = 1
            break
    print(ans)

C++▶ Chạy tay từng dòng codeCách 1: duyệt mask từ 0 đến 2^(n-1) - 1, bit = 1 là dấu +, bit = 0 là dấu -, tính tổng rồi so với s.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int t;

8 cin >> t;

9 while(t--){

10 long long n, s;

11 cin >> n >> s;

12 int ans = 0;

13 for(long long mask = 0; mask < (1LL << (n - 1)); ++mask){

14 long long sum = 1;

15 for(int k = 2; k <= n; ++k){

16 if(mask >> (k - 2) & 1){

17 sum += k;

18 }

19 else{

20 sum -= k;

21 }

22 }

23 if(sum == s){

24 ans = 1;

25 break;

26 }

27 }

28 cout << ans << endl;

29 }

30 return 0;

31}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$.
• Thời gian: trường hợp xấu nhất là khi đáp án là 0, ta phải xét qua tận cùng mọi trường hợp rồi mới kết luận. Có $2^{N-1}$ trường hợp, mỗi trường hợp tính tổng mất $O(N)$ ⇒ $O(T \cdot 2^{N-1} \cdot N)$.

Không gian$O(1)$

Thời gian$O(T \cdot 2^{N-1} \cdot N)$

Chỉ được subtask 1 (20%)

Với subtask 2, $N = 500$ thì trường hợp xấu nhất là $2^{499}$, cụ thể là lặp tới 1,636,695,303,948,070,935,006,594,848,413,799,576,108,321,023,021,532,394,741,645,684,048,066,898,202,337,277,441,635,046,162,952,078,575,443,342,063,780,035,504,608,628,272,942,696,526,664,263,794,688 lần 😱. Các bạn cứ thử lấy con số đó chia $10^8$ (máy tính phổ thông xử lý khoảng 100 triệu phép tính mỗi giây) ra số giây, rồi chia 3600 ra giờ, chia 24 ra ngày, chia 365 ra năm: sẽ là hàng tỷ tỷ tỷ… tỷ năm mới chạy xong, lúc đó chắc tận thế rồi quá haha. Subtask 3 với $N$ tới $10^9$ thì càng không thể.

Cách 2Làm nháp tìm quy luật – O(1) mỗi test

Vậy chắc chắn bài này phải có cách làm khác. Để ý thấy dãy số chỉ gồm các số từ 1 đến N. Bản thân mình ngay khi đọc đề là thấy: việc ràng buộc dãy phải là $1..N$ chứ không phải các số ngẫu nhiên nghĩa là chắc chắn có quy luật gì đó xoay quanh kết quả. Nếu là số ngẫu nhiên thì chỉ có nước vét cạn, còn khi dãy có quy luật mà $N$ lại cho lớn như vậy thì phải có cách chạy trong 1 giây. Muốn nhìn ra quy luật đó thì hãy làm nháp thật nhiều trường hợp. Bài này bạn nào không làm nháp là chắc chắn không thể nhìn ra được quy luật, đây cũng là kinh nghiệm mình chia sẻ đến các bạn.

Ở trên mình đã nháp $N = 1, 2, 3$. Giờ nháp tiếp $N = 4$ ($2^3 = 8$ trường hợp) và $N = 5$ ($2^4 = 16$ trường hợp):

1 - 2 - 3 - 4 = -8
1 - 2 - 3 + 4 = 0
1 - 2 + 3 - 4 = -2
1 - 2 + 3 + 4 = 6
1 + 2 - 3 - 4 = -4
1 + 2 - 3 + 4 = 4
1 + 2 + 3 - 4 = 2
1 + 2 + 3 + 4 = 10

1 - 2 - 3 - 4 - 5 = -13
1 - 2 - 3 - 4 + 5 = -3
1 - 2 - 3 + 4 - 5 = -5
1 - 2 - 3 + 4 + 5 = 5
1 - 2 + 3 - 4 - 5 = -7
1 - 2 + 3 - 4 + 5 = 3
1 - 2 + 3 + 4 - 5 = 1
1 - 2 + 3 + 4 + 5 = 11
1 + 2 - 3 - 4 - 5 = -9
1 + 2 - 3 - 4 + 5 = 1
1 + 2 - 3 + 4 - 5 = -1
1 + 2 - 3 + 4 + 5 = 9
1 + 2 + 3 - 4 - 5 = -3
1 + 2 + 3 - 4 + 5 = 7
1 + 2 + 3 + 4 - 5 = 5
1 + 2 + 3 + 4 + 5 = 15

(Nhìn danh sách $N = 5$ các bạn sẽ thấy không có số $6$ nào, đó là lý do test 2 của đề ra 0.) Dữ liệu lộn xộn thế này khó nhìn ra quy luật, giờ thử ghi kết quả của từng $N$ theo thứ tự tăng dần nhé:

N = 1 ⇒ 1
N = 2 ⇒ -1, 3
N = 3 ⇒ -4, 0, 2, 6
N = 4 ⇒ -8, -4, -2, 0, 2, 4, 6, 10
N = 5 ⇒ -13, -9, -7, -5, -3, -3, -1, 1, 1, 3, 5, 5, 7, 9, 11, 15

Các bạn có nhìn ra quy luật gì không? Những số trùng nhau ta chỉ tính 1 lần thì:

• Số cuối cùng (gọi là finish) là tổng $1 + 2 + \ldots + N$ (tất cả đều là dấu $+$). Ví dụ $N = 5$ thì $finish = 15$.
• Số đầu tiên (gọi là start) là $-(finish - 2)$. Ví dụ $N = 5$: $15 - 2 = 13$ nên $start = -13$. (Dễ hiểu thôi: số 1 luôn mang dấu $+$, các số còn lại đều $-$ thì được $1 - (finish - 1) = -(finish - 2)$.)
• Từ $start$ đến $finish$ các giá trị tăng dần đều 2 đơn vị, ngoại trừ hai giá trị $start + 2$ và $finish - 2$.

Ví dụ $N = 5$: dãy tăng đều 2 đơn vị là $-13, \color{red}{-11}, -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, \color{red}{13}, 15$, bỏ $start + 2 = -11$ và $finish - 2 = 13$ thì còn lại đúng các số đã liệt kê. Thử lại các $N$ khác:

N = 4: finish = 10, start = -8 ⇒ -8, -6, -4, -2, 0, 2, 4, 6, 8, 10 ✔
N = 3: finish = 6, start = -4 ⇒ -4, -2, 0, 2, 4, 6 ✔
N = 2: finish = 3, start = -1 ⇒ -1, 1, 3 ✔ (start + 2 = finish - 2 = 1)
N = 1: finish = 1, start = -(1 - 2) = 1 ⇒ chỉ có 1 ✔ (start + 2 = 3 và finish - 2 = -1 đều nằm ngoài đoạn)

Tính finish trong O(1)

Không cần vòng lặp cộng từ 1 đến $N$, dùng công thức cấp số cộng: $1 + 2 + \ldots + N = \dfrac{N(N+1)}{2}$.

Minh hoạ: các tổng "lấp" dần trục số

Các bạn nhập $N$ và $S$, bấm Tiếp để xem lần lượt từng cách điền dấu cho ra tổng nào (ô vàng), các ô xanh là tổng đã đạt được. Đến cuối sẽ thấy các tổng phủ kín đoạn $[start, finish]$ với bước nhảy 2, chỉ "thủng" đúng 2 ô đỏ $start + 2$ và $finish - 2$. Ô viền tím là $S$ cần kiểm tra.

N S

Ví dụ nhanh:

Giờ đã nhìn ra quy luật thì cách giải quyết như sau: từ $N$ tính ra $finish$ và $start$. Rồi liệt kê tất cả các trường hợp khiến kết luận là 0; chỉ cần thoả 1 trong số đó là kết luận 0 ngay, còn không thoả trường hợp nào thì kết luận 1:

Kết luận 0 khi và chỉ khi

1. $S \lt start$ hoặc $S \gt finish$ (nằm ngoài đoạn);
2. $S = start + 2$ hoặc $S = finish - 2$ (2 ô "thủng");
3. $S$ khác tính chẵn lẻ với $start$: khi tăng đều 2 đơn vị thì nếu $start$ chẵn, cả dãy đều chẵn; $start$ lẻ thì cả dãy đều lẻ. Nên $start$ lẻ mà $S$ chẵn, hoặc $start$ chẵn mà $S$ lẻ thì chắc chắn là 0.

Ngược lại thì in 1.

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(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        long long n, s;
        cin >> n >> s;
        long long finish = (n * (n + 1)) / 2;
        long long start = -(finish - 2);
        if(s < start || s > finish || s == start + 2 || s == finish - 2 || (start % 2 == 0 && s % 2 != 0) || (start % 2 != 0 && s % 2 == 0)){
            cout << 0 << endl;
        }
        else{
            cout << 1 << endl;
        }
    }
    return 0;
}

t = int(input())
for _ in range(t):
    n, s = map(int, input().split())
    finish = (n * (n + 1)) // 2
    start = -(finish - 2)
    if s < start or s > finish or s == start + 2 or s == finish - 2 or (start % 2 == 0 and s % 2 != 0) or (start % 2 != 0 and s % 2 == 0):
        print(0)
    else:
        print(1)

C++▶ Chạy tay từng dòng codeCách 2: tính finish = n(n+1)/2, start = -(finish - 2), loại các trường hợp ngoài đoạn / 2 ô thủng / khác chẵn lẻ.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int t;

8 cin >> t;

9 while(t--){

10 long long n, s;

11 cin >> n >> s;

12 long long finish = (n * (n + 1)) / 2;

13 long long start = -(finish - 2);

14 if(s < start || s > finish || s == start + 2 || s == finish - 2 || (start % 2 == 0 && s % 2 != 0) || (start % 2 != 0 && s % 2 == 0)){

15 cout << 0 << endl;

16 }

17 else{

18 cout << 1 << endl;

19 }

20 }

21 return 0;

22}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(1)$.
• Thời gian: vòng lặp chạy $T$ lần, mỗi lần đọc dữ liệu vào là tính ra kết quả ngay ⇒ $O(T)$. $T$ tối đa chỉ 20 nên cách này được xem là tối ưu nhất, không thể nào lo bị TLE được.

Không gian$O(1)$

Thời gian$O(T)$

Lưu ý 1: đừng dùng vòng lặp tính finish

Một số bạn tính $finish$ bằng cách lặp từ 1 đến $N$ để cộng dồn, khi đó độ phức tạp là $O(T \cdot N)$, với subtask 3 ($T = 20$, $N = 10^9$) là $2 \cdot 10^{10}$ phép tính ⇒ TLE. Hãy dùng công thức cấp số cộng để tính trong $O(1)$ các bạn nha.

Lưu ý 2: phải dùng long long

$N$ tới $10^9$ thì $N(N+1) \approx 10^{18}$ và $|S|$ tới $5 \cdot 10^{17}$, vượt xa kiểu int. Cả n, s, finish, start đều phải là long long, và phải để n là long long trước khi nhân n * (n + 1). Còn chuyện $S$, $start$ âm khi lấy % 2 (C++ cho ra $-1$) thì không ảnh hưởng vì code chỉ so sánh == 0 / != 0.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output test của đề. Code cách 2 đã được so với tập tổng đạt được tính chính xác bằng cách duyệt mọi cách điền dấu cho mọi $N \le 22$ và mọi $S$ trong $[-finish - 4,\ finish + 4]$ (4246 bộ) – khớp hết; code cách 1 khớp với cách 2 trên 300 bộ test ngẫu nhiên nhỏ. Với 20 test $N = 10^9$, $|S|$ cỡ $5 \cdot 10^{17}$, cách 2 chạy tức thì. Cách 1 (C++) với 20 test $N = 20$ đáp án 0 chạy khoảng 0.2 giây CPU nên vừa đủ subtask 1, còn bản Python cách 1 với $N = 20$ mất khoảng 2.5 giây cho chỉ 1 test, nên Python chỉ dùng để tham khảo ý tưởng thôi nhé.

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 😇