Đề bài: A. Bài toán Sắp xếp Cổng OXC (OXC Ports Arrangement Problem)

Mô tả

Một cụm máy tính thông minh sử dụng công nghệ OXC (Optical Circuit Switch - Chuyển mạch quang) làm lớp lõi để kết nối quy mô siêu lớn cho hàng chục nghìn thẻ tính toán.
Mặc dù OXC có ưu thế về độ trễ, hiệu quả năng lượng và băng thông so với chuyển mạch điện, nhưng khả năng chuyển mạch của nó bị giới hạn ở mức 1-1 (one-to-one) thay vì tất cả-đến-tất cả (all-to-all). Điều này gây khó khăn cho việc tận dụng tối đa băng thông.

Nhiệm vụ của bạn là phát triển một chiến lược để xác định cấu hình OXC và phương án định tuyến tối ưu cho các tác vụ AI trong thời gian thực.
Tất cả các liên kết trong bài toán được coi là hai chiều.

1. Cơ chế hoạt động của OXC

OXC thiết lập kết nối quang giữa các cổng bằng cách xoay các vi gương. Một kết nối quang nối một cổng nội bộ này với một cổng nội bộ khác, tạo thành đường dẫn hai chiều.
Lưu ý: Các kết nối là 1-1 (mỗi cổng chỉ nối được với đúng 1 cổng khác).

2. Cấu trúc mạng (Network Topology)

Mạng bao gồm các Group (Nhóm) và các OXC.

• Group: Gồm 2 tầng chuyển mạch điện (Leaf và Spine) và các NPU. Giao tiếp nội bộ trong Group chỉ đi qua chuyển mạch điện.
• Kết nối liên Group: Đi qua OXC theo lộ trình:
  \(\(NPU \rightarrow Leaf \rightarrow Spine \rightarrow OXC \rightarrow Spine \rightarrow Leaf \rightarrow NPU\)\)
  

3. Mạng đa mặt phẳng (Multi-Plane Network)

Để mở rộng quy mô, các Spine và OXC được chia thành \(P\) mặt phẳng độc lập (đánh số \(0 \dots P-1\)).
* Spine và OXC cùng mặt phẳng có liên kết với nhau. Khác mặt phẳng thì không.
* Trong cùng một mặt phẳng, giữa mỗi Spine và mỗi OXC có đúng \(K\) liên kết.

4. Chi tiết đánh số và địa chỉ

• \(N\) Group: \(0 \dots N-1\).
• \(M\) OXC: \(0 \dots M-1\). OXC \(i\) thuộc mặt phẳng \(\lfloor i / (M/P) \rfloor\).
• \(S\) Spine mỗi Group: \(0 \dots S-1\). Spine \(i\) thuộc mặt phẳng \(\lfloor i / (S/P) \rfloor\).
• \(L\) Leaf mỗi Group: \(0 \dots L-1\).
• Cổng trên OXC: Mỗi OXC có \(R = N \cdot (S/P) \cdot K\) cổng.
  • Cổng tương ứng với Group \(i\), Spine \(j\), liên kết \(k\) trên một OXC có số hiệu là:
    \(\(PortID = i \cdot (S/P) \cdot K + (j \pmod{S/P}) \cdot K + k\)\)
    

5. Yêu cầu bài toán

Có 5 truy vấn (queries). Mỗi truy vấn gồm nhiều luồng dữ liệu (flows) giữa \(Leaf_A\) và \(Leaf_B\). Bạn cần:
1. Cấu hình lại OXC: Nối các cổng với nhau.
* Chi phí điều chỉnh (Adjustment Cost): Mỗi lần thêm hoặc xóa 1 kết nối tính là 1 đơn vị chi phí (so với cấu hình của truy vấn trước đó).
2. Định tuyến: Chọn đường đi cho luồng: \(Leaf_A \to Spine_A \to OXC \to Spine_B \to Leaf_B\).
* Mục tiêu: Giảm thiểu Maximum Flow Conflict (Số luồng tối đa cùng đi qua 1 dây).

Dữ liệu nhập (Input)

• Dòng 1: 3 số nguyên \(N, S, L\) (Số Group, Số Spine/Group, Số Leaf/Group).
  • \(2 \le N \le 32\) (chẵn), \(1 \le S \le 32\), \(1 \le L \le 64\).
• Dòng 2: 3 số nguyên \(M, K, P\) (Số OXC, Số liên kết, Số mặt phẳng).
  • \(1 \le M \le 256\), \(1 \le K \le 2\), \(1 \le P \le 16\).
• Tiếp theo là 5 truy vấn. Mỗi truy vấn gồm:
  • Dòng đầu: Số nguyên \(Q\) (\(1 \le Q \le \frac{1}{2}NSL\)) - số lượng luồng yêu cầu.
  • \(Q\) dòng tiếp theo: Mỗi dòng chứa 4 số nguyên \(g_A, leaf_A, g_B, leaf_B\).
    • Mô tả luồng từ (Group \(g_A\), Leaf \(leaf_A\)) đến (Group \(g_B\), Leaf \(leaf_B\)).
    • \(0 \le g_A < g_B \le N-1\).

Dữ liệu xuất (Output)

Với mỗi truy vấn, in ra theo thứ tự:

1. Cấu hình OXC (\(M\) dòng):
   • Mỗi dòng chứa \(R\) số nguyên. Số thứ \(j\) là \(v_j\).
   • Ý nghĩa: Cổng \(j\) của OXC đó đang nối với cổng \(v_j\).
   • Nếu cổng \(j\) không nối với ai (idle), in ra -1.
2. Lộ trình luồng (\(Q\) dòng):
   • Mỗi dòng chứa 5 số nguyên:
     1. Spine x (kết nối với Leaf A).
     2. Link k_x (của Spine x nối vào OXC).
     3. OXC m (OXC được chọn).
     4. Spine y (kết nối với Leaf B).
     5. Link k_y (của Spine y nối vào OXC).

Cách tính điểm (Scoring)

Mục tiêu là tối đa hóa điểm số:

• \(\alpha = 1000, \beta = 300\).
• Convergence ratio (Tỷ lệ hội tụ) = \(\frac{(M/P) \cdot K}{L}\).
• Cost = Chi phí điều chỉnh OXC (Edit distance).

Ví dụ

Ràng buộc:

Có 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi S là 2, trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong 4 chữ cái A, T, G, C;

Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide;

Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide A, T, G, C nhỏ hơn 10;

20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.