Meet in the middle

Mức độ: Nâng cao

Đề cho n = 40 số, đếm số cách chọn một tập con có tổng bằng S. Thử hết thì có 2⁴⁰, khoảng 10¹² tập con, quá chậm. Quy hoạch động theo tổng cũng không được nếu các số tới 10⁹. Meet in the middle (gặp nhau ở giữa) chia dãy làm hai nửa, mỗi nửa 20 số chỉ có 2²⁰, khoảng 10⁶ tập con. Liệt kê riêng từng nửa, rồi ghép hai nửa lại một cách thông minh.

Ý tưởng

Mỗi tập con của cả dãy gồm một phần nằm ở nửa trái và một phần nằm ở nửa phải. Tổng tập con bằng S khi:

(tổng phần bên trái) + (tổng phần bên phải) = S

Vậy với mỗi tổng x của nửa trái, chỉ cần đếm có bao nhiêu tổng của nửa phải bằng S - x. Đây chính là bài đếm cặp có tổng bằng S giữa hai danh sách, làm bằng dict/map đếm tần suất hoặc sắp xếp rồi tìm kiếm nhị phân.

Dãy 3 5 6 7, S = 11, chia thành 3 5 | 6 7:

Tập con nửa trái	Tổng x	Cần S - x	Số tập con nửa phải có tổng đó
(rỗng)	0	11	0
3	3	8	0
5	5	6	1 (tập 6)
3, 5	8	3	0

Tổng các tập con nửa phải: (rỗng) 0, 6, 7, 13. Đáp số 1: tập 5, 6.

Số bước: liệt kê 2 × 2^n/2 tổng, rồi mỗi tổng nửa trái tra một lần. Với n = 40 là khoảng 2 × 10⁶ bước thay vì 10¹², ít hơn khoảng 500 000 lần.

Liệt kê tổng các tập con

Liệt kê tổng mọi tập con của một nửa bằng cách nhân đôi dần: bắt đầu với danh sách [0] (tập rỗng). Với mỗi số x, mọi tập con cũ hoặc không lấy x, hoặc lấy thêm x, nên danh sách mới gồm các tổng cũ và các tổng cũ cộng x.

Đã xét	Các tổng
(chưa có số nào)	0
3	0, 3
3, 5	0, 3, 5, 8

Python

import sys
from collections import Counter

def cac_tong(day):
    tong = [0]
    for x in day:
        tong += [t + x for t in tong]
    return tong

du_lieu = sys.stdin.read().split()
n, s = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))
trai = cac_tong(a[:n // 2])
dem_phai = Counter(cac_tong(a[n // 2:]))
print(sum(dem_phai[s - x] for x in trai))

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<long long> cacTong(const vector<long long> &day) {
    vector<long long> tong = {0};
    for (long long x : day) {
        int cu = tong.size();
        for (int i = 0; i < cu; i++) tong.push_back(tong[i] + x);
    }
    return tong;
}

int main() {
    int n;
    long long s;
    cin >> n >> s;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    vector<long long> trai = cacTong(vector<long long>(a.begin(), a.begin() + n / 2));
    vector<long long> phai = cacTong(vector<long long>(a.begin() + n / 2, a.end()));
    sort(phai.begin(), phai.end());
    long long soCach = 0;
    for (long long x : trai) {
        auto khoang = equal_range(phai.begin(), phai.end(), s - x);   // các tổng bằng s - x
        soCach += khoang.second - khoang.first;
    }
    cout << soCach << "\n";
    return 0;
}

Lưu ý: cách đếm này tính cả tập rỗng. Nếu đề chỉ đếm tập con khác rỗng và S = 0 thì trừ đi 1.

Không chỉ “bằng S”

Ghép hai nửa dùng được cho nhiều kiểu câu hỏi, chỉ cần sắp xếp danh sách nửa phải:

Câu hỏi	Với mỗi tổng x của nửa trái
đếm tập con có tổng bằng S	đếm các tổng nửa phải bằng S - x
tổng lớn nhất không quá S	tìm tổng nửa phải lớn nhất không quá S - x (tìm kiếm nhị phân)
đếm tập con có tổng không quá S	đếm các tổng nửa phải không quá S - x
tổng gần S nhất	xét hai tổng nửa phải đứng hai bên S - x

Ý tưởng chung: thay vì thử mọi cặp (trái, phải), với mỗi phần trái ta biết chính xác phần phải cần là gì, rồi tra nhanh trong danh sách đã chuẩn bị.

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Tổng các tập con

Bài 1. Đếm tập con có tổng bằng S

Dòng đầu có n, S (1 ≤ n ≤ 40, |S| ≤ 10¹⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10¹²). In ra số tập con (kể cả tập rỗng) có tổng bằng S.

Ví dụ:

Nhập	In ra
4 11 3 5 6 7	1

Kiểm tra: nhập

20 0
1 -2 3 -4 5 -6 7 -1 2 -3 4 -5 6 -7 1 -2 3 -4 5 -6

Xem đáp số

42040

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Có tập con tổng bằng S không

Dòng đầu có n, S (1 ≤ n ≤ 40, 0 ≤ S ≤ 10¹⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10¹²). In ra YES nếu có một tập con khác rỗng có tổng bằng S, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
5 23 10 4 8 3 15	YES

Kiểm tra: nhập

20 4000002478
1000000000 1000000007 1000000028 1000000063 1000000112 1000000175 1000000252 1000000343 1000000448 1000000567 1000000700 1000000847 1000001008 1000001183 1000001372 1000001575 1000001792 1000002023 1000002268 1000002527

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Tổng lớn nhất không vượt quá S

Dòng đầu có n, S (1 ≤ n ≤ 40, 0 ≤ S ≤ 10¹⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10¹²). In ra tổng lớn nhất của một tập con (có thể rỗng) không vượt quá S.

Ví dụ:

Nhập	In ra
5 20 7 11 4 13 8	20

Kiểm tra: nhập

20 23456789012
33333310 79012289 154320876 266666473 423456482 632098305 899999344 1234567001 1643208678 2133331777 2712343700 3387651849 4166663626 5056786433 6065427672 7199994745 8467895054 9876536001 1433324988 3145669417

Xem đáp số

23456773012

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Tổng gần S nhất

Dòng đầu có n, S (1 ≤ n ≤ 40, |S| ≤ 10¹⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10¹²). In ra giá trị nhỏ nhất của |(tổng tập con) - S| trên mọi tập con (kể cả tập rỗng).

Ví dụ:

Nhập	In ra
4 -7 5 -3 9 -2	2

Kiểm tra: nhập

20 77777777777
987654321 -1975308642 2962962963 -3950617284 4938271605 -5925925926 6913580247 -7901234568 8888888889 -9876543210 10864197531 -11851851852 12839506173 -13827160494 14814814815 -15802469136 16790123457 -17777777778 18765432099 -19753086420

Xem đáp số

246913582

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Chia hai đội

Có n bạn, bạn thứ i nặng a_i kg. Chia n bạn thành hai đội (đội có thể không có ai) sao cho chênh lệch tổng cân nặng hai đội nhỏ nhất. Dòng đầu có n (1 ≤ n ≤ 40), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10¹²). In ra chênh lệch nhỏ nhất.

Ví dụ:

Nhập	In ra
5 40 25 32 18 55	4

Kiểm tra: nhập

20
100000000000 100000031337 100000250696 100000846099 100002005568 100003917125 100006768792 100010748591 100016044544 100022844673 100031337000 100041709547 100054150336 100068847389 100085988728 100105762375 100128356352 100153958681 100182757384 100214940483

Xem đáp số

0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Đếm tập con có tổng trong đoạn

Dòng đầu có n, L, R (1 ≤ n ≤ 40, |L|, |R| ≤ 10¹⁵, L ≤ R), dòng thứ hai có n số nguyên (|a_i| ≤ 10¹²). In ra số tập con (kể cả tập rỗng) có tổng từ L đến R.

Ví dụ:

Nhập	In ra
4 5 10 2 3 5 8	7

Kiểm tra: nhập

20 -100 100
1 -38 75 -11 48 -85 21 -58 95 -31 68 -4 41 -78 14 -51 88 -24 61 -98

Xem đáp số

575214

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Ít đồng xu nhất

Có n đồng xu, đồng thứ i có mệnh giá a_i (mỗi đồng dùng nhiều nhất một lần). Dòng đầu có n, S (1 ≤ n ≤ 40, 1 ≤ S ≤ 10¹⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10¹²). In ra số đồng xu ít nhất để trả đúng S, hoặc -1 nếu không trả được.

Ví dụ:

Nhập	In ra
6 15 1 5 7 8 3 6	2

Kiểm tra: nhập

20 6004654065
1000000000 1000012345 1000049380 1000111105 1000197520 1000308625 1000444420 1000604905 1000790080 1000999945 1001234500 1001493745 1001777680 1002086305 1002419620 1002777625 1003160320 1003567705 1003999780 1004456545

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Tổng nhỏ nhất ít nhất bằng S

Dòng đầu có n, S (1 ≤ n ≤ 40, 1 ≤ S ≤ 10¹⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10¹²). In ra tổng nhỏ nhất của một tập con mà tổng đó ít nhất S, hoặc -1 nếu tổng cả dãy còn nhỏ hơn S.

Ví dụ:

Nhập	In ra
5 20 6 9 14 3 11	20

Kiểm tra: nhập

20 1232739991
32891189 39143233 45938933 53278289 61161301 69587969 78558293 88072273 98129909 108731201 119876149 131564753 143797013 156572929 169892501 183755729 198162613 213113153 228607349 244645201

Xem đáp số

1232739991

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Biến đổi rồi chia đôi

Bài 9. Tập con có trung bình bằng k

Dòng đầu có n, k (1 ≤ n ≤ 40, |k| ≤ 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số tập con khác rỗng có trung bình cộng đúng bằng k.

Ví dụ:

Nhập	In ra
5 4 2 6 4 9 3	3

Kiểm tra: nhập

20 7
3 8 4 9 5 10 6 11 7 3 8 4 9 5 10 6 11 7 3 8

Xem đáp số

67823

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Tổng chia hết cho m

Dòng đầu có n, m (1 ≤ n ≤ 40, 1 ≤ m ≤ 10⁹), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁹). In ra số tập con khác rỗng có tổng chia hết cho m.

Ví dụ:

Nhập	In ra
4 5 1 4 6 9	5

Kiểm tra: nhập

20 1009
123457 246914 370371 493828 617285 740742 864199 987656 111110 234567 358024 481481 604938 728395 851852 975309 98763 222220 345677 469134

Xem đáp số

1555

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Số dư lớn nhất

Dòng đầu có n, m (1 ≤ n ≤ 40, 1 ≤ m ≤ 10⁹), dòng thứ hai có n số nguyên (0 ≤ a_i ≤ 10⁹). In ra giá trị lớn nhất của (tổng tập con) chia lấy dư cho m, xét mọi tập con kể cả tập rỗng.

Ví dụ:

Nhập	In ra
4 10 5 2 4 1	9

Kiểm tra: nhập

20 999999937
31415926 62831852 94247778 125663704 157079630 188495556 219911482 251327408 282743334 314159260 345575186 376991112 408407038 439822964 471238890 502654816 534070742 565486668 596902594 628318520

Xem đáp số

995132486

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Tập con có XOR bằng x

Dòng đầu có n, x (1 ≤ n ≤ 40, 0 ≤ x nhỏ hơn 2⁶⁰), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2⁶⁰). In ra số tập con (kể cả tập rỗng) có XOR các phần tử bằng x (XOR của tập rỗng bằng 0).

Ví dụ:

Nhập	In ra
4 6 3 5 6 1	2

Kiểm tra: nhập

20 1023
0 433 866 275 708 117 550 983 392 825 234 667 76 509 942 351 784 193 626 35

Xem đáp số

1024

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Vali hành lý

Có n đồ vật, vật thứ i nặng w_i và có giá trị v_i. Chọn một số vật bỏ vào vali chịu được nhiều nhất W. Dòng đầu có n, W (1 ≤ n ≤ 40, 0 ≤ W ≤ 10¹⁵), n dòng sau mỗi dòng có w, v (1 ≤ w, v ≤ 10¹²). In ra tổng giá trị lớn nhất.

Ví dụ:

Nhập	In ra
4 10 5 10 4 40 6 30 3 50	90

Kiểm tra: nhập

18 300000000000
14000000000 1
13000000000 104730
12000000000 209459
11000000000 314188
10000000000 418917
9000000000 523646
8000000000 628375
7000000000 733104
6000000000 837833
5000000000 942562
4000000000 1047291
3000000000 1152020
2000000000 1256749
1000000000 1361478
90000000000 1466207
89000000000 1570936
88000000000 1675665
87000000000 1780394

Xem đáp số

12986412

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Mỗi phần tử có ba lựa chọn

Bài 14. Cân đồ vật

Một cái cân hai đĩa, đồ vật nặng S đặt ở đĩa trái. Có n quả cân, quả thứ i nặng a_i, mỗi quả đặt lên đĩa trái, đĩa phải hoặc không dùng. Dòng đầu có n, S (1 ≤ n ≤ 24, 1 ≤ S ≤ 10¹²), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10¹¹). In ra số cách đặt quả cân để hai đĩa cân bằng.

Ví dụ:

Nhập	In ra
3 5 1 3 9	1

Kiểm tra: nhập

12 1000
1 4 11 30 85 248 735 8 11 18 37 92

Xem đáp số

182

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Trả tiền, mỗi loại hai tờ

Có n loại tiền, loại thứ i mệnh giá a_i, mỗi loại có đúng hai tờ. Dòng đầu có n, S (1 ≤ n ≤ 24, 0 ≤ S ≤ 10¹⁵), dòng thứ hai có n số a_i (1 ≤ a_i ≤ 10¹², có thể trùng). In ra số cách chọn số tờ dùng của mỗi loại (0, 1 hoặc 2 tờ) để tổng đúng S.

Ví dụ:

Nhập	In ra
3 7 1 2 5	2

Kiểm tra: nhập

12 60
1 2 3 5 6 7 9 10 11 4 5 6

Xem đáp số

10095

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Ghép hai nửa của một biểu thức

Bài 16. Bốn dãy có tổng bằng 0

Có bốn dãy A, B, C, D, mỗi dãy n số nguyên. Dòng đầu có n (1 ≤ n ≤ 1000), bốn dòng sau lần lượt là bốn dãy (|giá trị| ≤ 10⁹). In ra số bộ (a, b, c, d), lấy a từ A, b từ B, c từ C, d từ D (theo vị trí), có a + b + c + d = 0.

Ví dụ:

Nhập	In ra
2 1 2 -2 -1 -1 2 0 2	2

Kiểm tra: nhập

8
3 -1 4 1 -5 9 -2 6
5 3 -5 8 9 7 -9 3
2 -3 8 4 -6 2 6 -4
-3 3 8 -3 2 7 9 5

Xem đáp số

103

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Bộ bốn chỉ số có tổng bằng S

Dòng đầu có n, S (4 ≤ n ≤ 1000, |S| ≤ 4 × 10⁹), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số bộ chỉ số i, j, k, l với i đứng trước j, j trước k, k trước l và a_i + a_j + a_k + a_l = S.

Ví dụ:

Nhập	In ra
6 10 1 2 3 4 5 1	3

Kiểm tra: nhập

10 0
-3 1 2 -1 0 3 -2 1 -1 2

Xem đáp số

26

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Chọn ở hai giỏ cùng tổng

Giỏ thứ nhất có n quả, giỏ thứ hai có m quả, mỗi quả có khối lượng. Chọn một nhóm quả (có thể rỗng) ở giỏ thứ nhất và một nhóm ở giỏ thứ hai có tổng khối lượng bằng nhau. Dòng đầu có n, m (1 ≤ n, m ≤ 20), hai dòng sau là khối lượng các quả của hai giỏ (1 ≤ khối lượng ≤ 10⁹). In ra số cách chọn (cả hai nhóm đều rỗng cũng là một cách).

Ví dụ:

Nhập	In ra
3 3 1 2 3 3 1 5	7

Kiểm tra: nhập

10 10
1 2 3 4 5 1 2 3 4 5
1 2 3 4 5 6 7 1 2 3

Xem đáp số

48848

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Đường đi XOR trên lưới

Bảng n hàng, m cột, mỗi ô ghi một số. Đi từ ô trên cùng bên trái đến ô dưới cùng bên phải, mỗi bước sang phải hoặc xuống dưới. Dòng đầu có n, m, k (1 ≤ n, m ≤ 20, 0 ≤ k nhỏ hơn 2⁶⁰), n dòng sau mỗi dòng có m số (0 ≤ số nhỏ hơn 2⁶⁰). In ra số đường đi có XOR các ô trên đường (kể cả ô đầu và ô cuối) bằng k.

Ví dụ:

Nhập	In ra
3 3 11 2 1 5 7 10 0 12 6 4	3

Kiểm tra: nhập

8 8 5
0 4 8 12 3 7 11 2
5 9 0 4 8 12 3 7
10 1 5 9 0 4 8 12
2 6 10 1 5 9 0 4
7 11 2 6 10 1 5 9
12 3 7 11 2 6 10 1
4 8 12 3 7 11 2 6
9 0 4 8 12 3 7 11

Xem đáp số

48

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Sáu số trong phương trình

Cho tập T gồm n số nguyên khác nhau. Dòng đầu có n (1 ≤ n ≤ 100), dòng thứ hai có n số (|giá trị| ≤ 30000). In ra số bộ sáu (a, b, c, d, e, f), mỗi số lấy từ T (được lặp lại), thỏa mãn d khác 0 và (a × b + c) / d - e = f.

Ví dụ:

Nhập	In ra
2 2 3	4

Kiểm tra: nhập

10
-7 -3 -1 0 1 2 4 5 9 12

Xem đáp số

10529

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.