or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
\(\Huge \text{🌱 Tin học trẻ 2021 - Vòng khu vực - Bảng B - Kho báu}\)
🔗 Link: https://oj.vnoi.info/problem/tht21_kvb_treasure
📌 Tags:
Backtrack
,Brute-forces
,Meet In The Middle
,DP-Knapsack
,DP-Space Optimized
🛠 Work: 7+ hours
👤 Writer: @matchamachiato, @deptrai2k7, @SPyofgame
👥 Contributor: @eggdacoder2006, @Editorial Slayers Team
📋 Content:
Subtask 1
Ở subtask này, vì \(n \le 12\) nên ta hoàn toàn có thể sinh dãy tam phân hoặc gọi đệ quy như
dfs
để xét từng trường hợp.Vì \(3^{12} = 531441 \le 10^{6}\) nên độ phức tạp \(3^{n}\) có thể chấp nhận được.
Duy_e Code
kazamahoang Code
SPyofgame Code
Bonus:
Nếu bạn nào muốn dùng bitmask để duyệt thay vì sinh tam phân hoặc gọi đệ quy thì có thể xem thêm phần "Duyệt qua tất cả tập con" của vnoi ở đây LINK. Việc này giúp giảm constant time, do đó code sẽ chạy nhanh hơn.
Subtask 2
Hướng dẫn chi tiết của SPyofgame
Đây là subtask được cho nhằm tối ưu thuật toán
back track
ở subtask trước vì với \(n \le 24\) thì ta không thể sinh đủ dãy tam phân có \(n\) phần tử trong thời gian cần thiết được.Nhưng nhận thấy rằng khi ta duyệt qua nhiều dãy tam phân như vậy thì phần kết quả đều có phần chung, đó là vì các biến độc lập nhau nên khi ta chọn sẵn \(k\) phần tử đầu tiên từ tập \(n\) phần tử thì \(n - k\) phần tử còn lại tuy có nhiều dãy thỏa mãn, nhưng đều chỉ có một kết quả là tối ưu nhất.
Để dễ hình dung, đầu tiên ta có các định nghĩa như sau:
Ta có được một thuật toán đơn giản như sau
Nếu chỉ đến đây, ta sẽ có độ phức tạp là \(O(|S| \times |T|)\)
Gọi \(C_k(S)\) là các giá trị \(V(S)\) có \(k = D(S)\) , ta có thể sắp xếp các cặp theo giá trị \(D(S)\) tăng dần để có thể biết được các giá trị \(V(S)\) có cùng \(D(S)\) trong \(O(C_{D(S)}(S))\)
Tuy nhiên độ phức tạp lại thành \(O(|S| \log |S| \times |T| \log |T|)\)
Ta có thể tối ưu bằng cách cố định \(k\), ta cũng dễ biết được
Gọi \(O(F_k(S)) = O\left(C_k(S) \log C_k(S)\right)\) là độ phức tạp khi sắp xếp từng dãy
Lúc này độ phức tạp từ \(O(|S| \log |S| \times |T| \log |T|) = O( \Sigma(F_k(S)) \times \Sigma (F_k(T)))\) thành \(O(\Sigma (F_k(S) \times F_k(T)))\)
Nhìn có vẻ có thêm phần \(O(log)\) thì làm chậm chương trình, nhưng trong trường hợp tổng quát thì nhanh hơn nhiều, và tất nhiên cũng có thể tối ưu để nó cũng nhanh hơn trong mọi trường hợp
Cuối cùng, một bước đơn giản thôi
Vì sau khi sắp xếp các cặp theo \(D(S)\), ta biết các giá trị \(V(S)\) có cùng \(D(S)\) rồi, nên ta cũng có thể tính \(min(V(S))\) trong \(O(1)\) với mọi \(D(S)\)
Lúc này độ phức tạp từ \(O(\Sigma (C_k(S) \times C_k(T)))\) thành \(O( \Sigma(F_k(S)) + \Sigma (F_k(T))) = O(|S| \log |S| + |T| \log |T|)\)
Ta đã tối ưu từ \(O(|S| \times |T|) = O(3^n \times 3^{n - k})\) sang \(O(|S| + |T|) = O(3^n + 3^{n-k})\)
Ta đạt được độ phức tạp tối ưu khi chia dãy sao cho \(|n - k| \leq 1\), khi này \(O(|S| + |T|) = O(3^{\left \lceil n/2 \right \rceil})\)
Đây là subtask được cho nhằm tối ưu thuật toán
back track
ở subtask trước. Với \(n \le 24\) thì ta không thể sinh đủ dãy tam phân có \(n\) phần tử được. Nhưng nhận thấy rằng khi ta duyệt qua nhiều dãy tam phân như vậy thì phần kết quả đều có phần chung. Cụ thể là ta sẽBằng cách chia đôi tập các vật, ta có thể xử lí riêng trên mỗi tập và sau đó
merge
lại.Tiếp cận:
Với \(m = \left \lceil \frac{n}{2} \right \rceil\).
Duy_e Code
kazamahoang Code
SPyofgame Code
Subtask 3
Từ subtask 3, ta phải thay đổi thuật toán bởi vì \(n\) lớn và \(a_i\) nhỏ hơn nhiều so với hai subtask trên.
Một thuật toán có thể dùng đó là
DP-knapsack
hay là quy hoạch động cái túi.Thông thường
DP-knapsack
sẽ lưu một chiều là trọng lượng của túi. Nhưng ở đây ta có hai người nên ta sẽ dùng hai chiều, một để lưu giá trị vật phẩm của Alice, một để lưu giá trị vật phẩm Bob.Tiếp cận:
Gọi
dp[i][V_A][V_B]
là giá trị nhỏ nhất sẽ bỏ ra để Alice nhận số vật phẩm có giá trị làV_A
và Bob nhận được số vật phẩm có giá trị làV_B
khi vật cuối cùng được mua là vật thứi
.Do ban đầu cả hai không có vật phẩm nào nên hàm cơ sở
dp[0][0][0] = 0
.Các hàm còn lại ta khởi tạo bằng
inf
.Nếu hiện tại ta xét đến vật thứ
i
, Alice có số vật phẩm có ước giáV_A
và Bob có số vật phẩm có ước giá
V_B
thì quan hệ giữa các hàm sẽ như sau:Thêm cho Alice một vật phẩm:
dp[i + 1][A_v + v[i + 1]][V_B] = min(dp[i + 1][A_v + v[i + 1]][V_B], dp[i][V_A][V_B])
Thêm cho Bob một vật phẩm:
dp[i + 1][A_v][V_B + v[i + 1]] = min(dp[i + 1][A_v][V_B + v[i + 1]], dp[i][V_A][V_B])
Không thêm cho ai cả:
dp[i + 1][A_v][V_B] = min(dp[i + 1][A_v][V_B], dp[i][V_A][V_B] + v[i + 1])
Tối ưu không gian
Vì quy hoạch động chỉ xét \(f[i + 1]\) dựa trên \(f[i]\) nên những phần \(f[i-1], f[i-2], \dots\) trở xuống ta có thể trực tiếp ghi đè dữ liệu lên
Code:
kazamahoang Code
Subtask 4
Ý tưởng
Từ subtask 3, ta đã biết về cách
DP-knapsack
với hai chiều chứa giá trị, tạm gọi là hai túi. Lúc này nếu dùng cách quy hoạch động trên số lượng trường hợp cần xét ở mỗi vật phẩm \(i\) sẽ là \(W_A \times W_B\), với \(W_A\) và \(W_B\) là trọng lượng tối đa ta sẽ xét ở mỗi túi của \(A\) và \(B\).Rõ ràng là với độ phức tạp lớn như vậy hoàn toàn không thể qua được subtask 4.
Ta có nhận xét: Hai người chia được, khi có thể phân thành ba tập, trong đó có hai tập có chênh lệch giá trị là \(0\) và tập còn lại sẽ là tập bỏ đi.
Từ nhận xét trên, ta biết ở mỗi giai đoạn số tài sản của mỗi người sẽ có một lượng chênh lệch, và ta cần làm lượng này bằng \(0\) đồng thời cực tiểu hóa giá trị tập bỏ đi.
Lúc này ta có thể quy hoạch động theo chênh lệch và số lượng trường hợp cần xét sẽ chỉ còn \(W_A + W_B\) tập giá trị sẽ từ \([-W_B.. W_A]\).
Hướng dẫn giải
Lúc này ta sẽ không quy hoạch động theo giá trị, mà sẽ quy hoạch động theo chênh lệch giữa hai tập giá trị.
Gọi hàm
dp[i][delta]
là giá trị nhỏ nhất của tập bỏ đi khi xét đến phần tử thứi
và chênh lệch giá trị của hai tập còn lại làdelta
.Ở đây
delta = Value_of_Alice - Value_of_Bob
Do ban đầu cả hai người đều không có bất kì vật phẩm nào nên ta có hàm cơ sở:
dp[0][0] = 0
.Các hàm còn lại ta khởi tạo bằng
inf
.Với
dp[i][delta]
, ta có thể thấydp[i + 1][delta + v[i+1]]
,dp[i+1][delta - v[i-1]]
vàdp[i + 1][delta]
sẽ cần dùng tên đến hàmdp[i][delta]
.Ta duyệt
i
từ0
đếnn-1
, phần chuyển dịch (transition) giữa các hàm sẽ như sau:Thêm một phần tử cho Alice:
dp[i + 1][delta + v[i + 1]] = min(dp[i][delta], dp[i + 1][delta + v[i + 1]])
.Thêm một phần tử cho Bob:
dp[i + 1][delta - v[i + 1]] = min(dp[i][delta], dp[i + 1][delta - v[i + 1]])
.Không thêm cho ai, bỏ vào tập để bán:
dp[i + 1][delta] = min(dp[i][delta] + v[i + 1], dp[i + 1][delta])
.Lúc này, kết quả bài toán sẽ là
dp[n][0]
.Một số lưu ý:
vì
delta
có thể âm, nếu ngôn ngữ lập trình không hỗ trợ chỉ số âm thì bạn cần gấp đôi bảng và luôn giữdelta
luôn không âm. Một cách có thể đó là cộng thêm biếnoffset
vàodelta
.Từ cách làm trên, độ phức tạp bộ nhớ sẽ là \(O(n \times 2 \times sum_v)\) và ta sẽ bị quá bộ nhớ. Ta nhận thấy hàm
dp
ở mỗii
chỉ dùng hai tầng là dùng tầngi
để tính tầngi + 1
. Từ đây ta có thể tối ưu bộ nhớ chỉ lưudp[2][2*sum_v]
.Duy_e Code
kazamahoang Code
SPyofgame Code