Hình học \(L_1\) và tập điểm đạt được

Mọi khoảng cách dưới đây là Manhattan, ký hiệu \(dist(x,y)\). “Mặt cầu” tâm \(t\), bán kính \(r\) trong hình học này là một bát diện đều; điều quan trọng là khoảng cách giữa các điểm nguyên cũng nguyên và các tính chất liên tục cần dùng vẫn đúng.

Gọi \(R_i\) là tập điểm tới được từ \(P\) sau đúng \(i\) lần dịch chuyển. \(R_0=\{P\}\). Nếu lần đầu dùng máy \(t\), ta tới mọi điểm trên mặt cầu tâm \(t\), bán kính \(dist(P,t)\); tất cả các mặt cầu này giao nhau tại \(P\), nên \(R_1\) liên thông.

Quy nạp rằng với mỗi máy \(t\), tồn tại một khoảng bán kính \([L_{t,i},U_{t,i}]\) sao cho

Nếu \(R_i\) liên thông, ảnh của nó qua hàm liên tục \(dist(t,\cdot)\) là một khoảng. Mọi vành cầu đều chứa \(P\), nên hợp vẫn liên thông; điều này chứng minh quy nạp.

Bộ nhỏ: quy hoạch động trên các khoảng

Biên ngoài mới là điểm xa nhất của \(R_i\) đối với \(t\):

Khoảng cách nhỏ nhất từ \(t\) tới vành \([L_{u,i},U_{u,i}]\) bằng

Do đó \(L_{t,i+1}=\min_u g(t,u)\). Sau mỗi vòng, nếu có \(t\) thỏa \(L_{t,i}\le dist(Q,t)\le U_{t,i}\) thì \(i\) là đáp án.

Một điểm đạt được sau \(i\) bước cũng đạt được sau \(i+1\) bước bằng cách dùng một máy để đứng yên. Vì thế \(U\) không giảm và \(L\) không tăng. Khi \(N\ge2\), \(\max U\) tăng nghiêm ngặt và \(\min L\) giảm nghiêm ngặt cho tới khi chạm 0; do mọi giá trị nguyên, mỗi vòng tiến ít nhất 1. Với tọa độ trong \([-M,M]\), sau không quá \(3M\) vòng một vành phủ toàn miền có thể của \(Q\). Mỗi vòng tốn \(O(N^2)\), tổng \(O(MN^2)\). Với \(N=1\), dùng cùng máy hai lần liên tiếp không giúp gì: nếu không đạt \(Q\) trong một lần thì IMPOSSIBLE.

Các trường hợp một và hai bước

Đáp án là 1 khi và chỉ khi tồn tại \(t\) sao cho
\(dist(P,t)=dist(Q,t)\).

Nếu tồn tại \(t,u\) với

thì mặt cầu tâm \(t\) qua \(P\) chứa \(Q\), còn mặt cầu tâm \(u\) qua \(Q\) chứa \(P\). Hai mặt cầu giao nhau tại một điểm \(x\); đi \(P\to x\) bằng \(t\), rồi \(x\to Q\) bằng \(u\), nên đáp án là 2. Điều kiện này không bao quát mọi trường hợp hai bước, nhưng cho phép thu gọn trường hợp còn lại.

Nếu điều kiện không xảy ra, một trong \(P,Q\) gần hơn máy dịch chuyển kia đối với mọi máy. Đổi vai hai đầu nếu cần để \(P\) gần hơn. Khi đó \(Q\) luôn nằm ngoài mọi mặt cầu ban đầu; vì biên trong chỉ co lại, để kiểm tra đạt được chỉ cần theo dõi \(U\).

Bộ lớn: đường đi dài nhất và đại số max-plus

Công thức của \(U\) cho thấy \(U_{t,i}\) là độ dài đường đi dài nhất từ \(P\) tới máy \(t\), dùng các máy khác làm đỉnh trung gian và trọng số cạnh là khoảng cách \(L_1\). Với ma trận \(A_{uv}=dist(u,v)\), phép “nhân” là

tức nhân ma trận trong đại số max-plus. Bình phương lặp cho ma trận độ dài đúng \(2^k\) bước. Nhân vector \(dist(P,t)\) với các ma trận cho toàn bộ \(U_t\) sau một số bước; số bước đủ khi tồn tại \(t\) với \(U_t\ge dist(Q,t)\).

Cách trực tiếp tính một lũy thừa trong \(O(N^3\log i)\) rồi nhị phân \(i\) cho \(O(N^3\log^2 M)\), vẫn có thể qua nếu cài đặt nhanh. Để bỏ một thừa số log, tiền xử lý \(A^{2^k}\) trong \(O(N^3\log M)\). Chọn khoảng nhị phân \([lo,hi)\) có độ dài là lũy thừa hai; tại mỗi bước, phần tăng từ \(lo\) đến trung điểm cũng là một lũy thừa hai, nên chỉ cần nhân vector hiện tại với đúng một ma trận đã có, tốn \(O(N^2)\). Tổng là \(O(N^3\log M)\) thời gian và \(O(N^2\log M)\) bộ nhớ.

Vì sao các bán kính luôn là một khoảng

Sau một lần dùng máy \(t\), tập đích là mặt của “cầu” \(L_1\) tâm \(t\) bán kính \(dist(P,t)\). Các mặt này đều đi qua \(P\), nên hợp của chúng liên thông và liên tục. Nếu lần tiếp theo dùng máy \(u\), bán kính mới có thể là khoảng cách từ \(u\) tới bất kỳ điểm nào trong tập đang đạt được. Ảnh của một tập liên thông qua hàm khoảng cách liên tục là một khoảng; vì thế ta nhận toàn bộ các bán kính giữa giá trị nhỏ nhất và lớn nhất, không bị lỗ hổng.

Mỗi vành cầu ở bước kế tiếp vẫn chứa \(P\), do ta luôn được phép dùng một máy để dịch chuyển một điểm về chính nó. Vì vậy các vành của mọi tâm lại giao nhau và hợp tiếp tục liên thông. Quy nạp này vừa chứng minh biểu diễn bằng \([L_{t,i},U_{t,i}]\) là chính xác, vừa chứng minh mọi điểm đạt được sau \(i\) lần cũng đạt được sau mọi số lần lớn hơn.

Đối với biên gần, ba trường hợp trong công thức có diễn giải hình học trực tiếp: nếu \(t\) ở ngoài cầu ngoài của \(u\), khoảng cách gần nhất là khoảng cách hai tâm trừ bán kính ngoài; nếu \(t\) nằm trong lỗ cầu trong, đó là bán kính trong trừ khoảng cách hai tâm; còn nếu \(t\) nằm ngay trong vành đạt được thì khoảng cách bằng 0. Lấy nhỏ nhất trên mọi \(u\) cho toàn bộ hợp.

Khi \(N\ge2\), khoảng cách giữa hai máy là dương. Do đó cực đại của các \(U\) tăng nghiêm ngặt qua từng vòng, còn cực tiểu của các \(L\) giảm nghiêm ngặt cho tới lần đầu bằng 0. Các đại lượng là số nguyên nên mỗi vòng thay đổi ít nhất 1. Với miền tọa độ gồm \(2M+1\) giá trị trên mỗi trục, không quá \(3M\) vòng đủ để biên ngoài phủ mọi vị trí đích hợp lệ. Trường hợp \(N=1\) khác hẳn: dùng lại duy nhất một máy không thay đổi bán kính, nên nếu một lần không đến được \(Q\) thì mãi mãi không đến được.

Tối ưu tìm số bước ở Test Set lớn

Trong trường hợp còn lại sau các kiểm tra 1 và 2 bước, ta đã đổi vai để \(dist(P,t)<dist(Q,t)\) với mọi máy \(t\). Khi đó \(Q\) nằm ngoài tất cả cầu ban đầu. Biên trong chỉ co nên không thể cản \(Q\); thời điểm đầu tiên một \(U_{t,i}\) chạm \(dist(Q,t)\) chính là đáp án.

Công thức max-plus cho phép ghép một đường đi đúng \(a\) cạnh với một đường đúng \(b\) cạnh qua mọi đỉnh trung gian, thu được đường dài nhất đúng \(a+b\) cạnh. Bình phương ma trận lần lượt tạo các độ dài \(1,2,4,8,\ldots\). Nếu mỗi lần nhị phân lại tự tính một lũy thừa thì mất \(O(N^3\log^2 M)\). Cách nhanh hơn tiền xử lý một lần mọi ma trận lũy thừa hai. Giữ cận dưới cùng vector độ dài tương ứng; khi thử trung điểm, nhân vector ấy với ma trận ứng với phần chênh là lũy thừa hai. Nếu đã chạm đích thì hạ cận trên, nếu chưa thì nhận vector thử làm vector cận dưới. Nhờ độ dài khoảng tìm kiếm luôn là lũy thừa hai, mọi ma trận cần dùng đều đã được tiền xử lý.

Phân tích chính thức lưu ý phương án \(O(N^3\log^2 M)\) vẫn có thể chạy trong vài phút với ngôn ngữ nhanh, còn bản loại một hệ số log chạy trong vài giây. Tất cả số liệu khoảng cách và tổng đường đi phải dùng kiểu nguyên đủ rộng cho tọa độ \(10^{12}\) và số bước được xét.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2017, World Finals, bài Teleporters; kho Google Coding Competitions (Apache-2.0).