🔒 Chia kẹo (Contest Practice VNOI 2021 Round 1)

--- tags: Private, LQDOJ, Practice VNOI, Medium Implementation, Brute-forces, DP, DP-bitmask, Greedy, Math, Time Optimization, Space Optimization, SPyogame title: 🔒 Chia kẹo (Contest Practice VNOI 2021 Round 1) author: Editorial-Slayers Team license: Free to use in private but unless required by problem author, contest consent, applicable law or agreed to in writing, editorial distributed under the license is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. Under this license, Editorial-Slayers Team WILL NOT TAKE IN CHARGE FOR the editorial to be published publicly by the third party using this editorial. --- <style> .markdown-body { max-width: 2048px; } </style> $\Huge \text{🔒 Chia kẹo (Contest Practice VNOI 2021 Round 1)}$ ----- ###### 🔗 Link: [https://lqdoj.edu.vn/problem/d13r1sweets](https://lqdoj.edu.vn/problem/d13r1sweets) ###### 📌 Tags: `Medium Implementation`, `Brute-forces`, `DP`, `DP-bitmask`, `Greedy`, `Math`, `Time Optimization`, `Space Optimization` ###### 🛠 Work: At least 14 hours ###### 👤 Writter: @SPyofgame ###### 👥 Contributor: [@Editorial-Slayers Team](https://hackmd.io/@Editorial-Slayers) ###### 📋 Content: [TOC] ----- # Gợi ý giảm bớt trường hợp cần xét > [color=lightgreen] Tags: `Math` Chia $n$ phần tử nguyên dương vào $k$ nhóm sao cho có tổng bằng nhau. Thì nếu tổng của $n$ phần tử là $S$ thì mỗi nhóm phải có tổng $V = \Large \frac{S}{k}$ Vậy $2$ điều kiện đầu tiên là - $S$ chia hết cho $k$ - Số lớn nhất trong dãy $a[]$ không được quá $V$ :::success :::spoiler Code #### Declare ```cpp=46 typedef long long ll; const int LIM = 1e6 + 16; int n, k; ll value; int a[LIM]; int p[LIM]; ``` #### Output ```cpp=53 void output(bool found) { if (!found) return cout << -1, void(); for (int i = 1; i <= n; ++i) cout << p[i] << " "; } ``` #### Call function ```cpp=110 ios::sync_with_stdio(NULL); cin.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; ll sum = 0; bool special = true; for (int i = 1; i <= n; ++i) { sum += a[i]; if (a[i] != i) special = false; } value = sum / k; if (value * k != sum || value < *max_element(a + 1, a + n + 1)) /// Two simplest condition to split to k subsequences { output(false); } ``` ::: ----- ----- ----- ----- ----- # Subtask 1-2 Nhận thấy măc dù $a_i$ khá lớn, nhưng lại có $k, n$ rất nhỏ, nên ta sẽ xử lí dựa trên dữ kiện này ----- ### Trâu trong O(k^n) > [color=lightgreen] Tags: `Brute-forces` Duyệt đệ quy tới độ sâu $[i]$ xét số $a[i]$ thử chia nó vào $1$ trong $k$ nhóm Khi chia vào một nhóm ta tăng tổng lên một lượng bằng $a[i]$ và đánh dấu nhóm tại $[i]$ Khi chia xong nhớ giảm lại tổng của nhóm đó Khi duyệt hết các số $a[i]$ mà tất cả $k$ tổng bằng nhau thì xuất kết quả là nhóm của các $a[i]$ và dừng chương trình Sau khi duyệt hết các trường hợp mà không tồn tại kết quả ta xuất $-1$ ----- ### Trâu trong O(n!) > [color=lightgreen] Tags: `Brute-forces`, `Greedy` Duyệt qua $O(n!)$ hoán vị của các số $a[i]$ Duyệt qua từng phần tử, cộng tới khi nào tổng không còn nhỏ hơn $V$ thì dừng và chia thành một nhóm và tính tiếp nhóm tiếp theo Nếu tính đủ $k$ nhóm có tổng bằng nhau thì xuất kết quả, không thì bỏ qua Nếu tất cả hoán vị không thỏa thì xuất $-1$ ----- ### Quy hoạch động trong O(2^n) > [color=lightgreen] Tags: `DP`, `Greedy` Áp dụng 2 cách trên vào một thành một thuật $O(2^n \times n!)$ và sử dụng quy hoạch động để giảm bớt còn $O(2^n)$ Gọi đệ quy $f(i, S, k)$ là xét đến nhóm $[c]$ có tổng hiện tại là $[k]$ và tập các nhóm đã chọn là $[S]$ Khi $i > n$, ta đã duyệt hết các phần tử trong mảng, nên nếu thu được số nhóm là $k$ thì xuất kết quả Ngược lại, duyệt qua từng phần tử $x$ chưa có trong $S$, nếu tổng $k + x \geq V$ thì xét tới $f(i + 1, S \cup \{i\}, k = 0)$$ Nếu tất cả các trường hợp không thỏa thì xuất $-1$ ----- ### Tối ưu hóa - Dừng chương trình ngay sau khi xuất kết quả - Tổng của một nhóm quá $V$ thì dừng đi sâu vào nhánh này - Dùng bitmask để lưu thay vì sài tập $S$ để tối ưu cả không gian lẫn bộ nhớ lên nhiều lần - Nhờ cache friendly, có thể dung mảng boolean để chạy nhanh hơn vài lần so với mảng $[int]$ - Vì chỉ lưu theo bit, có thể dùng bitset để giảm bộ nhớ xuống $32$ lần ----- ### Code > **Time:** $O(k \times 2^n) = O(n \times 2^n) = O(2^n)$ > **Space:** $O(2^n)$ > **Algo:** DP-bitmask, Greedy :::success :::spoiler Code #### Declare ```cpp=46 typedef long long ll; const int LIM = 1e6 + 16; int n, k; ll value; int a[LIM]; int p[LIM]; ``` ```cpp=60 bool g[1 << 20]; bool f[1 << 20]; ``` #### Solve ```cpp=+ bool magic(int i = 1, int mask = 0, ll sum = 0) { if (i > k) return true; if (g[mask >> 1]) return f[mask >> 1]; else g[mask >> 1] = true; bool &res = f[mask >> 1]; for (int j = 1; j <= n; ++j) if (!(mask >> j & 1)) { if (sum + a[j] < value && magic(i + 0, mask | (1 << j), sum + a[j])) { p[j] = i; return res = true; } if (sum + a[j] == value && magic(i + 1, mask | (1 << j), 0)) { p[j] = i; return res = true; } } return res = false; } ``` #### Call function ```cpp=134 else if (n <= 20) /// O(2^n) | can be improved to O(2^(n/2) { memset(g, false, sizeof(g[0]) * (1 << n)); output(magic()); } ``` ::: ----- ### Bonus - Bạn có thể giải bài này với $n \leq 40$ hay không ? ----- ----- ----- ----- ----- # Subtask 3 Vì $k = 3$, ta chia dãy làm 3 nhóm có các tổng là $A, B, C$, ban đầu $A = B = C = 0$ Việc chia nhóm kết thúc khi $A = B = C = V = \Large \frac{S}{3}$ Nhận thấy $n$ với $a_i$ nhỏ tạo tổng không quá lớn nên ta sẽ xử lí trên dữ kiện này ----- ### Trâu trong O(3^n) > [color=lightgreen] Tags: `Brute-forces` Vì bài này cả $n$ lẫn $a[i]$ đều nhỏ nên tổng cho ra cũng nhỏ. Nên ta sẽ thử đệ quy $f(i, A, B, C)$ là xét đền phần tử thứ $[i]$, nhóm thứ nhất có tổng $[A]$, nhóm thứ hai có tổng $[B]$, nhóm thứ ba có tổng là $[C]$ Ta xét $3$ trường hợp - Cho $a[i]$ vào nhóm một, ta xét tiếp $f(i + 1, A + a[i], B, C)$ - Cho $a[i]$ vào nhóm hai, ta xét tiếp $f(i + 1, A, B + a[i], C)$ - Cho $a[i]$ vào nhóm ba, ta xét tiếp $f(i + 1, A, B, C + a[i])$ Khi $i > n$ tức là ta đã xét hết, và kiểm tra nếu $3$ tổng bằng nhau thì xuất kết quả Nếu không có kết quả được tìm thấy ta xuất $-1$ Vì mỗi số có $3$ cách chọn chia tập, mà có $n$ số cần chia, vậy độ phức tạp $O(3^n)$ ----- ### Quy hoạch động trong O(n * S^2) > [color=lightgreen] Tags: `Brute-forces`, `DP` Lúc này để tránh độ phức tạp lên mức lũy thừa, ta sẽ cho một mảng nhớ, để các trạng thái đã xét không còn xét lại nữa Nhưng số trường hợp cách này lại lên tới $O\left(n \times S^3\right) = O\left(n^4 \times max(a)^3\right)$ sẽ chạy rất chậm, chưa kể bộ nhớ quá lớn mà còn phải lưu phần tổng có vẻ không ăn điểm như $O(3^n)$ Ta để ý là vì kiểu gì cũng phải chia dãy làm ba tập, nên không mất tính tổng quát giả sử ta chọn được tổng $A, B$ thì phần còn lại ta cho hết vào $C$. Khi này ta có $C = V - A - B$ Nhận thấy nếu ta xét việc đệ quy $f(i, A, B)$ là xét đền phần tử thứ $[i]$, nhóm thứ nhất có tổng $[A]$, nhóm thứ hai có tổng $[B]$. Thì ta xét $3$ trường hợp - Cho $a[i]$ vào nhóm một, ta xét tiếp $f(i + 1, A + a[i], B)$ - Cho $a[i]$ vào nhóm hai, ta xét tiếp $f(i + 1, A, B + a[i])$ - Cho $a[i]$ vào nhóm ba, ta xét tiếp $f(i + 1, A, B)$ Độ phức tạp lúc này còn $O\left(n \times S^2\right) = O\left(n^3 \times max(a)^2\right)$ Độ phức tạp tổng quát là $O\left(k \times n \times S^{k-1}\right) = O\left(k \times n^k \times max(a)^{k-1}\right)$ ----- ### Tối ưu hóa lên O(n * S^2 / 567) > [color=lightgreen] Tags: `Brute-forces`, `DP`, `Time Optimization`, `Space Optimization` Nhận thấy là nếu mà tổng $A$ hoặc tổng $B$ quá lớn thì sẽ không thể chia dãy đều thành $3$ phần được. Nên khi $A > V$ hoặc $B > V$ thì không xét tới nữa. Số trạng thái giảm đi $9$ lần vì mỗi tổng chỉ cần lưu tới tối đa $\Large \frac{S}{3}$. Nhưng thực tế lại loại đi rất nhiều trường hợp Nhận thấy là không mất tính tổng quát ta có thể sắp xếp $A, B, C$ theo thứ tự tăng dần để giảm bớt trường hợp cần xét. Số trạng thái giảm đi $6$ lần vì mỗi tổ hợp chỉ xét $1$ lần. Tuy vậy, phải cài khéo để tránh độ phức tạp không gian còn lơn hơn cả thời gian. Nhưng vì số $6$ khá nhỏ so với việc tăng thêm phép nhân nên đổi lại của việc này thường dẫn tới code chạy chậm hơn do vấn đề hằng số Mình có thể dùng mảng $[bool]$ để nhận hằng số và bộ nhớ nhỏ hơn vài lần so với $[int]$, và trong C++ mình có thể sài bitset để tối ưu không gian lưu trữ giảm đi $O(wordsize) = O(32)$ lần Vậy độ phức tạp lúc này còn $O(n * S^2)$ với hằng số $c_0 = \Large \frac{3 \times c}{9 \times 6 \times 32} \normalsize = \frac{c}{576}$ đủ để qua bài này Độ phức tạp tổng quát $O\left(n \times \left(\Large \frac{S}{k}\right)^{k-1} \normalsize \times \Large \frac{k^2}{32k!} \right)$ Độ phức tạp thực tế không tính chi tiết được ----- ### Code > **Time:** $O(\frac{n \times S^2}{3 \times 32})$ > **Space:** $O(\frac{n \times S^2}{9 \times 32})$ > **Algo:** DP-bitmask, Brute-forces, Time Optimization, Space Optimization > [color=lightgreen] :::success :::spoiler Code #### Declare ```cpp=46 typedef long long ll; const int LIM = 1e6 + 16; int n, k; ll value; int a[LIM]; int p[LIM]; ``` ```cpp=93 bitset<3335> T[101][3335]; bitset<3335> M[101][3335]; ``` #### Solve ```cpp=+ bool magic(int i, int x, int y, int z) { if (i > n) return (x == y) && (y == z) && (z == value); if (x > value || y > value || z > value) return false; if (T[i][x][y]) return M[i][x][y]; else T[i][x][y] = true; if (magic(i + 1, x + a[i], y, z)) { p[i] = 1; return M[i][x][y] = true; } if (magic(i + 1, x, y + a[i], z)) { p[i] = 2; return M[i][x][y] = true; } if (magic(i + 1, x, y, z + a[i])) { p[i] = 3; return M[i][x][y] = true; } return M[i][x][y] = false; } ``` #### Call Function ```cpp=139 else /// O(n * (sum / k) ^ (k - 1) * k / 32) | can be improved to O(n * (sum / k) ^ (k - 1) / k! / 64) { memset(p, -1, sizeof(p[0]) * (n + 1)); output(magic(1, 0, 0, 0)); } ``` ::: ----- ### Bonus - Không quan tâm tới độ phức tạp, bạn có thể xử lí với trường hợp $k$ tổng quát không ? ----- ----- ----- ----- ----- # Subtask 4-5 ----- ### Thuật toán tham O(n * k) > [color=lightgreen] Tags: `Greedy`, `Brute-forces` Duyệt qua từng nhóm $c = 1 \dots k$, khởi tạo tổng $X = V$ - Duyệt qua từng phần tử $t$ từ $n$ về $1$ - Nếu $t$ đã được đánh dấu thì bỏ qua - Ngược lại đánh dấu $t$, gán nhóm tại $t$ là $c$, giảm tổng $X := X - t$ - Nếu $X > 0$ sau khi duyệt thì sẽ không tồn tại cách chọn thỏa mãn Nếu sau khi duyệt xong đánh dấu đủ $n$ phần tử thì xuất kết quả ngược lại xuất $-1$ ----- ### Chứng minh - Dựa trên [toán học](https://math.stackexchange.com/questions/1438911/partition-of-1-2-n-into-subsets-with-equal-sums), ta thấy kết quả sẽ luôn xuất hiện khi tổng của $n$ phần tử có thể chia thành tổng của $k$ số nguyên bằng nhau - Vì mỗi số thuộc về duy nhất một nhóm, mà qua việc duyệt này mỗi nhóm mình chỉ lấy các phần tử tốt nhất với nó, cũng như việc các phần tử đó sẽ không có nhóm khác tốt hơn mà không làm các phần tử chưa đánh dấu không bắt cặp tối ưu với các nhóm còn lại - Bằng việc duyệt từ số to nhất về, các nhóm không thể lấy trùng cùng một phần tử tối ưu, không mất tính tổng quát xét một nhóm bất kì sẽ có các phần tử tốt nhất sẽ bị đánh dấu dần theo nhóm đó, nên việc chia nhóm không khả thi - Việc chứng minh sâu hơn cho thuật toán tham xin để lại cho bạn đọc vì cơ sở toán qúa phức tạp để có thể trình bày một cách dễ hình dung nhất ----- ### Tối ưu theo từng nhóm O(k * f(n)) > [color=lightgreen] Tags: `Greedy`, `Data Structure`, `Binary Search` Mục tiêu ta là tìm phần tử lớn nhất nhỏ hơn $X$ mà chưa được đánh dấu - Duyệt như trên sẽ mất $O(n)$ - Duyệt chia căn sẽ mất $O(\sqrt{n})$ - Sử dụng cấu trúc dữ liệu và chặt nhị phân vị trí cùng với việc tính tổng trên cây để tìm phần tử mỗi lần chặt sẽ mất $O(\log^3n)$ cho mỗi nhóm - Sử dụng cấu trúc dữ liệu và chặt nhị phân tìm kiếm thì sẽ mất $O(\log^2n)$ cho mỗi nhóm - Sử dụng cấu trúc dữ liệu và di chuyển trên cây thì sẽ mất $O(\log n)$ cho mỗi nhóm - Sử dụng cấu trúc dữ liệu DSU có thể giảm xuống còn $O(\alpha(n))$ - Không rõ có cấu trúc dữ liệu có thể tìm trong $\Theta(n + k)$ hay không ----- ### Tối ưu theo từng phần tử O(n * f(k)) > [color=lightgreen] Tags: `Greedy`, `Data Structure`, `Math` Tương tự thuật toán trên, nhưng ta sẽ duyệt qua từng phần tử $t$ từ lớn về bé và tìm nhóm hiện tại đang giữ tổng lớn nhất - Duyệt tương tự trâu sẽ mất $O(k)$ - Sử dụng cây chia căn sẽ mất $O(\sqrt{k})$ - Sử dụng cây phân đoạn hoặc heap sẽ mất $O(\log k)$ Sử dụng [toán học](https://math.stackexchange.com/questions/1438911/partition-of-1-2-n-into-subsets-with-equal-sums) ta có thể chia nhóm trong $O(n + k)$ > Trường hợp tổng quát xin bạn đọc tự chứng minh như một bài tập ----- ### Code > **Time:** $O(n \times k)$ > **Space:** $O(n)$ > **Algo:** > [color=lightgreen] :::success :::spoiler Code #### Declare ```cpp=46 typedef long long ll; const int LIM = 1e6 + 16; int n, k; ll value; int a[LIM]; int p[LIM]; ``` #### Solve ```cpp=78 bool greedy() { memset(p, -1, sizeof(p[0]) * (n + 1)); for (int t = 1; t <= k; ++t) { ll left = value; for (int i = n; i >= 1; --i) if (p[i] == -1 && left >= i) p[i] = t, left -= i; if (left) return false; } return true; } ``` #### Call Function ```cpp=118 bool special = true; for (int i = 1; i <= n; ++i) { sum += a[i]; if (a[i] != i) special = false; } ``` ```cpp=139 else if (special) /// O(n * k) | can be improved to O(n log k) { output(greedy()); } ``` ::: ----- ### Bonus Bạn có thể chứng minh tính đúng đắn của $3$ thuật kể trên không ----- # Code tổng thể > **Time:** $O(subtask)$ > **Space:** $O(2^n + \frac{n \times S^2}{9 \times 32})$ > **Algo:** Medium Implementation, Brute-forces, DP, DP-bitmask, Greedy, Math, Time Optimization, Space Optimization > [color=lightgreen] :::success :::spoiler Code #### Author Comment ```cpp= /// @Author: SPyofgame /// @License: Free to use /// @Problem: K-partition problem in special cases /// @Submit: https://lqdoj.edu.vn/problem/d13r1sweets /// /// @Algorithm: (n <= 20) dp bitmask O(2^n) /// (a[i] = i) greedy O(n * k) /// (k small) heuristical bruteforces with at most O(n * (sum / k) ^ (k - 1) * k / 32) /// /// @Improvement: (n <= 20) can be improved to O(2^(n/2)) using random algorithm /// (a[i] = i) can be improved to O(n log k) using data structure /// (k small) can be improved to at most O(n * (sum / k) ^ (k - 1) / k! / 64) using heuristical methods /// /// @Editorial: (n <= 20) /// With selected number in mask and current sum /// Try to build furthur then limit /// Switch to next sum when current sum is filled /// The problem can be generalized to (m) different sum (k) partions of (n) elements /// With the same idea and complexity /// The solution can be impoved using random algorithm but kinda complex /// /// @Editorial: (a[i] = i) /// Greedily take from higher element to smaller element if possible /// There is math proof for this but it is kinda complex so skip it /// The solution to O(n + k) is unknown but O(n log k) can be achieved using data structure /// /// @Editorial: (k small) /// Literally brute-forces /// Using memoization to avoid exponential complexity algorithm /// Though there is the fact that the algorithm itself is NP for general K /// But K is bounded, hence a P algorithm is achieved /// You can boost memoization with hashmap, bitset, boolean /// Faster algorithm is unknown, but this complexity is as the same as O(n * (sum / k) ^ (k - 1) / k! / 64) /// /// @General: There are many anytime algorithms, but they are either not-that-accuracy /// or not-that-fast /// ``` #### Declare ```cpp=+ #include <algorithm> #include <iostream> #include <cstring> #include <bitset> using namespace std; typedef long long ll; const int LIM = 1e6 + 16; int n, k; ll value; int a[LIM]; int p[LIM]; ``` #### Output Function ```cpp=+ void output(bool found) { if (!found) return cout << -1, void(); for (int i = 1; i <= n; ++i) cout << p[i] << " "; } ``` #### DP Bitmask ```cpp=+ bool g[1 << 20]; bool f[1 << 20]; bool magic(int i = 1, int mask = 0, ll sum = 0) { if (i > k) return true; if (g[mask >> 1]) return f[mask >> 1]; else g[mask >> 1] = true; bool &res = f[mask >> 1]; for (int j = 1; j <= n; ++j) if (!(mask >> j & 1)) { if (sum + a[j] < value && magic(i + 0, mask | (1 << j), sum + a[j])) { p[j] = i; return res = true; } if (sum + a[j] == value && magic(i + 1, mask | (1 << j), 0)) { p[j] = i; return res = true; } } return res = false; } ``` #### Greedy ```cpp=+ bool greedy() { memset(p, -1, sizeof(p[0]) * (n + 1)); for (int t = 1; t <= k; ++t) { ll left = value; for (int i = n; i >= 1; --i) if (p[i] == -1 && left >= i) p[i] = t, left -= i; if (left) return false; } return true; } ``` #### DP Brute-forces ```cpp=+ bitset<3335> T[101][3335]; bitset<3335> M[101][3335]; bool magic(int i, int x, int y, int z) { if (i > n) return (x == y) && (y == z) && (z == value); if (x > value || y > value || z > value) return false; if (T[i][x][y]) return M[i][x][y]; else T[i][x][y] = true; if (magic(i + 1, x + a[i], y, z)) { p[i] = 1; return M[i][x][y] = true; } if (magic(i + 1, x, y + a[i], z)) { p[i] = 2; return M[i][x][y] = true; } if (magic(i + 1, x, y, z + a[i])) { p[i] = 3; return M[i][x][y] = true; } return M[i][x][y] = false; } ``` #### Main ```cpp=+ int main() { ios::sync_with_stdio(NULL); cin.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; ll sum = 0; bool special = true; for (int i = 1; i <= n; ++i) { sum += a[i]; if (a[i] != i) special = false; } value = sum / k; if (value * k != sum || value < *max_element(a + 1, a + n + 1)) /// Two simplest condition to split to k subsequences { output(false); } else if (special) /// O(n * k) | can be improved to O(n log k) { output(greedy()); } else if (n <= 20) /// O(2^n) | can be improved to O(2^(n/2) { memset(g, false, sizeof(g[0]) * (1 << n)); output(magic()); } else /// O(n * (sum / k) ^ (k - 1) * k / 32) | can be improved to O(n * (sum / k) ^ (k - 1) / k! / 64) { memset(p, -1, sizeof(p[0]) * (n + 1)); output(magic(1, 0, 0, 0)); } return 0; } ``` :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.