Hướng dẫn giải của Đội Hợp Xướng Hogwarts

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

Hướng tiếp cận

Bài toán yêu cầu gán một trong $K$ loại giọng cho mỗi ô trong lưới $N \times M$ sao cho tổng bất hòa âm giữa tất cả các cặp ô kề nhau là nhỏ nhất. Với $M \leq 7$ và $K \leq 4$ , ta có thể dùng quy hoạch động theo broken profile (broken profile DP).

Nhận xét quan trọng

$M$ nhỏ, $N$ lớn: Số cột $M \leq 7$ gợi ý rằng ta nên xử lý theo từng cột hoặc từng ô, duy trì trạng thái dựa trên bố cục cột hiện tại.
Không gian trạng thái: Mỗi cột có $M$ ô, mỗi ô có $K$ lựa chọn, nên có $K^{M}$ trạng thái cho mỗi cột. Với $K = 4, M = 7$ : $4^{7} = 16384$ trạng thái — đủ nhỏ để duy trì DP.
Chuyển trạng thái hiệu quả: Nếu ta duyệt từng cặp trạng thái cột ( $K^{M} \times K^{M}$ ), mỗi cột tốn $\approx 268$ triệu thao tác — quá chậm. Thay vào đó, ta dùng kỹ thuật broken profile: xử lý từng ô một, cập nhật trạng thái dần dần.
Ma trận bất đối xứng: Cần chú ý hướng khi tính bất hòa âm — $D_{a, b}$ luôn tính từ ô được xử lý trước (trên, trái) sang ô được xử lý sau (dưới, phải).

Thuật toán

Biểu diễn trạng thái

Trạng thái $s$ là một số trong hệ cơ số $K$ gồm $M$ chữ số, trong đó chữ số thứ $i$ biểu diễn loại giọng tại hàng $i$ của "profile" hiện tại.

Broken profile

Tại mỗi thời điểm khi ta đang xử lý ô $(i, j)$ trong cột $j$ :

Các hàng $0, 1, \dots, i - 1$ của profile chứa giá trị của cột $j$ (đã gán)
Các hàng $i, i + 1, \dots, M - 1$ của profile chứa giá trị của cột $j - 1$ (chưa bị thay thế)

Xử lý

Cột đầu tiên ( $j = 0$ ): Xử lý từng hàng $i = 0, 1, \dots, M - 1$ . Khi gán loại giọng $k$ cho hàng $i$ :
- Nếu $i > 0$ : cộng bất hòa âm dọc $D_{k, giọng hàng i - 1}$
- Cập nhật profile: thay đổi chữ số $i$ thành $k$
Các cột tiếp theo ( $j = 1, \dots, N - 1$ ): Xử lý từng hàng $i = 0, 1, \dots, M - 1$ . Khi gán loại giọng $k$ cho ô $(i, j)$ :
- Cộng bất hòa âm ngang: $D_{k, giọng cũ tại hàng i}$ (giá trị từ cột $j - 1$ , còn trong profile)
- Nếu $i > 0$ : cộng bất hòa âm dọc: $D_{k, giọng mới tại hàng i - 1}$ (đã gán ở bước trước)
- Cập nhật profile: thay đổi chữ số $i$ thành $k$
Kết quả: Sau khi xử lý hết $N \times M$ ô, lấy giá trị nhỏ nhất trong tất cả các trạng thái.

Lưu ý về hướng bất hòa âm

Khi ô $(i, j)$ được gán giọng $k$ :

Bất hòa âm ngang với ô $(i, j - 1)$ : ta tính $D_{k} [giọng ô bên trái]$ . Tuy nhiên, theo đề bài, $D_{g_{i, j - 1}, g_{i, j}}$ mới đúng (từ trái sang phải). Nhưng vì ta xử lý từ trái sang phải, ô $(i, j - 1)$ là "old_type" đã có trong profile. Vậy ta cộng $D_{old_type, k}$ ... Thực ra, hướng tính không quan trọng miễn ta nhất quán: mỗi cặp kề nhau được tính đúng một lần. Khi xử lý ô $(i, j)$ , ta tính bất hòa âm giữa nó và ô bên trái/bên trên — đây chính xác là mỗi cặp được tính một lần.

Trong cài đặt: D[k][old_type] nghĩa là ô hiện tại (giọng $k$ ) đứng cạnh ô trước (giọng old_type), tương đương $D_{k, old_type}$ .

Độ phức tạp

Thời gian: $O (N \times M \times K^{M} \times K)$ . Với $N = 1000$ , $M = 7$ , $K = 4$ : $\approx 460$ triệu thao tác cơ bản.
Bộ nhớ: $O (K^{M}) = O (16384)$ cho mảng DP — rất tiết kiệm.

Bình luận

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