Đội Hợp Xướng Hogwarts

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\le 7$ và $K\le 4$, ta có thể dùng quy hoạch động theo broken profile (broken profile DP).

Nhận xét quan trọng

1. $M$ nhỏ, $N$ lớn: Số cột $M\le 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.

2. 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.

3. 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.

4. 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ý

1. 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,\text{giọng hàng }i-1}$
   • Cập nhật profile: thay đổi chữ số $i$ thành $k$

2. 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,\text{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,\text{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$

3. 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[\text{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_{\text{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,\text{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.