Trong bài này, bạn đóng vai người ra đề và phải tạo dữ liệu để phân biệt hai chương trình. Ban tổ chức cung cấp hai bài toán đồ thị, tám phân nhóm và một số chương trình tưởng như giải được các bài đó. Với mỗi phân nhóm, hãy tạo một dữ liệu \(X\) sao cho:

1. Chương trình A không bị quá thời gian trên \(X\).
2. Chương trình B bị quá thời gian trên \(X\).

Mỗi chương trình duy trì biến counter xấp xỉ số phép toán. Một chương trình được xem là quá thời gian ngay khi counter vượt quá \(1\,000\,000\). Ban tổ chức ưu tiên dữ liệu nhỏ, với mục tiêu chứa không quá \(T\) số nguyên có dấu.

Mã nguồn C, C++ và Pascal của các thuật toán được cung cấp trong tệp đính kèm. Hệ thống chấm sử dụng đúng hành vi của bản C++.

Cách nộp bài

Đây là bài output-only. Nộp một tệp ZIP chứa tám tệp sau ở ngay thư mục gốc của tệp nén:

tasksauthor1.out
tasksauthor2.out
tasksauthor3.out
tasksauthor4.out
tasksauthor5.out
tasksauthor6.out
tasksauthor7.out
tasksauthor8.out

Tệp tasksauthorX.out là dữ liệu vào do bạn thiết kế cho phân nhóm \(X\). Nếu thiếu tệp, sai định dạng, vi phạm ràng buộc, chương trình A bị quá thời gian, hoặc chương trình B không bị quá thời gian thì phân nhóm đó được \(0\) điểm.

Nếu dữ liệu hợp lệ và phân biệt được hai chương trình, gọi \(F\) là số số nguyên trong tệp, \(S\) là điểm của phân nhóm và \(T\) là kích thước mục tiêu. Điểm nhận được là:

Do đó, nếu \(F\le T\) thì nhận đủ \(S\) điểm.

Các phân nhóm

Bài toán SSSP

Cho đồ thị có hướng có trọng số \(G\) và hai đỉnh \(s,t\). Gọi \(p(s,t)\) là trọng số đường đi ngắn nhất từ \(s\) đến \(t\). Nếu không thể đi từ \(s\) đến \(t\), quy ước \(p(s,t)=1\,000\,000\,000\). Dữ liệu gồm đồ thị và \(Q\) truy vấn \((s_k,t_k)\).

Tệp bắt đầu bằng số đỉnh \(V\). Các đỉnh được đánh số từ \(0\) đến \(V-1\). Sau đó có \(V\) dòng mô tả danh sách kề; dòng của đỉnh \(i\) bắt đầu bằng \(n_i\), tiếp theo là \(n_i\) cặp \((j,w)\) mô tả cạnh có hướng \(i\to j\) trọng số \(w\). Khối thứ hai bắt đầu bằng \(Q\), rồi đến \(Q\) dòng chứa \(s_k,t_k\).

Các số liên tiếp trên cùng dòng phải cách nhau bởi ít nhất một dấu cách. Dữ liệu phải thỏa mãn:

• \(0<V\le300\).
• \(n_i\ge0\).
• \(0\le j<V\).
• \(|w|<10^6\).
• \(0\le\sum_{i=0}^{V-1}n_i\le5\,000\).
• \(0<Q\le10\).
• \(0\le s_k,t_k<V\).
• Đồ thị không có chu trình âm.

Ví dụ minh họa dưới đây chứa \(15\) số nguyên, nhưng không phải tệp cần nộp cho một phân nhóm cụ thể.

3
2 1 4 2 1
0
1 1 2
2
0 1
1 0

Kết quả SSSP tương ứng là 3 và 1000000000; counter của ModifiedDijkstra bằng \(5\).

{{asset:apio13-tasksauthor-sssp}}

Bài toán Mystery

Cho đồ thị vô hướng \(G\) có \(V\) đỉnh và \(E\) cạnh. Hãy gán cho mỗi đỉnh một nhãn nguyên trong \([0,X-1]\) sao cho hai đầu mút của mọi cạnh có nhãn khác nhau, với \(X\) nhỏ nhất có thể.

Tệp bắt đầu bằng \(V,E\), sau đó là \(E\) dòng, mỗi dòng chứa một cạnh vô hướng \((a,b)\). Dữ liệu phải thỏa mãn:

• \(70<V<1\,000\).
• \(1\,500<E<10^6\).
• Với mọi cạnh: \(a\ne b\), \(0\le a,b<V\).
• Mỗi cạnh xuất hiện đúng một lần.

Ví dụ dưới đây chỉ để minh họa và không hợp lệ làm dữ liệu nộp vì \(V,E\) quá nhỏ. Tệp có \(12\) số nguyên; counter của RecursiveBacktracking bằng \(18\).

4 5
0 1
0 2
0 3
1 2
2 3

Một cách tô tối ưu dùng \(X=3\) với nhãn 0 1 2 1.

{{asset:apio13-tasksauthor-mystery}}

Hành vi các thuật toán

• FloydWarshall: thực hiện đúng \(V^3\) lượt lặp, mỗi lượt tăng counter một đơn vị, rồi trả lời các truy vấn.
• OptimizedBellmanFord: với mỗi truy vấn, lặp tối đa \(V-1\) lần trên toàn bộ danh sách cạnh; mỗi cạnh được xét làm tăng counter một đơn vị. Dừng sớm nếu một lượt không cập nhật khoảng cách.
• ModifiedDijkstra: với mỗi truy vấn, mỗi lần lấy một phần tử khỏi hàng đợi ưu tiên làm tăng counter một đơn vị. Thuật toán vẫn chạy đúng theo mã được cung cấp, kể cả khi đồ thị có trọng số âm nhưng không có chu trình âm.
• Gamble1: gán nhãn đỉnh \(i\) bằng \(i\) và đặt counter=0.
• Gamble2: gán nhãn đỉnh \(i\) bằng \(i\) và đặt counter=1000001.
• RecursiveBacktracking: thử \(X\) từ \(2\) đến \(V\), tô đỉnh \(0\) bằng \(0\), rồi thử các nhãn theo thứ tự nhỏ nhất cho các đỉnh kề; vị trí tăng counter được xác định chính xác bởi mã nguồn đính kèm.

Phân nhóm

Bảng Các phân nhóm ở trên là bảng điểm chính thức; tổng điểm là \(100\).

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Tasks Author. Tên tệp nộp được đổi từ định dạng .tgz của hệ thống gốc sang ZIP và tên tệp chuẩn của LQDOJ; bài toán, ràng buộc, bộ đếm và công thức điểm được giữ nguyên.