Parallel Courses II (LeetCode 1494)
Đề bài
1494. Parallel Courses II – Các khóa học song song II (LeetCode, độ khó Hard)
Cho một số nguyên $n$, cho biết có $n$ khóa học được đánh số từ $1$ tới $n$. Cho thêm mảng relations trong đó relations[i] = [prevCoursei, nextCoursei] biểu diễn quan hệ tiên quyết giữa khóa prevCoursei và khóa nextCoursei: khóa prevCoursei phải được học trước khóa nextCoursei. Ngoài ra còn cho số nguyên $k$.
Trong một học kỳ, bạn có thể học tối đa $k$ khóa học, miễn là với mỗi khóa đang học, bạn đã học xong tất cả các khóa tiên quyết của nó ở các học kỳ trước.
Hãy trả về số học kỳ ít nhất cần thiết để học hết tất cả các khóa học. Dữ liệu được sinh sao cho luôn có thể học hết mọi khóa.
Ràng buộc:
- $1 \le n \le 15$
- $1 \le k \le n$
- $0 \le$
relations.length$\le n \cdot (n - 1) / 2$ relations[i].length == 2- $1 \le$
prevCoursei, nextCoursei$\le n$ prevCoursei != nextCoursei- Tất cả các cặp
[prevCoursei, nextCoursei]đều khác nhau. - Đồ thị đã cho là đồ thị có hướng không chu trình (DAG).
Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm minNumberOfSemesters trong class Solution. Để chạy được như một chương trình bình thường (và dùng được khung chạy tay bên dưới), mình đặt thêm định dạng:
- Dữ liệu vào: dòng đầu gồm ba số nguyên $n$, $m$, $k$ ($m$ là số quan hệ). Tiếp theo là $m$ dòng, mỗi dòng gồm hai số
prevCourse nextCourse. - Kết quả: một số nguyên là số học kỳ ít nhất.
1494. Parallel Courses II (LeetCode, Hard)
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei. Also, you are given the integer k.
In one semester, you can take at most k courses as long as you have taken all the prerequisites in the previous semester for the courses you are taking.
Return the minimum number of semesters needed to take all courses. The testcases will be generated such that it is possible to take every course.
Constraints:
1 <= n <= 151 <= k <= n0 <= relations.length <= n * (n-1) / 2relations[i].length == 21 <= prevCoursei, nextCoursei <= nprevCoursei != nextCoursei- All the pairs
[prevCoursei, nextCoursei]are unique. - The given graph is a directed acyclic graph.
Example 1: Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2 – Output: 3.
Explanation: The figure below represents the given graph. In the first semester, you can take courses 2 and 3. In the second semester, you can take course 1. In the third semester, you can take course 4.
Example 2: Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2 – Output: 4.
Explanation: The figure below represents the given graph. In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester. In the second semester, you can take course 4. In the third semester, you can take course 1. In the fourth semester, you can take course 5.
Example 3: Input: n = 11, relations = [], k = 2 – Output: 6.
Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
Output: 34 3 2
2 1
3 1
1 4
---
3Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 45 4 2
2 1
3 1
4 1
1 5
---
4Input: n = 11, relations = [], k = 2
Output: 611 0 2
---
6Giải thích ví dụ của đề:
- Ví dụ 1: học kỳ 1 học khóa 2 và 3; học kỳ 2 học khóa 1; học kỳ 3 học khóa 4. Tổng cộng 3 học kỳ.
- Ví dụ 2: học kỳ 1 chỉ học được khóa 2 và 3 vì mỗi kỳ không học quá 2 khóa; học kỳ 2 học khóa 4; học kỳ 3 học khóa 1; học kỳ 4 học khóa 5. Tổng cộng 4 học kỳ.
- Ví dụ 3: không có ràng buộc nào, 11 khóa, mỗi kỳ học tối đa 2 khóa nên cần $\lceil 11 / 2 \rceil = 6$ học kỳ.
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 😇.
Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.
Tóm tắt đề bài: có $n$ khóa học và một danh sách quan hệ: quan hệ $(a, b)$ nghĩa là phải học khóa $a$ trước khóa $b$. Mỗi học kỳ học tối đa $k$ khóa. Tuy nhiên trong một học kỳ, ta không được học 2 khóa mà giữa chúng có quan hệ trước – sau (kể cả gián tiếp), tức là các khóa học cùng kỳ phải hoàn toàn độc lập với nhau, và mọi khóa phải học trước chúng đều đã học xong ở các kỳ trước. Hãy tính số học kỳ tối thiểu để học hết $n$ khóa.
Mình nói thêm về ví dụ 2 cho bạn nào thắc mắc: khóa 1 cần cả 3 khóa 2, 3, 4 học xong trước, mà mỗi kỳ chỉ học được 2 khóa nên 3 khóa này tốn ít nhất 2 kỳ, rồi khóa 1 một kỳ, khóa 5 một kỳ nữa – tổng 4 kỳ. Bài này dễ "dính bẫy" tham lam: không phải lúc nào chọn đại $k$ khóa đang học được cũng tối ưu, vì chọn khóa nào ở kỳ này sẽ ảnh hưởng tới những khóa được "mở khóa" ở kỳ sau. Vì vậy ta phải xét hết các khả năng – và $n \le 15$ chính là gợi ý để dùng bitmask.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Quy hoạch động + bitmask – O(3^N · N)
Để ý là $n \le 15$, nên một tập hợp các khóa học có thể biểu diễn bằng một số nguyên $15$ bit gọi là mask: bit thứ $i$ bằng 1 nghĩa là khóa thứ $i$ (đánh số từ 0 trong code, tức khóa $i + 1$ của đề) có trong tập. Ta mô hình hóa bài toán thành bài toán đồ thị, mỗi đỉnh là một khóa học.
Để tính $fact[i]$, mình lưu đồ thị ngược: với quan hệ $(a, b)$ thêm cạnh $b \to a$ (từ khóa sau chỉ về khóa phải học trước). Khi đó DFS từ $i$ theo đồ thị ngược sẽ đi qua đúng các khóa phải học trước $i$, ta bật bit của chúng vào biến mask.
Với $f[mask]$ hiện tại, ta duyệt nextmask là danh sách các khóa học tiếp theo ta muốn học (là tập con của các khóa chưa học restmask). Lưu ý, nextmask phải thỏa điều kiện: với mỗi khóa $i$ có trong nextmask:
- Trong
nextmaskkhông có khóa nào phải học trước $i$:fact[i] & nextmaskchỉ còn đúng 1 bit (chính là bit $i$). Nhờ vậy các khóa trongnextmaskhoàn toàn độc lập với nhau. - Tập các khóa phải học trước $i$ đã xuất hiện trong
maskrồi:fact[i] & (mask | nextmask) == fact[i](bit $i$ nằm trongnextmask, các bit còn lại phải nằm trongmask).
Nếu thỏa mãn, ta cập nhật:
với $cost[x] = \left\lceil \dfrac{popcount(x)}{k} \right\rceil$ là số học kỳ tối thiểu cần thiết để học hết các khóa trong tập $x$ (mỗi kỳ học tối đa $k$ khóa).
mask | nextmask là gì?| là phép OR theo bit. Vì mask và nextmask không có bit chung, mask | nextmask chính là hợp của hai tập: các khóa đã học cộng thêm các khóa vừa học. Ví dụ mask = 0110 (đã học khóa 2, 3 của đề) và nextmask = 0001 (học thêm khóa 1) thì mask | nextmask = 0111. Còn dp[mask | nextmask] là số học kỳ ít nhất để học xong tập hợp đó.nextmask độc lập với nhau và mọi khóa phải học trước chúng đã nằm trong mask, nên chia nextmask thành từng nhóm $k$ khóa và học ở $\lceil |nextmask| / k \rceil$ kỳ liên tiếp theo thứ tự nào cũng được. Ngược lại, mỗi học kỳ của một cách học hợp lệ bất kỳ cũng chính là một nextmask thỏa điều kiện với chi phí 1. Vì vậy quy hoạch động không bỏ sót cũng không tính sai cách học nào. Cho phép nextmask lớn giúp ví dụ 3 (không có quan hệ) nhảy thẳng từ $f[0]$ lên $f[2^{11} - 1] = \lceil 11/2 \rceil = 6$.Cách duyệt tất cả tập con của restmask là mẹo quen thuộc: for (nextmask = restmask; nextmask > 0; nextmask = (nextmask - 1) & restmask). Phép (nextmask - 1) & restmask cho ra tập con liền trước (theo giá trị) của restmask, nên vòng lặp đi qua đủ mọi tập con khác rỗng.
Minh hoạ quy hoạch động trên tập
Em nhập $n$ (tối đa 6), $k$ và các quan hệ (mỗi quan hệ là 2 số a b: học $a$ trước $b$), rồi bấm Tiếp. Mỗi bước là một lần chuyển hợp lệ từ $f[mask]$ sang $f[mask \mid nextmask]$. Vòng tròn xanh lá là khóa đã học (trong mask), viền xanh dương là khóa đang học được, vàng là các khóa của nextmask:
Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé. Mảng toàn cục adj lưu đồ thị ngược, hàm dfs gom tập phải học trước vào biến toàn cục mask:
#include <bits/stdc++.h>
using namespace std;
int dp[(1 << 15) + 5];
int fact[15];
int cost[(1 << 15) + 5];
vector<int> adj[15];
int mask = 0;
const int inf = 10005;
class Solution {
public:
void dfs(int u) {
mask |= (1 << u);
for (int i = 0; i < (int) adj[u].size(); i++) {
int v = adj[u][i];
dfs(v);
}
}
int minNumberOfSemesters(int n, vector<vector<int>>& a, int k) {
for (int i = 0; i < n; i++) {
adj[i].clear();
}
for (int i = 0; i < (int) a.size(); i++) {
adj[a[i][1] - 1].push_back(a[i][0] - 1);
}
for (int i = 0; i < n; i++) {
mask = 0;
dfs(i);
fact[i] = mask;
}
for (int mask = 1; mask < (1 << n); mask++) {
int cnt = (int) __builtin_popcount(mask);
cost[mask] = (cnt + k - 1) / k;
}
for (int mask = 0; mask < (1 << n); mask++) {
dp[mask] = inf;
}
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == inf) {
continue;
}
int restmask = (1 << n) - 1 - mask;
for (int nextmask = restmask; nextmask > 0; nextmask = (nextmask - 1) & restmask) {
if ((mask & nextmask) > 0) {
continue;
}
bool check = true;
for (int i = 0; i < n; i++) {
if ((nextmask & (1 << i)) > 0) {
int tmpmask = fact[i] & nextmask;
if ((int) __builtin_popcount(tmpmask) != 1) {
check = false;
break;
}
tmpmask = mask | nextmask;
if ((fact[i] & tmpmask) != fact[i]) {
check = false;
break;
}
}
}
if (check == true) {
dp[mask | nextmask] = min(dp[mask | nextmask], dp[mask] + cost[nextmask]);
}
}
}
return dp[(1 << n) - 1];
}
};
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> a(m, vector<int>(2));
for (int i = 0; i < m; i++) {
cin >> a[i][0] >> a[i][1];
}
Solution sol;
cout << sol.minNumberOfSemesters(n, a, k);
return 0;
}import sys
from typing import List
INF = 10005
class Solution:
def minNumberOfSemesters(self, n: int, a: List[List[int]], k: int) -> int:
adj = [[] for _ in range(n)]
for u, v in a:
adj[v - 1].append(u - 1)
# fact[i]: môn i và tất cả các môn phải học trước môn i (trực tiếp lẫn gián tiếp)
fact = [0] * n
for i in range(n):
mask = 0
stack = [i]
while stack:
u = stack.pop()
if mask >> u & 1:
continue
mask |= 1 << u
stack.extend(adj[u])
fact[i] = mask
full = (1 << n) - 1
cost = [0] * (1 << n)
for mask in range(1, 1 << n):
cost[mask] = (bin(mask).count("1") + k - 1) // k
dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == INF:
continue
# các môn chưa học mà mọi môn phải học trước nó đều đã nằm trong mask
avail = 0
for i in range(n):
if not (mask >> i & 1) and (fact[i] & ~(1 << i)) & ~mask == 0:
avail |= 1 << i
cur = dp[mask]
nextmask = avail
while nextmask > 0:
t = mask | nextmask
c = cur + cost[nextmask]
if c < dp[t]:
dp[t] = c
nextmask = (nextmask - 1) & avail
return dp[full]
def main():
data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = []
for i in range(m):
a.append([int(data[3 + 2 * i]), int(data[4 + 2 * i])])
print(Solution().minNumberOfSemesters(n, a, k))
if __name__ == "__main__":
main()for i của bản C++ gộp lại đúng bằng: mọi khóa trong nextmask đều chưa học và có tất cả khóa phải học trước nằm trong mask (khi đó các khóa trong nextmask tự động độc lập với nhau). Nên ở bản Python mình tính trước tập avail gồm các khóa như vậy rồi chỉ duyệt tập con của avail: vẫn đúng các phép chuyển như bản C++, chỉ là không phải duyệt rồi loại bớt nữa (Python chạy chậm nên tiết kiệm được chút nào hay chút đó).Khung chạy tay bên dưới chạy đúng từng dòng của code C++ ở trên (cả hàm main, hàm dfs lẫn hàm minNumberOfSemesters). Mảng dp vẽ theo chỉ số mask (ô vàng là dp[mask] đang xét, ô viền vàng là ô vừa được cập nhật):
Đánh giá độ phức tạp của cách làm này:
- Không gian: các mảng
dp,costcó $2^n$ phần tử nên là $O(2^N)$. - Thời gian: với mỗi
mask, ta duyệt mọi tập con của phần bùrestmask. Tổng số cặp (mask,nextmask) là $3^n$ (mỗi khóa có 3 khả năng: thuộcmask, thuộcnextmask, hoặc không thuộc cả hai). Mỗi cặp kiểm tra thêm $n$ khóa nên tổng là $O(3^N \cdot N)$. Với $n = 15$ thì $3^{15} \approx 1.4 \cdot 10^7$ cặp.
adj, fact, dp lại là biến toàn cục, nên đầu hàm phải clear() danh sách kề và gán lại dp bằng inf cho mọi mask. Quên bước này là test sau "dính" dữ liệu của test trước.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét