Phân tích

Test Set 1

Các \(X_i\) chia đường tròn thành một dãy đoạn mà nhiệt độ không đổi trong mỗi đoạn. Gọi đoạn \(i\) bắt đầu tại \(X_i\) và đi theo chiều kim đồng hồ, có độ dài \(d_i\). Không có hai đoạn kề cùng nhiệt độ nên có thể bỏ qua giá trị thực \(T_i\).

Ta có các nhận xét:

• Không cần quá hai nhiệt kế trên mỗi đoạn: chiếc nằm giữa hai chiếc khác cùng đoạn không phủ thêm điểm nào.
• Nghiệm tối ưu không có hai đoạn kề đều chứa \(2\) nhiệt kế. Nếu có, hãy “đẩy” hai chiếc ở giữa ra ngoài tới khi ít nhất một chiếc chạm chiếc còn lại trong đoạn của nó, giảm tổng số ít nhất một.
• Hai nhiệt kế kề nhau thuộc hai đoạn kề khác nhau phải cách đều điểm chung; nếu không, nhiệt độ một số điểm giữa chúng sẽ sai.
• Trong nghiệm tối ưu luôn có thể đặt nhiệt kế tại vị trí nguyên hoặc bán nguyên. Nếu chưa vậy, có thể “đẩy” chúng tới các vị trí ấy.

Với các nhận xét và giới hạn nhỏ, duyệt mọi cấu hình rồi chọn tốt nhất.

Test Set 2

Nếu biết vị trí nhiệt kế trên đoạn \(A\) gần đoạn kề \(B\) nhất, ta tính vị trí dự kiến trên \(B\) bằng cách phản xạ vị trí ấy qua điểm chung. Nếu ảnh phản xạ không thuộc \(B\), vị trí đã chọn trên \(A\) là không thể.

Trước tiên giả sử đáp án lớn hơn \(N\). Dùng chiến lược tham lam sau; tính đúng đắn sẽ được chứng minh bên dưới.

Bắt đầu với đoạn \(A\) duy nhất. Một nhiệt kế tại bất kỳ điểm nào của \(A\) (trừ đầu mút theo đề) phủ toàn đoạn, nên khoảng vị trí hợp lệ là cả đoạn. Với đoạn kề \(B\), phản xạ khoảng trên \(A\) qua điểm chung rồi giao với \(B\) để có khoảng hợp lệ trên \(B\). Gọi thao tác này là lan truyền.

Tiếp tục lan truyền qua nhiều đoạn nhất có thể, dừng nếu khoảng mới rỗng. Lan truyền ngược khoảng cuối về \(A\) qua các đoạn trung gian sẽ cho những vị trí hợp lệ phủ tất cả các đoạn bằng một nhiệt kế mỗi đoạn.

Khi không thể lan truyền tiếp, xác định một khoảng hợp lệ mới trên đoạn hiện tại có xét khoảng cũ, tức đặt hai nhiệt kế ở đó, rồi lặp lại. Khi trở về \(A\), phải kiểm tra khoảng cuối bắt đầu trước khi khoảng đầu kết thúc để có thể đặt hai nhiệt kế trên \(A\).

Đáp án bằng \(N\) cộng số lần phải bắt đầu khoảng mới, tức số đoạn đặt hai nhiệt kế. Thử mọi đoạn làm điểm bắt đầu và lấy tốt nhất. Chứng minh ở dưới.

Xét đáp án đúng bằng \(N\). Gọi \(z_i\) là vị trí nhiệt kế trên đoạn \(i\) tính từ \(X_i\). Khi đó:

Các phương trình cho phép kiểm tra nhanh đáp án có thể bằng \(N\) không.

Nếu \(N\) chẵn:

hay trừ \(z_1\) ở hai vế:

Nếu đẳng thức đúng, mọi \(z_1\) thỏa phương trình. Nhưng một số \(z_i\) có thể nằm ngoài đoạn tương ứng, nên phải kiểm tra có thể lan truyền trở lại đoạn đầu mà không thêm nhiệt kế thứ hai hay không. Nếu được, đáp án là \(N\).

Nếu \(N\) lẻ:

hay cộng \(z_1\) ở hai vế:

Chỉ có một giá trị \(z_1\). Cần lan truyền nó qua mọi đoạn để kiểm tra tập vị trí hợp lệ. Nếu được, đáp án là \(N\).

Lan truyền qua mọi đoạn tốn \(O(N)\). Ta làm nhiều nhất một lần để kiểm tra \(N\), và \(N\) lần nếu đáp án không phải \(N\), nên tổng thời gian \(O(N^2)\).

Chứng minh lời giải tham lam

Hình sau mô tả khái quát các bước chứng minh:

Ta chỉ xét đáp án lớn hơn \(N\), vì trường hợp bằng \(N\) có lời giải xây dựng.

Ta định nghĩa thêm vài thuật ngữ.

Một chuỗi là dãy đoạn kề có cách đặt sao cho mỗi đoạn được phủ bởi một nhiệt kế, trừ đoạn đầu và cuối, mỗi đoạn cần hai. Chuỗi có thể phủ cả đường tròn, bắt đầu và kết thúc tại cùng một đoạn.

Chuỗi cực đại không thể kéo dài theo chiều kim đồng hồ bằng đoạn kế tiếp vì không tồn tại cách đặt theo định nghĩa chuỗi để phủ nó.

Hai chuỗi liên tiếp nếu đoạn cuối chuỗi này là đoạn đầu chuỗi kia. Đoạn chung phải dùng hai nhiệt kế.

Dãy chuỗi hợp lệ là dãy chuỗi liên tiếp chứa mọi đoạn đã cho.

Mọi cách đặt hợp lệ là một dãy chuỗi hợp lệ và dùng \(N\) cộng số chuỗi nhiệt kế. Tối ưu tương ứng với ít chuỗi nhất.

Bổ đề 1. Nếu chuỗi đầu của một dãy hợp lệ chưa cực đại, có thể chuyển các đoạn từ chuỗi hoặc các chuỗi kế vào nó tới khi cực đại mà vẫn hợp lệ và không tăng số chuỗi.

Chứng minh.

Bổ sung vài thuật ngữ.

Vị trí nhiệt kế trên đoạn \(i\) là khoảng cách tới \(X_i\).

Khoảng linh hoạt của chuỗi là tập vị trí hợp lệ trên một đoạn có thể lan truyền đúng qua toàn chuỗi. Nó luôn là đoạn con, có thể dài \(0\).

Khoảng linh hoạt đầu và cuối là các khoảng ấy trên đoạn đầu và cuối tương ứng.

Dãy chuỗi hợp lệ tương đương dãy liên tiếp chứa mọi đoạn sao cho tại đoạn nối hai chuỗi, nếu \((x_{last},y_{last})\), \((x_{first},y_{first})\) là khoảng cuối và đầu thì \(x_{last}\le y_{first}\).

Xét hai chuỗi đầu:

• \(a,b,c\) là độ dài ba đoạn đầu (nếu có) của chuỗi hai; \(a\) cũng là đoạn cuối chuỗi một.
• \((x_1,y_1)\) là khoảng cuối chuỗi một trên \(a\).
• \((x_2,y_2)\) là khoảng đầu chuỗi hai trên \(a\).

Cụ thể:

• \(x_1\le y_2\) theo tính hợp lệ.
• \((a-y_2,a-x_2)\) là khoảng thứ hai của chuỗi hai trên \(b\).

Nối \(b\) vào chuỗi một. Khi đó:

• Khoảng cuối chuỗi một phản xạ sang \(b\) thành \((a-y_1,\min(b,a-x_1))\).
• Khoảng thứ hai chuỗi hai thành khoảng đầu; xấu nhất là \((a-y_2,a-x_2)\), còn trường hợp khác nó rộng hơn và chứa trọn khoảng này.

Nếu các khoảng ban đầu giao nhau (\(x_2\le y_1\)), cấu hình mới hợp lệ vì \(a-y_1\le a-x_2\); có thể thử đoạn tiếp.

Nếu không giao nhau (\(x_2>y_1\)), cấu hình mới không hợp lệ. Hai khoảng \((a-y_2,a-x_2)\) và \((a-y_1,\min(b,a-x_1))\) không giao; khoảng đầu chuỗi hai đứng trước khoảng cuối chuỗi một.

Tuy nhiên, \((a-y_2,a-x_2)\) thuộc chuỗi hai nên lan truyền được sang \(c\). Khoảng \((a-y_1,\min(b,a-x_1))\) còn gần biên hơn nên cũng lan truyền được. Do đó có thể nối thêm đoạn kế vào chuỗi một:

• Khoảng đầu chuỗi hai thành \((b-(a-x_2),b-(a-y_2))\).
• Khoảng cuối chuỗi một thành \((b-\min(b,a-x_1),\min(c,b-(a-y_1)))\).

Cấu hình hợp lệ vì \(b-\min(b,a-x_1)\le b-(a-y_2)\) và \(x_1\le y_2\).

Nếu không có đoạn thứ hai để nối, đoạn thứ nhất cũng không thể nối vì các khoảng không giao nhau, còn khoảng linh hoạt của chuỗi một đoạn là cả đoạn.

Bổ đề 2. Luôn có thể đạt tối ưu bằng một dãy chuỗi cực đại và nhiều nhất một chuỗi có thể không cực đại.

Chứng minh.

Xét chuỗi đầu của đáp án tối ưu. Nối các đoạn từ chuỗi kế vào chừng nào có thể theo Bổ đề 1. Lặp lại với chuỗi kế tiếp. Giữ nguyên chuỗi cuối. Khi ấy mọi chuỗi trừ chuỗi cuối đều cực đại; chuỗi cuối có thể cực đại hoặc không.

Lời giải trên xây dựng mọi dãy trong Bổ đề 2, nên một trong số chúng là tối ưu.

Chứng minh chưa xử lý đúng chuỗi ngắn: chuỗi dài \(1\), \(2\), \(3\) có thể không tuân theo lập luận trên, nhưng dễ xử lý riêng như các trường hợp đặc biệt.

Dữ liệu kiểm thử. Khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 3 — Thermometers.