Lời giải đầy đủ tại đây. Slides chữa bài của VNOI tại đây.

Tóm tắt đề bài

Cho ~K~ điểm nằm trên hệ trục toạ độ Đề-các ~Oxy~, trong đó điểm thứ ~i~ (~1\le i\le K~) có tọa độ là ~\left(R\times cos \frac{a_i\times \pi}{180},R\times sin \frac{a_i\times \pi}{180}\right)~. Trong bài toán này lấy ~R=100,\pi=3.14159265359~.

Bạn cần thêm một số điểm trên hệ trục tọa độ, có thể không thêm điểm nào và được thêm không quá ~25~ điểm. Các điểm này cần nằm trong hoặc nằm trên đường tròn tâm ~O(0,0)~ bán kính ~R~.

Sau đó, bạn cần vẽ một số đường nối giữa một số cặp điểm sao cho:

• Với mọi cặp điểm trong ~K~ điểm ban đầu, tồn tại duy nhất một con đường liên kết trực tiếp hoặc gián tiếp giữa chúng.
• Tổng độ dài các đường nối (tính theo khoảng cách Euclid) là tối thiểu.

Độ tối ưu của một phương án sẽ được tính dựa trên giá trị ~A~ là tổng độ dài trong phương án tối ưu của BTC (giá trị này bạn được biết trước, cách tính điểm sẽ được giải thích rõ ở phần sau).

Giới hạn và subtask

• ~3\le K\le 10~
• ~a_i~ là số nguyên không âm với mọi ~i~ từ ~1~ đến ~K~
• ~0\le a_1\le a_2\le \dots\le a_K\le 359~
• ~0<A<2\times \pi\times R~</li>

Subtask	Điểm	Giá trị ~K~	Dãy ~a~	Giá trị ~A~
1	~12\%~	~3~	~\{0,90,180\}~	~273.2056~
2	~14\%~	~3~	~\{0, 40, 150\}~	~230.5843~
3	~14\%~	~4~	~\{40, 140, 200, 340\}~	~341.1483~
4	~14\%~	~5~	~\{0, 72, 144, 216, 288\}~	~457.4330~
5	~6\%~	~6~	~\{0, 60, 120, 180, 240, 300\}~	~500.0000~
6	~40\%~	~\dagger~	~\dagger~	~\dagger~

~\dagger~: Không có ràng buộc gì thêm

Cách tính điểm

Với mỗi test, gọi ~B~ là tổng độ dài các đường nối trong phương án của bạn. Điểm của bạn được tính theo công thức sau:

Giá trị ~B~	Phần trăm số điểm
~B\le A~	~100\%~
~A<B\le A\times 1.03~</td>	~\left(13-12^{\frac{B}A}\right)\times 100\%~
~B>A\times 1.03~	~0\%~

Lưu ý trước khi đọc lời giải

Đây là dạng bài lần đầu tiên xuất hiện trong VOI, và nó đã tạo ra rất nhiều bất ngờ và cả hoảng loạn cho các thí sinh. Đây không phải là bài dễ, vì vậy, việc phân bổ chiến thuật cho bài này là điều vô cùng quan trọng.

Một số giải thích về dạng bài mới:

• Đây là dạng bài gần đúng, cho phép bạn có điểm dựa trên độ tối ưu của đáp án bạn đưa ra.
• Ngoài ra, các bạn còn được cho trước dữ liệu đầu vào của một số test.
• Thông thường, sẽ không có lời giải tối ưu toàn cục cho các bài dạng này.

Dạng bài này đã tiếp tục xuất hiện ở Kỳ thi Olympic truyền thống 30 tháng 4. Vì vậy, các bạn nên chuẩn bị tinh thần rằng dạng bài này hoàn toàn có thể xuất hiện trong các kỳ VOI sắp tới.

Ở phần đầu, mình sẽ giải thích kỹ về cách tiếp cận cũng như hướng giải của mình cho bài này. Phần tiếp theo sẽ là phần Bonus, mình sẽ nói về một số cách các bạn có thể làm để có điểm trong bối cảnh giờ thi.

Subtask 1-2: ~K = 3~

Với ~K = 3~, ta có thể chứng minh, ta chỉ cần thêm tối đa ~1~ điểm là sẽ đạt được đáp án tối ưu của bài. Xét hai trường hợp:

• Trường hợp 1 (không thêm điểm nào): Dễ thấy phương án nối tối ưu luôn là chọn hai cạnh có độ dài nhỏ nhất trên ba cạnh nối giữa các cặp điểm.
• Trường hợp 2 (thêm ~1~ điểm): Có thể thấy phương án tối ưu để sử dụng điểm mới là nối với ~3~ điểm ban đầu.

Chứng minh: Xét bất kỳ phương án nào khác, ta đều phải thực hiện nối hai điểm gốc bất kỳ với nhau. Khi đó, việc nối điểm còn lại tới một trong hai điểm gốc thông qua điểm trung gian không làm đáp án tối ưu hơn (theo BĐT tam giác). Trong trường hợp này, việc thêm điểm trung gian vào sẽ là việc không cần thiết.

Trong trường hợp cần thêm ~1~ điểm, thì điểm đó sẽ là Điểm Fermat của tam giác đó.

Sau đây là một số cách làm để tìm điểm Fermat:

Cách 1: Cày trâu

Vì input được cho trước, ta không cần phải quan tâm đến vấn đề time limit mà có thể sinh ra đáp án trong giờ thi.

Ta có thể duyệt các điểm (duyệt ~x~ từ ~-100.00~ tới ~100.00~, bước nhảy ~0.01~, duyệt ~y~ cũng tương tự) để cho ra kết quả tối ưu. Khi duyệt, thường sẽ mất từ ~6~ tới ~7~ phút cho cả hai test.

Độ phức tạp sẽ tùy vào precision các bạn chọn trong bước duyệt nói trên.

Cách 2: Ternary search (chặt tam phân)

Gọi ~f(x,y)~ là tổng khoảng cách giữa điểm ~(x,y)~ với ~K~ điểm được cho trước. Ta có thể nhận thấy ~f(x,y)~ là hàm lồi.

Dựa vào tính chất đặc biệt ở trên, ta có thể thực hiện chặt tam phân trên hai chiều ~x~ và ~y~ để tìm kết quả. Cách này sẽ nhanh và hiệu quả hơn rất nhiều so với cách trước, các bạn có thể chạy chương trình mà không mất quá nhiều thời gian.

Subtask 3-6: Không có ràng buộc gì thêm

Với một tập điểm mới được chọn, có thể thấy phương án tối ưu luôn là dựng MST (cây khung nhỏ nhất) của tất cả các điểm. Tuy nhiên, cần phải đảm bảo tất cả điểm mới có thể đóng góp vào cách nối tốt nhất. Nếu không, sẽ luôn tồn tại một cách chọn tập điểm khác tối ưu hơn.

Ta thử đặt ra một vấn đề như sau: Nếu có một tập điểm có thể được chọn làm điểm mới, làm sao để tối ưu việc nối giữa các điểm gốc với nhau? Khi đã tìm được phương án tối ưu, ta chỉ cần loại bỏ các điểm không đóng góp vào đáp án là xong.

Ta sẽ coi đây như bài toán con để giải quyết trước, sau đó chúng ta sẽ trở lại bài toán gốc.

Bài toán con

Cho trước một tập hợp gồm ~K+M~ điểm trên hệ trục tọa độ Đề-các ~Oxy~, với ~K~ điểm gốc và ~M~ điểm trung gian. Tìm cách nối các điểm sao cho ~K~ điểm gốc được liên kết với nhau (có thể thông qua một số điểm trung gian) và tổng độ dài của các cạnh nối là nhỏ nhất có thể.

Đây là bài toán Steiner Tree. Về mặt lý thuyết, bài toán này là bài toán NP-hard và không thể giải được. Tuy nhiên, với giới hạn đặc biệt (~K\le 10~), ta có thể giải quyết bài toán bằng quy hoạch động.

Gọi ~dp(X,v)~ (với ~X~ là một tập con của tập điểm gốc và ~v~ là một điểm thuộc cây Steiner liên kết tất cả điểm thuộc tập ~X~) là tổng độ dài nhỏ nhất của các đoạn trên Steiner Tree thỏa mãn điều kiện đã chú thích. Như vậy đáp án cho bài toán sẽ là giá trị nhỏ nhất của các giá trị ~dp(S,v)~ với ~S~ là tập điểm gốc và ~v~ là một trong ~K+M~ điểm (bao gồm điểm gốc và điểm trung gian).

Để dễ dàng quản lý, ta có thể biểu diễn các tập ~X~ dưới dạng bitmask.

Nếu ~|X|=1~, gọi ~X=\{x\}~. Khi đó ta có ~dp(X,v)=dist(x,v)~. Trong đó ~dist(a,b)~ là cách tối ưu nối để liên kết điểm ~a~ và ~b~.

Trong các cách nối thì nối theo đường thẳng luôn là cách tối ưu nhất. Vì thế nên việc sử dụng Dijkstra là việc không cần thiết, ta chỉ cần duyệt trạng thái trong ~O(K+M)~ là xong.

Xét trường hợp ~|X|>1~. Với một cây Steiner tối ưu tương ứng với ~dp(X,v)~, ta có thể thấy: Luôn có cách chọn một điểm ~u~ (có thể ~u=v~) và một tập con ~Y~ của ~X~ sao cho có thể chia cây Steiner làm ba phần:

• Phần 1: Đường nối liên kết giữa ~u~ và ~v~.
• Phần 2: Một cây Steiner liên kết các đỉnh trong tập ~Y~ và chứa đỉnh ~u~.
• Phần 3: Một cây Steiner liên kết các đỉnh trong tập ~X\setminus Y~ và chứa đỉnh ~u~.

Như vậy, ~dp(X,v)=min(dist(u,v)+min(dp(Y,u)+dp(X\setminus Y,u)))~.

Ta có thể tính trước các giá trị ~min(dp(Y,u)+dp(X\setminus Y,u))~ để xử lý nhanh hơn. Tương tự như trường hợp ~|X|=1~, ta không cần phải xử lý Dijkstra mà chỉ cần duyệt trâu tất cả giá trị ~u~ và tập con ~Y~.

Độ phức tạp: ~O\left(3^K\times (K+M)+2^K\times (K+M)^2\right)~.

Cách giải bài toán con trên đã được tham khảo từ blog Dreyfus-Wagner DP algorithm trên Codeforces. Vì tính chất đặc biệt của bài toán con, độ phức tạp cho bài toán này tốt hơn rất nhiều so với bài toán Steiner Tree chuẩn.

Trở lại bài toán gốc

Ta đã giải quyết xong bài toán con. Từ ý tưởng đó, ta có thể thực hiện một số phương pháp để tìm đáp án tối ưu nhất có thể với giới hạn time limit như sau:

Cách 1

Ta thực hiện thao tác sau nhiều lần:

• Chọn một tập điểm trung gian gồm nhiều điểm ngẫu nhiên. Theo đề bài, các điểm này cần phải nằm trên hình tròn tâm ~O(0,0)~ bán kính ~R=100~.
• Từ tập điểm gốc và tập điểm trung gian, ta thực hiện quy hoạch động để xác định Steiner Tree.
• Từ cây Steiner, ta loại bỏ các điểm trung gian không cần thiết bằng cách tạo thêm mảng ~trace~ để truy vết ra cây Steiner. Sau đó, dựng MST từ các điểm còn lại để có một cách liên kết các điểm gốc.

Trong tất cả phương án liên kết các điểm gốc đã tạo được, ta sẽ lấy phương án tối ưu nhất có thể.

Về việc xét số lần thực hiện thao tác, bạn có thể lặp số lần cố định, tuy nhiên đây không phải là một cách làm tốt do trong khuôn khổ của kỳ thi HSGQG, việc chấm offline làm bạn không thể biết nên lặp bao nhiêu lần để chương trình không bị chạy quá thời gian (TLE). Thay vào đó, bạn nên dùng 1.0 * clock() / CLOCKS_PER_SEC để căn thời gian chương trình của bạn cần dừng tối ưu.

Tuy nhiên, bạn chỉ nên để 1.0 * clock () / CLOCKS_PER_SEC < 2.67, để có dư địa tránh bị TLE oan.

Cách 2

Ta có một nhận xét như sau: Nếu thêm một số điểm trung gian từ tập điểm đã có, ta hoàn toàn có thể tối ưu đáp án hơn.

Phát triển từ ý tưởng của Cách 1, ta bắt đầu với việc thêm một tập điểm trung gian nhỏ. Sau khi dựng được một cây Steiner, ta bỏ tất cả điểm trung gian không cần thiết.

Từ lần thử tiếp theo, mỗi lần ta thêm một số điểm và xác định cây Steiner một lần nữa để xem có cho ra kết quả tối ưu hơn không. Rõ ràng với cách này, đáp án chỉ có thể tối ưu hơn hoặc không tối ưu được thêm. Sau mỗi lần tìm cây Steiner, ta lại bỏ các điểm trung gian không cần thiết và tiếp tục quá trình trên.

Nếu bạn biết cách chọn điểm trung gian, chương trình của bạn có thể tìm ra được đáp án tối ưu hơn trong khuôn khổ time limit. Sau đây là một số phương pháp chọn điểm (bạn có thể kết hợp nhiều phương pháp nếu muốn):

• Chọn một số điểm mới hoàn toàn ngẫu nhiên.
• Chọn một số điểm gần với các điểm xuất hiện (bao gồm các điểm gốc và các điểm trung gian còn lại trong lần duyệt trước).
  • Chọn các điểm với khoảng cách nằm trong một khoảng cố định.
  • Càng chạy thử nhiều lần, ta càng chọn các điểm với khoảng cách nhỏ hơn.

Nếu có thời gian, bạn có thể thử nhiều lần để tìm cách chọn điểm tốt nhất theo cảm nhận của bạn.

Note

Với các subtask 3, 4, 5, đây là các subtask bạn được biết trước input. Vì thế nên bạn hoàn toàn có thể chạy chương trình trên máy trước để tìm đáp án tối ưu mà không cần phải quan tâm vấn đề time limit.

Bonus

Ngoài ra, đây là một số cách làm cơ bản giúp bạn có thể có điểm nếu không đủ thời gian làm các cách trên. Tất nhiên, các bạn nên kết hợp cả hai cách dưới đây với lời giải nói trên, vì ta luôn có thể lấy cách tối ưu nhất.

Cách 1

In ra như sau:

0
1 2
2 3
...
K-1 K

Cách 2

Ta không tạo điểm nào mới, dựng MST và in ra tập cạnh nối tối ưu tương ứng với các cạnh trong MST.

Bạn cũng có thể thêm một số điểm vào trước rồi thực hiện tạo MST (có thể thử nhiều lần). Tuy nhiên như đã nói ở phần đầu Subtask 3-6, việc dựng MST chưa chắc tạo ra được đáp án tối ưu như áp dụng quy hoạch động tìm cây Steiner.

Bonus 2.0 - Chiến thuật làm bài

Ở bài này, chiến thuật làm bài sẽ tùy thuộc vào việc bạn sẵn sàng bỏ bao nhiêu thời gian cho bài này. Mình sẽ phân cấp ra theo hai mức ở dưới.

Lưu ý, xuyên suốt phần hướng dẫn này, tác giả giả định rằng người đọc sẽ cài đặt tất cả các cách tối ưu phía dưới và chọn ra cách tốt nhất.

Level 1 - 20 phút

Với 20 phút, bạn có thể cài đặt thuật toán sau:

• Cây khung nhỏ nhất trên tập điểm có sẵn (mà không thêm điểm nào).
• Thêm một điểm (với độ chính xác 1 chữ số sau phần thập phân), sau đó thực hiện cây khung nhỏ nhất.

Thực tế, cách này giúp bạn có được ~38,58 \%~ số điểm, một số điểm đủ tốt.

Level 2 - 60 phút

Các bạn chỉ nên dành 60 phút cho bài này nếu đã hoàn thành trọn vẹn hai bài 4 và 5, hoặc các bạn không còn ý tưởng nào cho hai bài nói trên.

Với 60 phút, các bạn hoàn toàn có thể nghĩ tới việc ăn điểm ở ~40\%~ số test còn lại. Có rất nhiều cách khác nhau, vì dung lượng bài viết có hạn, mình sẽ không trình bày lại nữa.