Phân tích: Square Math

Bài toán sẽ dễ dàng hơn nhiều nếu chỉ có các dấu cộng. Với sự hiện diện của các dấu trừ, một biểu thức hợp lệ có thể đạt đến một giá trị lớn ở giữa, sau đó giảm dần về giá trị chúng ta đang tìm kiếm. Liệu đó có phải là câu trả lời ngắn nhất cho một truy vấn nhất định hay không?

Đường đi tốt nhất không thể quá dài

Trước hết, hãy ký hiệu một chữ số khác không trong hình vuông là pos nếu nó có ít nhất một lân cận là dấu cộng; gọi nó là neg nếu nó có một dấu trừ là lân cận. Một chữ số có thể vừa là pos vừa là neg. Chúng ta giả định rằng có cả chữ số pos và chữ số neg trong hình vuông. Gọi \(q\) là giá trị chúng ta đang tìm kiếm.

Gọi \(g\) là ước chung lớn nhất (GCD) của tất cả các chữ số trong hình vuông. Nếu \(g \neq 1\), để tìm được lời giải cho \(q\), \(q\) phải là bội số của \(g\). Chia tất cả cho \(g\), từ đây chúng ta có thể giả định rằng GCD của tất cả các số trong hình vuông là 1. Tình huống còn đơn giản hơn khi tất cả các số của chúng ta nằm trong khoảng từ 0 đến 9 -- trong trường hợp này, điều trên ngụ ý rằng phải có hai chữ số \(a\) và \(b\) trong hình vuông sao cho \(gcd(a, b) = 1\).

Trường hợp 1: \(a\) là pos và \(b\) là neg. Lấy bất kỳ đường đi ngắn nhất \(P\) từ \(a\) đến \(b\) trong hình vuông. Gọi \(q'\) là giá trị của đường đi này. \(q'\) nằm trong khoảng \([-200, 200]\). Gọi \(t = q - q'\). Chúng ta chứng minh trường hợp \(t \ge 0\); trường hợp còn lại tương tự.
Vì \(gcd(a, b) = 1\), một trong các số \(t, t+b, t+2b, \dots, t+(a-1)b\) là bội số của \(a\). Điều này có nghĩa là chúng ta có thể tìm các số không âm \(x\) và \(y\) sao cho \(ax - by = t\), trong đó \(y < a\) (do đó \(x < t/a + b\)). Chúng ta bắt đầu từ \(a\), vì nó là một chữ số dương, chúng ta sử dụng dấu cộng để lặp lại tại \(a\) \(x\) lần, sau đó đi theo \(P\). Sau khi đến \(b\), chúng ta sử dụng dấu trừ để lặp lại \(y\) lần. Đường đi vừa mô tả sẽ có giá trị bằng truy vấn \(q\).

Trường hợp 2: Cả \(a\) và \(b\) đều là pos, có một chữ số neg là \(c\). Nếu \(c\) nguyên tố cùng nhau với \(a\) hoặc \(b\), chúng ta xử lý như Trường hợp 1. Ngược lại, \(c\) phải là 6.
Chọn bất kỳ đường đi ngắn nhất \(P\) kết nối \(a, b,\) và \(c\). Giả sử nó có giá trị \(q'\). Chọn một số không âm \(z\) sao cho \(q - q' + 6z \ge ab - a - b + 1\). Chúng ta sử dụng một định lý cơ bản trong lý thuyết số ở đây:

Nếu hai số nguyên dương \(a\) và \(b\) nguyên tố cùng nhau, thì với mọi \(t \ge ab-a-b+1\), tồn tại các số nguyên không âm \(x\) và \(y\) sao cho \(ax+by=t\).

Để có câu trả lời cho truy vấn \(q\), chúng ta sử dụng đường đi \(P\), lặp lại \(a\) \(x\) lần với dấu cộng, \(b\) \(y\) lần với dấu cộng, và \(c\) \(z\) lần với dấu trừ.

Trường hợp 3: Cả \(a\) và \(b\) đều là neg. Trường hợp này tương tự như Trường hợp 2.

Do đó, chúng ta đã chứng minh được rằng đối với bất kỳ truy vấn nào có thể giải được, luôn có một đường đi không quá dài, cũng như bất kỳ tổng trung gian nào trên đường đi không thể quá lớn. Ước tính sơ bộ cho thấy bất kỳ đường đi nào cũng không thể vượt quá 1000 bước. Người ta có thể tìm được một giới hạn tốt hơn bằng cách phân tích kỹ lưỡng hơn.

Thuật toán

Giải pháp của chúng ta là BFS (tìm kiếm theo chiều rộng). Không gian tìm kiếm bao gồm tất cả các bộ \((r, c, v)\), trong đó \((r, c)\) là vị trí của một chữ số, và ký hiệu \(A(r, c, v)\) là đường đi tốt nhất có giá trị bằng \(v\) và kết thúc tại vị trí \((r, c)\).
Chúng ta biết có tối đa 200 cặp \((r, c)\) như vậy (\(20^2/2\)), và tối đa (thực tế ít hơn nhiều) 20000 giá trị \(v\) từ giới hạn chúng ta đã tìm thấy.

Sự khác biệt duy nhất so với BFS tiêu chuẩn là, do yêu cầu về thứ tự từ điển, chúng ta có thể cần cập nhật câu trả lời tại một nút. Nhưng chúng ta không bao giờ cần đẩy lại nó vào hàng đợi, vì nó chưa được mở rộng.

Dựa trên phân tích chính thức của Google Code Jam.