Hướng dẫn giải của Tập hợp cân bằng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Tập hợp cân bằng

Hướng tiếp cận

Gặp nhau ở giữa (Meet in the middle): chia $N$ bò thành 2 nửa, liệt kê tất cả tập con của mỗi nửa.

Nhận xét quan trọng

Tập con $S$ cân bằng ↔ tổng $T = \sum_{i \in S} M_{i}$ chẵn và tồn tại tập con $A \subseteq S$ với $\sum_{i \in A} M_{i} = T / 2$ .
Chia bò thành nửa trái (H bò) và nửa phải (H2 bò). Với mỗi cặp $(l m a s k, r m a s k)$ : cần tồn tại $s u b_l \subseteq l m a s k$ và $s u b_r \subseteq r m a s k$ sao cho $lsum [s u b_l] + rsum [s u b_r] = T / 2$ .
Tiền xử lý: với mỗi $l m a s k$ , tính tập hợp ${l s u m [s u b_l] : s u b_l \subseteq l m a s k}$ (sắp xếp để tìm kiếm nhị phân).

Thuật toán

Với mỗi $l m a s k$ ( $2^{N / 2}$ giá trị): liệt kê tất cả $s u b_l \subseteq l m a s k$ , lưu lsum vào mảng sắp xếp.
Với mỗi $(l m a s k, r m a s k)$ : nếu $T$ lẻ → bỏ qua. Với mỗi $s u b_r \subseteq r m a s k$ , tìm kiếm nhị phân $T / 2 - r s u m [s u b_r]$ trong mảng của $l m a s k$ .

Độ phức tạp

Thời gian: $O (2^{N / 2} \cdot 3^{N / 2})$ — chấp nhận được với $N \leq 20$ .
Bộ nhớ: $O (3^{N / 2})$

Bình luận

Không có bình luận tại thời điểm này.