Test Set 1

Để hình thức hóa lập luận, đồng thời thu được thuật toán và chứng minh đúng, ta dùng lý thuyết đồ thị. Xét đồ thị vô hướng \(G\) có \(RC+1\) đỉnh: một đỉnh cho mỗi ô của tranh và một đỉnh đặc biệt gọi là gốc. Nối mỗi cặp ô kề cạnh bằng một cạnh độ dài \(D\). Với mỗi ô cố định có độ sáng \(v\), thêm cạnh từ gốc đến ô ấy, độ dài \(v\).

Gọi \(p(c)\) là độ dài đường đi ngắn nhất trong \(G\) từ gốc đến đỉnh biểu diễn ô \(c\).

Tính chất 1

\(p(c)\) là cận trên của giá trị có thể gán cho \(c\). Xét đường đi \(k\) cạnh từ gốc đến \(c\), tổng độ dài \(p(c)\):

Theo cách dựng \(G\), \(a_1\) là ô cố định; gọi giá trị của nó là \(v\). Cạnh \((\text{gốc},a_1)\) dài \(v\), còn mọi cạnh \((a_i,a_{i+1})\) dài \(D\), nên \(p(a_i)=v+(i-1)D\). Hiển nhiên \(p(a_1)=v\) là cận trên của giá trị \(v\). Theo quy nạp, nếu \(p(a_i)\) là cận trên cho \(a_i\) thì \(p(a_{i+1})=p(a_i)+D\) là cận trên cho \(a_{i+1}\), bởi hai ô kề nhau không được chênh quá \(D\).

Tính chất 2

Nếu \(c\) là ô cố định giá trị \(v\) và \(p(c)\ne v\), bộ test vô nghiệm. Vì có cạnh \((\text{gốc},c)\) dài \(v\), ta luôn có \(p(c)\le v\). Nếu \(p(c)<v\), Tính chất 1 nói rằng không thể gán \(v\) cho \(c\).

Tính chất 3

Nếu \(p(c)\) đúng bằng giá trị đã gán cho mọi ô cố định \(c\), bộ test khả thi; gán \(p(c)\) cho mỗi ô chưa cố định là một phép gán hợp lệ có tổng lớn nhất. Tiền đề bảo đảm các ô cố định giữ nguyên giá trị, nên chỉ cần kiểm tra hai ô kề nhau không chênh quá \(D\). Với hai ô kề \(c,d\), \(G\) có cạnh \((c,d)\) dài \(D\); theo định nghĩa đường đi ngắn nhất,

Vậy phép gán hợp lệ. Theo Tính chất 1, nó gán cho từng ô giá trị lớn nhất có thể, nên tổng cũng lớn nhất.

Từ đó có thuật toán cho bộ nhỏ: dùng Dijkstra tính đường đi ngắn nhất từ gốc đến mọi ô, rồi dùng Tính chất 2 kiểm tra vô nghiệm. Nếu khả thi, đáp án là tổng \(p(c)\) trên mọi ô. Dijkstra chạy trong \(O(RC\log(RC))\); kiểm tra Tính chất 2 và cộng tổng đều mất \(O(RC)\). Tổng thể là \(O(RC\log(RC))\), thoải mái trong giới hạn bộ nhỏ.

Một cách tương tự nhưng tránh ngôn ngữ đồ thị là nhận xét rằng theo tính bắc cầu, ô cách ô cố định giá trị \(v\) đúng \(S\) bước trực giao không thể lớn hơn \(v+SD\). Vì vậy, nếu hai ô cố định cách nhau \(S\) bước mà độ sáng chênh hơn \(SD\), bộ test vô nghiệm. Ngược lại, nếu không có cặp nào vi phạm thì có thể chứng minh bộ test khả thi; phép gán tổng lớn nhất gán cho mỗi ô giá trị nhỏ nhất trong các \(v+SD\) tương ứng với mọi ô cố định — chính là \(p\) ở trên. Kiểm tra mọi cặp ô cố định mất \(O(N^2)\) và dựng phép gán mất \(O(RCN)\), nên tổng thể \(O(RCN)\), cũng đủ qua bộ nhỏ. Có thể chứng minh trực tiếp các khẳng định này, nhưng ký hiệu đồ thị làm lập luận dễ hơn và hai cách thực chất là một. Cách đồ thị còn trực tiếp cho lời giải bộ nhỏ hiệu quả hơn.

Test Set 2

Lưới của bộ lớn quá lớn để duyệt từng ô, nên cần cách khác. Tuy vậy, nền tảng của bộ nhỏ vẫn rất hữu ích. Ta giữ nguyên định nghĩa \(G\) và \(p\).

Tính chất 4

Với mọi ô \(c\), tồn tại một đường đi ngắn nhất trong \(G\) từ gốc đến \(c\):

trong đó \(a_1\) là ô cố định và tồn tại chỉ số \(i\) sao cho cạnh \((a_j,a_{j+1})\) là bước ngang khi và chỉ khi \(j<i\). Nói cách khác, đường đi từ gốc đến một ô cố định, sau đó đi ngang không hoặc nhiều bước, rồi đi dọc không hoặc nhiều bước. Nếu \(k-1\) bước cuối của một đường ngắn nhất bất kỳ gồm \(h\) bước ngang và \(k-1-h\) bước dọc, thực hiện \(h\) bước ngang trước rồi các bước dọc sau vẫn tới cùng đích. Mọi cạnh ngang và dọc đều dài \(D\), nên đường mới vẫn ngắn nhất.

Gọi ma trận \(R\times C\) ban đầu là \(M\). Ta nén tọa độ để chỉ xét phần đáng chú ý. Một hàng hoặc cột là đáng chú ý nếu nằm ở biên — hàng trên, hàng dưới, cột trái hoặc cột phải — hoặc chứa ít nhất một ô cố định. Ma trận con đáng chú ý \(M'\) thu được bằng cách xóa mọi hàng và cột không đáng chú ý. \(M'\) chứa mọi ô cố định của \(M\) và có thể chứa thêm ô chưa cố định; kích thước không vượt \((N+2)^2\), nhỏ hơn rất nhiều so với \(RC\) ở các trường hợp lớn nhất.

Định nghĩa \(G\) và \(p\) trên \(M\) như trước. Đồng thời dựng đồ thị nhỏ hơn \(G'\) gồm đỉnh gốc và các ô thuộc \(M'\). Với mỗi ô cố định \(c\) giá trị \(v\), \(G'\) có cạnh \((\text{gốc},c)\) dài \(v\); do \(M'\) chứa mọi ô cố định, gốc và mọi cạnh đi ra của gốc giống hệt trong \(G\). \(G'\) còn nối hai ô kề trực giao trong \(M'\). Độ dài cạnh \((c,d)\) là \(SD\), với \(S\) là khoảng cách theo số bước trực giao giữa \(c\) và \(d\) trong ma trận gốc \(M\).

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_9069d5d0.png

Trong hình, ma trận đầu vào có ba ô cố định. Ba hàng và bốn cột đáng chú ý được tô đỏ nhạt; các giao điểm của hàng và cột đáng chú ý được tô đỏ đậm. Các ô đỏ đậm tạo thành \(M'\) và các đỉnh của \(G'\) ngoài gốc. Ô cố định chứa \(3\) có hai hàng xóm trong \(G'\). Cạnh đến hàng xóm dọc dài \(2D\) vì hai ô cách nhau hai bước trong \(M\); tương tự, cạnh đến hàng xóm ngang dài \(3D\).

Khi đã có \(G'\), gọi \(p'(c)\) là khoảng cách ngắn nhất trong \(G'\) từ gốc đến mỗi ô \(c\) của \(M'\).

Tính chất 5

Với mọi ô \(c\) trong \(M'\), \(p'(c)=p(c)\). Để chứng minh, xét đường đi ngắn nhất trong \(G\) từ gốc đến \(c\) có dạng của Tính chất 4:

Nếu cạnh đi vào \(a_i\) nằm ngang và cạnh đi ra nằm dọc, tức \(a_i\) là góc duy nhất của đường đi, thì \(a_i\) thuộc \(M'\): nó cùng hàng với ô cố định \(a_1\), nên hàng ấy đáng chú ý, và cùng cột với \(a_k=c\in M'\), nên cột ấy đáng chú ý. Giữa \(a_1\) và \(a_i\) chỉ có các bước ngang; ta có thể “bỏ qua” những \(a_j\) không thuộc \(M'\), vì độ dài cạnh tương ứng trong \(G'\) đúng bằng tổng độ dài các cạnh trung gian. Lập luận tương tự áp dụng cho các bước dọc từ \(a_i\) đến \(a_k\).

Tính chất 5 cho phép dùng thuật toán tương tự trên \(G'\) để phát hiện vô nghiệm: tính \(p'\), suy ra \(p'(c)=p(c)\) cho mọi ô cố định, rồi kiểm tra Tính chất 2. Với trường hợp khả thi, vẫn cần tính tổng \(p(c)\) trên toàn bộ ô mà không thể liệt kê tường minh.

Xét ô \(c\) ở hàng \(i\), cột \(j\) của \(M\). Gọi \(i_0\) là hàng đáng chú ý lớn nhất không vượt \(i\), và \(i_1\) là hàng đáng chú ý nhỏ nhất không nhỏ hơn \(i\). Nếu \(i\) đáng chú ý thì \(i_0=i=i_1\); nếu không thì \(i_0<i<i_1\). Tương tự, \(j_0,j_1\) là các cột đáng chú ý gần \(j\) nhất về hai phía. Gọi tối đa bốn ô

thuộc \(M'\) là các ô bao quanh \(c\).

Tính chất 6

Với mỗi ô chưa cố định \(c\) ở hàng \(i\), cột \(j\) của \(M\), có một đường đi ngắn nhất từ gốc đến \(c\) trong \(G\) đi qua một ô bao quanh. Chứng minh tương tự Tính chất 4: sau bước từ gốc đến ô cố định thích hợp \(a_1\), mọi đường dùng số bước ngang và dọc tối thiểu có cùng tổng độ dài. Luôn có một ô bao quanh gần \(a_1\) hơn \(c\), nên ta có thể chọn đường đi qua ô ấy.

Từ Tính chất 6, dựng \(G'\), tính \(p'\), rồi giải riêng từng ma trận con liên tiếp của \(M\) được giới hạn bởi các hàng và cột đáng chú ý. Mỗi bài toán con là một phiên bản bài gốc với đúng bốn góc cố định. Biên của các bài toán con bị chồng lặp, nhưng chỉ cần trừ phần trùng khỏi tổng. Tính tổng phần trùng dùng vài nhận xét đơn giản cũng cần cho trường hợp bốn góc; do đó ta tập trung vào bài toán: với kích thước ma trận và giá trị bốn góc, tính tổng modulo \(10^9+7\).

Không được lấy modulo khi tính \(p\) hoặc \(p'\), vì phép so sánh đường đi dùng bất đẳng thức mà modulo không bảo toàn. Nếu \(U\) là cận trên của các giá trị cố định, đường dài nhất có nhiều nhất \(2U\) bước, nên giá trị lớn nhất của \(p\) không quá \(U+2UD\le U+2U^2\). Với \(U\le10^9\), số này vừa số nguyên có dấu \(64\) bit; chỉ cần modulo ở giai đoạn cộng tổng.

Gọi ma trận bốn góc là \(A\), với tl, tr, bl, br lần lượt là góc trên trái, trên phải, dưới trái và dưới phải. Như ở bộ nhỏ, giá trị mỗi ô do một trong bốn góc quyết định. Sự tồn tại của cây đường đi ngắn nhất cho thấy miền ô do từng góc quyết định — phá hòa theo một thứ tự ưu tiên tùy ý — là liên thông.

Với góc \(x\) và ô \(c\), định nghĩa ảnh hưởng \(i(x,c)\) là giá trị cố định tại \(x\) cộng \(SD\), trong đó \(S\) là khoảng cách trực giao từ \(x\) đến \(c\). Ảnh hưởng nhỏ hơn là mạnh hơn. Góc quyết định giá trị của một ô là bất kỳ góc nào có ảnh hưởng mạnh nhất.

Xét hàng trên cùng: tl mạnh hơn tr trên một đoạn liên tiếp bên trái, còn tr mạnh hơn trên một đoạn liên tiếp bên phải; có thể có một ô duy nhất hòa nhau. Cột nơi ảnh hưởng mạnh nhất chuyển từ tl sang tr là như nhau trên mọi hàng: trên hàng thứ \(i\) tính từ trên xuống, hai giá trị ảnh hưởng đúng bằng giá trị trên hàng đầu cộng cùng \(iD\), nên lựa chọn giữa tl và tr không đổi trong mỗi cột. Điều tương tự đúng với mỗi cặp góc không đối diện; có bốn cặp như vậy. Các đường phân chia miền ảnh hưởng của chúng gồm tối đa hai đường dọc và hai đường ngang, có thể trùng nhau, chia \(A\) thành tối đa chín phần. Trừ phần giữa, mỗi phần có đúng một góc ảnh hưởng mạnh nhất và được tính theo cùng một công thức.

Xét ma trận \(r\) hàng, \(c\) cột chỉ chịu ảnh hưởng của một góc giá trị \(v\). Tổng của hàng chứa góc ấy là

tính được bằng công thức tổng cấp số cộng. Mỗi hàng tiếp theo có tổng lớn hơn hàng trước \(cD\), vì mỗi cột tăng thêm \(D\). Lại thu được tổng của một hàm tuyến tính đã biết, cũng rút gọn bằng công thức ấy.

Phần giữa của \(A\) chịu ảnh hưởng từ hai góc đối diện; cặp góc nào tùy thứ tự các đường phân chia. Lại chia nó thành tối đa ba phần: các hàng chỉ chịu ảnh hưởng của góc thứ nhất, các hàng chỉ chịu ảnh hưởng của góc thứ hai, và các hàng chịu ảnh hưởng của cả hai. Hai phần đầu được cộng tương tự trường hợp một góc. Phần còn lại là một hình chữ nhật chia thành hai miền bậc thang theo ảnh hưởng. Tổng mỗi miền bậc thang là tổng trên một đoạn của một hàm bậc hai, có thể rút gọn bằng công thức tổng đa thức quen thuộc.

Đến đây lời giải hoàn tất. Còn nhiều chi tiết kỹ thuật, đặc biệt là biến đổi toán học, không được phân tích chính thức triển khai từng bước. Nhóm tác giả khuyến khích người đọc tự điền các khoảng trống và nhờ cộng đồng hỗ trợ nếu cần; đây là bài luyện tập rất tốt cho cuộc thi tiếp theo.

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2017, Vòng 3, bài Slate Modern.