Chia Ruộng
Đề bài
Trong làng Omega có 1 phú ông rất giàu có. Tài sản của ông rất nhiều trâu, bò, ruộng vườn. Một hôm ông gọi 3 người con đã đến tuổi trưởng thành đến ông chia cho một số ruộng để làm ăn. Ông có hàng trăm mẫu ruộng nhưng ông chỉ chọn $n$ thửa ruộng để chia, thửa thứ $i$ có diện tích $a_i$ m². Hỏi rằng phú ông có bao nhiêu cách chia đều $n$ thửa ruộng cho 3 con sao cho các thửa ruộng được chia phải giữ nguyên diện tích.
Input:
- Dòng 1: ghi số $n$ là số thửa ruộng của phú ông đem chia $(1 \le n \le 20)$.
- Dòng 2: ghi các số $a_i$ là diện tích của thửa ruộng thứ $i$ $(100 \le a_i \le 5000)$.
Output:
- Dòng thứ nhất ghi số cách chia, nếu không thể chia được thì ghi $-1$.
- Các dòng sau trong trường hợp chia được, mỗi dòng là 01 cách chia với quy ước người thứ nhất có tên là "A", người thứ hai có tên là "B", người thứ ba có tên là "C" và phải tương ứng với thứ tự của các thửa ruộng được chia.
Lưu ý: Nếu có cách chia thì in ra các cách chia tăng dần theo thứ tự từ điển. Như trong ví dụ đề cho các chuỗi trên từng dòng theo thứ tự từ điển: AABBC < AACCB < BBAAC < BBCCA < CCAAB < CCBBA.
Subtask:
- 40% số test đầu tiên có $n \le 15$.
- 60% số test còn lại không có giới hạn gì thêm.
5
100 200 250 50 3006
AABBC
AACCB
BBAAC
BBCCA
CCAAB
CCBBAGiải thích ví dụ: tổng diện tích là $100 + 200 + 250 + 50 + 300$ $= 900$, mỗi người con phải nhận đúng $300$. Ví dụ cách AABBC: A nhận $100 + 200$, B nhận $250 + 50$, C nhận $300$.
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 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Vét cạnSinh hết dãy tam phân – O(N · 3^N) là TLE
Với bài chia đất này nếu làm theo kiểu sinh ra các dãy tam phân (do có 3 trường hợp: mỗi thửa ruộng giao cho A, B hoặc C), thì liệt kê ra hết các dãy tam phân rồi cứ 0 là ứng với thằng A, 1 là ứng với thằng B, 2 là ứng với thằng C, như thế tính tổng từng thằng xem trường hợp nào thỏa mãn thì đưa vào đáp án.
Nếu làm như thế độ phức tạp sẽ là $O(N \cdot 3^N)$. Với $N$ tối đa $20$ thì $20 \cdot 3^{20} = 69\,735\,688\,020$, xem như gần 70 tỷ, như thế chắc chắn sẽ TLE rồi vì đã vượt quá ngưỡng $10^8$ (tức là 100 triệu) phép tính của 1 giây.
Thì bài này cũng vẫn làm theo tư tưởng xét dãy tam phân nhưng phải kết hợp thêm với kỹ thuật meet in the middle hay còn gọi là phân đôi tập để tối ưu hóa thêm.
Kiến thứcKỹ thuật Meet in the middle (phân đôi tập)
Em có thể tham khảo thêm bài viết của GeeksforGeeks hoặc bài viết mới của VNOI Wiki về kỹ thuật này.
Em có thể hiểu đại khái như sau: giả sử bài toán cho $N = 20$ thì hãy tách ra làm 2 phần với mỗi phần có $N = 10$, vậy nếu dùng dãy tam phân ta sẽ có $3^{10}$ dãy bên này kết nối với $3^{10}$ dãy bên kia. Em sẽ hiểu rằng cứ mỗi dãy trong $3^{10}$ dãy bên này sẽ xét nó với toàn bộ $3^{10}$ dãy bên kia.
Nhìn lại bài "tiền tệ" quen thuộc
Ví dụ trước đó anh nhớ em đã từng giải bài toán tiền tệ: Bà mẹ có 2 người con là A và B và cần chia $N$ tờ tiền $(N \le 20)$ cho 2 người con sao cho tổng tiền mỗi người con nhận được đều bằng nhau, yêu cầu in ra chi tiết tất cả các cách có thể chia. Test ví dụ đề cho:
6
1 2 2 5 10 104
A A A B A B
A A A B B A
B B B A A B
B B B A B AThì có phải là em giải quyết bằng cách sinh ra tất cả các dãy nhị phân có chiều dài $N$, bài cho $N$ tối đa $20$ nên tổng cộng sẽ có $2^{20} = 1\,048\,576$ (hơn 1 triệu) dãy nhị phân, và như thế em sẽ xét vào từng dãy, nếu tổng tiền tại các vị trí số 0 bằng tổng tiền tại các vị trí số 1 thì đó là 1 đáp án thỏa mãn. Tính ra độ phức tạp sẽ là $O(N \cdot 2^N)$, khi $N = 20$ thì sẽ là $20 \cdot 2^{20}$, hơn 20 triệu thôi và vẫn nhỏ hơn ngưỡng $10^8$ của 1 giây nên không sợ bị TLE.
Thì nếu bài tiền tệ này mà em ứng dụng kỹ thuật phân đôi tập vào cũng sẽ giúp chạy nhanh hơn nha. Nhìn lại test ví dụ $N = 6$, chia đôi ra tức là $6 / 2 = 3$, tức là mỗi nửa có $2^3 = 8$ dãy nhị phân: 000, 001, 010, 011, 100, 101, 110, 111. Cứ với 1 dãy bên này sẽ xét với toàn bộ 8 dãy bên kia:
000|000 000|001 000|010 000|011 000|100 000|101 000|110 000|111001|000 001|001 001|010 001|011 001|100 001|101 001|110 001|111010|000 010|001 010|010 010|011 010|100 010|101 010|110 010|111…và cứ thế tới dãy 111 bên này.
Thì khi phân ra làm 2 như vậy, với 1 nửa bên kia em lưu các kết quả vào map và em chỉ việc xét 1 nửa bên này, rồi ứng với từng phần tử của 1 nửa bên này em check vào map để xét với bên kia. Như thế tính ra độ phức tạp thay vì $O(2^N)$ thì chỉ còn $O(2^{N/2} \cdot \log(2^{N/2}))$, tối ưu hơn rất nhiều:
| $N = 20$ | Vét cạn | Phân đôi tập |
|---|---|---|
| Bài tiền tệ (nhị phân) | $2^{20} = 1\,048\,576$ | $2^{10} \cdot \log_2(2^{10}) = 10\,240$ |
| Bài chia ruộng (tam phân) | $20 \cdot 3^{20} \approx 70$ tỷ | $10 \cdot 3^{10} \cdot \log_2(3^{10})$ $\approx 9\,359\,045$ |
Em thấy nhanh hơn cả 100 lần không? Với bài chia ruộng chỉ cần tầm 9 triệu mấy phép tính thì yên tâm AC trong 1 giây. Cái kỹ thuật phân đôi tập này rất hay, em tìm hiểu rồi ứng dụng vào bài chia ruộng nhé.
Ý tưởngÁp dụng vào bài chia ruộng
Để anh nói cụ thể hơn ở bài chia đất này như sau, đầu tiên em chia đôi $n$ ra: $n1 = n / 2$, $n2 = n - n1$. Em tạo ra các dãy tam phân có chiều dài $n1$ và $n2$, quy ước theo ABC cho dễ đi ha. Ví dụ $n = 5$ thì $n1 = 2$, $n2 = 3$: có $3^2 = 9$ dãy cho nửa đầu và $3^3 = 27$ dãy cho nửa sau:
AA AB AC BA BB BC CA CB CCAAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCCEm tạo ra cấu trúc Key có 3 thành phần là sumA, sumB, sumC. Khi xét các dãy ứng với $n2$ thì em phải hiểu là nó ứng với $n2$ phần tử cuối của mảng. Ví dụ test đề có $n = 5$ thì mảng $a$ có các vị trí $a[0],$ $a[1],$ $a[2],$ $a[3],$ $a[4]$, khi xét dãy $n2 = 3$ phần tử cuối mà giả sử dãy là CAB thì có nghĩa là: chọn $a[2]$ cho thằng C, chọn $a[3]$ cho thằng A, chọn $a[4]$ cho thằng B. Khi đó $sumA = 50$, $sumB = 300$, $sumC = 250$.
Cứ thế em tạo ra cái hash table lưu hết trạng thái Key{sumA, sumB, sumC} của các dãy xét ra, và value của nó chính là (danh sách) chuỗi trạng thái của dãy, ví dụ khi xét "CAB" thì: key = {50, 300, 250} và value chứa "CAB".
Gọi $sum$ là tổng các phần tử của mảng, nếu thấy $sum$ không chia hết cho 3 thì ta kết luận $-1$ ngay, còn nếu chia hết cho 3 thì ta tính $sum$ /= 3 (phần mỗi người con phải nhận). Sau khi xét hết toàn bộ $3^{n2}$ dãy tam phân, em quay lại sinh ra $3^{n1}$ dãy tam phân và cũng tính ra được $\{sumA, sumB, sumC\}$ của từng dãy. Nếu $sumA \le sum$, $sumB \le sum$ và $sumC \le sum$ thì mới thỏa, khi đó ta tìm kiếm trong hash table xem có tồn tại các dãy mà tại đó
và lấy value của nó ra ghép với chuỗi dãy tam phân của $n1$ thì đó là 1 đáp án, cứ thế đưa hết các đáp án vào vector, sau cùng in ra nó.
AA…A tới CC…C nên chúng xuất hiện theo đúng thứ tự từ điển. Nửa đầu $s1$ được duyệt theo thứ tự từ điển, và với mỗi $s1$ thì các chuỗi nửa sau trong cùng 1 value cũng được thêm vào theo thứ tự từ điển, nên chuỗi ghép $s1 + s2$ đã tăng dần sẵn, không cần sắp xếp lại.Em nhập diện tích các thửa ruộng rồi bấm Tiếp để xem 2 giai đoạn: lưu nửa sau vào hash table, rồi duyệt nửa đầu và tra khóa còn thiếu:
100%Code Meet in the middle + unordered_map với Key tự định nghĩa
Nó chỉ khó ở chỗ khi em dùng hash table thì dữ liệu hiện tại có Key là struct có 3 thành phần số nguyên, lúc này em phải tự cài đặt cơ chế hash cho nó. Nếu chỉ có 1 số nguyên thì nó còn biết hash, nhưng ở đây nó đang là 1 cấu trúc có 3 thành phần số nguyên thì nó sẽ không biết hash thế nào. Giải pháp ở đây hoặc là em tự tạo hash table, hoặc em dùng hash table có trong thư viện thì phải chỉ định rõ phép so sánh bằng (operator==) và hàm hash (KeyHasher) cho nó, em có thể tham khảo tại câu hỏi này trên StackOverflow.
Đó thì toàn bộ ý tưởng là như vậy, anh gửi luôn source code của anh đã làm đúng theo ý tưởng anh nói ở trên để nếu em không làm được thì tham khảo, đã nộp thành công trên web. Và cũng nói rõ là code này chưa có clean đâu nha em, vì em xem sẽ thấy có rất nhiều phần code bị trùng nhau, nếu chia hàm rồi gọi lại nhìn sẽ gọn gàng hơn nhưng anh tranh thủ code nhanh ra nên để hết code trong hàm main. Bản Python thì dùng luôn dict với key là tuple (sumA, sumB, sumC), Python tự hash được tuple nên đỡ phải cài đặt.
#include <bits/stdc++.h>
using namespace std;
struct Key
{
int first, second, third;
bool operator==(const Key &other) const{
return first == other.first && second == other.second && third == other.third;
}
};
// https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key
struct KeyHasher
{
size_t operator()(const Key& k) const
{
return ((hash<int>()(k.first) ^ (hash<int>()(k.second) << 1)) >> 1) ^ (hash<int>()(k.third) << 1);
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int a[n], sum = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
sum += a[i];
}
if(sum % 3 != 0){
cout << -1;
return 0;
}
sum /= 3;
vector<string> res;
int n1 = n / 2;
int n2 = n - n1;
unordered_map<Key, vector<string>, KeyHasher> mp;
string s(n2, 'A');
bool flag = true;
while(flag){
flag = false;
int sumA = 0, sumB = 0, sumC = 0;
for(int i = 0; i < n2; ++i){
if(s[i] == 'A'){
sumA += a[n1 + i];
}
else if(s[i] == 'B'){
sumB += a[n1 + i];
}
else{
sumC += a[n1 + i];
}
}
if(sumA <= sum && sumB <= sum && sumC <= sum){
mp[{sumA, sumB, sumC}].push_back(s);
}
for(int i = n2 - 1; i >= 0; --i){
if(s[i] != 'C'){
s[i]++;
flag = true;
for(int j = i + 1; j < n2; ++j){
s[j] = 'A';
}
break;
}
}
}
string s1(n1, 'A');
flag = true;
while(flag){
flag = false;
int sumA = 0, sumB = 0, sumC = 0;
for(int i = 0; i < n1; ++i){
if(s1[i] == 'A'){
sumA += a[i];
}
else if(s1[i] == 'B'){
sumB += a[i];
}
else{
sumC += a[i];
}
}
if(sumA <= sum && sumB <= sum && sumC <= sum){
auto it = mp.find({sum - sumA, sum - sumB, sum - sumC});
if(it != mp.end()){
for(int i = 0; i < it->second.size(); ++i){
res.push_back(s1 + it->second[i]);
}
}
}
for(int i = n1 - 1; i >= 0; --i){
if(s1[i] != 'C'){
s1[i]++;
flag = true;
for(int j = i + 1; j < n1; ++j){
s1[j] = 'A';
}
break;
}
}
}
if(res.size() == 0){
cout << -1;
}
else{
cout << res.size();
for(int i = 0; i < res.size(); ++i){
cout << '\n' << res[i];
}
}
return 0;
}import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
if s % 3 != 0:
print(-1)
sys.exit(0)
target = s // 3
res = []
n1 = n // 2
n2 = n - n1
# sinh n2 phần tử
mp = {} # key: (sumA, sumB, sumC) -> list các chuỗi
s2 = ['A'] * n2
flag = True
while flag:
flag = False
sumA = sumB = sumC = 0
for i in range(n2):
if s2[i] == 'A':
sumA += a[n1 + i]
elif s2[i] == 'B':
sumB += a[n1 + i]
else:
sumC += a[n1 + i]
if sumA <= target and sumB <= target and sumC <= target:
key = (sumA, sumB, sumC)
mp.setdefault(key, []).append(''.join(s2))
# tăng chuỗi base-3 A/B/C
for i in range(n2 - 1, -1, -1):
if s2[i] != 'C':
s2[i] = chr(ord(s2[i]) + 1) # A→B, B→C
flag = True
for j in range(i + 1, n2):
s2[j] = 'A'
break
# sinh n1 phần tử
s1 = ['A'] * n1
flag = True
while flag:
flag = False
sumA = sumB = sumC = 0
for i in range(n1):
if s1[i] == 'A':
sumA += a[i]
elif s1[i] == 'B':
sumB += a[i]
else:
sumC += a[i]
if sumA <= target and sumB <= target and sumC <= target:
need = (target - sumA, target - sumB, target - sumC)
if need in mp:
pre = ''.join(s1)
for tail in mp[need]:
res.append(pre + tail)
# tăng chuỗi base-3 A/B/C
for i in range(n1 - 1, -1, -1):
if s1[i] != 'C':
s1[i] = chr(ord(s1[i]) + 1)
flag = True
for j in range(i + 1, n1):
s1[j] = 'A'
break
if not res:
print(-1)
else:
print(len(res))
for r in res:
print(r)Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), bài này có thể phải in ra rất nhiều dòng đáp án nên ta hãy để 2 dòng này vào để chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.- Sinh dãy tam phân kế tiếp: duyệt từ cuối chuỗi về đầu, gặp ký tự đầu tiên khác
'C'thì tăng nó lên 1 ('A'→'B','B'→'C'), các ký tự phía sau đặt lại hết thành'A', giống hệt phép cộng 1 trong hệ cơ số 3. Nếu cả chuỗi toàn'C'thìflagvẫn làfalse, vòngwhilekết thúc. mp[{sumA, sumB, sumC}]có value làvector<string>vì nhiều dãy nửa sau có thể cho ra cùng 1 bộ tổng. Chỉ lưu những dãy có cả 3 tổng đều $\le sum$, các dãy khác chắc chắn không ghép được.- Khi $n = 1$ thì $n1 = 0$, chuỗi
s1rỗng vẫn được xét đúng 1 lần (vòngwhilechạy 1 lần với 3 tổng bằng 0) nên code vẫn đúng.
Sinh $3^{n2}$ dãy, mỗi dãy tốn $O(n2)$ để tính tổng và $O(1)$ trung bình để thêm vào hash table; tương tự $3^{n1}$ dãy nửa đầu, mỗi dãy tra hash table $O(1)$. Tổng cộng cỡ $O(N \cdot 3^{N/2})$ cộng với số dòng đáp án phải in ra. Với $N = 20$ thì $20 \cdot 3^{10} \approx 1{,}2 \cdot 10^6$ phép tính, nhẹ nhàng.
Nhận xét
Đăng nhận xét