Phân tích bài Endless Knight

Tập dữ liệu nhỏ có thể được giải bằng quy hoạch động hai chiều đơn giản. Thực tế, đây rõ ràng là bài dễ nhất mà hầu hết các thí sinh tìm thấy trong vòng này. Ngược lại, tập dữ liệu lớn lại trở thành bài khó nhất, chỉ có 32 thí sinh giải được.

Dưới đây chúng tôi phác thảo ba kỹ thuật có thể sử dụng trong bài toán này.

Phần A. Một sự đơn giản hóa thú vị

Hầu hết mọi người đều quen thuộc với các bước đi trên lưới từ \((0, 0)\) đến \((m, n)\), trong đó mỗi bước người ta có thể tăng hàng thêm 1 hoặc tăng cột thêm 1. Tổng số bước đi như vậy là số nhị thức \((m+n)\) chọn \(n\). Một lý do đơn giản là tập hợp các đường đi tương ứng 1-1 với các cách bạn chọn \(m\) bước cho các lần di chuyển dọc trong số \((m+n)\) bước.

Nếu không có đá, có thể thấy tình huống trong bài toán này khá giống. Thực tế, chúng về bản chất là giống nhau. Sau một phép biến đổi dữ liệu vào, chúng ta có thể quên quân mã đi và tập trung vào các bước đi trên lưới thông thường.

Trong bài toán của chúng ta, hai loại nước đi mà quân mã có thể thực hiện tương ứng với các vectơ \(u = (1, 2)\) và \(v = (2, 1)\). Tập hợp các vị trí có thể tiếp cận tạo thành một lưới với \(u, v\) làm cơ sở. Để tìm tọa độ của \((r, c)\) trong hệ thống mới là vấn đề biến đổi tuyến tính giữa hai cơ sở. Trong bài toán của chúng ta, nó đơn giản như sau:

Giải hệ phương trình, chúng ta nhận được \(r+c \equiv 2 \pmod 3\), và

Chúng tôi minh họa bằng hình ảnh sau đây:

Khi đọc dữ liệu vào, chúng ta có thể biến đổi các điểm sang hệ thống mới và loại bỏ bất kỳ điểm nào không thể tới được. Giả sử đích đến là tới được, nếu không chúng ta chỉ cần xuất 0. Chúng ta cũng có thể bỏ qua bất kỳ tảng đá nào có số hàng hoặc số cột vượt quá đích đến. Tóm lại, bây giờ chúng ta đang ở trong một lưới hình chữ nhật trong hệ tọa độ mới.

Phần B. Ý tưởng then chốt

Lưu ý rằng có một hạn chế quan trọng trong bài toán của chúng ta: có tối đa 10 tảng đá. Ý tưởng then chốt cho giải pháp của chúng ta — mặc dù các giải pháp khác cũng khả thi — là nguyên lý bao hàm - loại trừ (inclusion-exclusion principle).

Gọi \(S\) là bất kỳ tập con nào của các tảng đá (bao gồm cả tập rỗng). Định nghĩa \(f(S)\) là số cách chúng ta có thể đi bộ từ điểm xuất phát đến đích và đi qua mọi tảng đá trong \(S\), và có thể đi qua một số tảng đá khác.

Lưu ý thêm: Chúng tôi nhắc lại bài toán Ugly Numbers ở Vòng 1C. Ở đó, chúng ta cần xem xét các bội số của 2, 3, 5 và 7. Một số giải pháp có thể được xem như là một ứng dụng của nguyên lý bao hàm - loại trừ, mặc dù điều đó không nhất thiết phải có để giải bài toán đó.

Phần C. Tính n chọn k mod 10007?

Bây giờ chúng ta cần tính \(f(S)\) cho bất kỳ \(S\) nào. Hãy sắp xếp các tảng đá trong \(S\) từ trái sang phải, và đối với các tảng đá trên cùng một cột, hãy chọn tảng đá cao hơn trước. Rõ ràng là nếu một tảng đá đứng sau lại cao hơn một tảng đá đứng trước, thì \(f(S) = 0\) — không có cách nào để đi qua tất cả các tảng đá trong \(S\).
Ngược lại, tập hợp \(S\) đã sắp xếp tạo thành một chuỗi từ góc trên bên trái đến góc dưới bên phải:

Chúng ta có thể xem bất kỳ đường đi nào đi qua tất cả \(k\) tảng đá là gồm \((k+1)\) giai đoạn. \(f(S)\) là tích của số cách chúng ta có thể thực hiện mỗi giai đoạn. (Đây là một nguyên lý đếm quan trọng khác. Nó quan trọng và hiển nhiên đến mức thông thường người ta không gọi nó bằng tên. Nhưng nó có tên — quy tắc nhân.)

Bây giờ, chúng ta quay lại bài toán cổ điển ở đầu bài phân tích này. Gọi \(m = (r_i - r_{i-1})\) và \(n = (c_i - c_{i-1})\), số cách chúng ta có thể thực hiện giai đoạn thứ \(i\) chính là \((m+n)\) chọn \(n\).

Vậy, đây đã là kết thúc của câu chuyện chưa? Chưa hẳn. Nhiều thí sinh đã thất bại ở bài toán này vì việc tính \(A\) chọn \(B \pmod{10007}\) một cách nhanh chóng và chính xác là một điều lắt léo. Trong bài toán này, cả \(A\) và \(B\) đều có thể ở bậc \(10^8\). Để tính \(A\) chọn \(B \pmod P\) với \(P\) là số nguyên tố, người ta cần một số kỹ thuật. Có nhiều cách thông minh bạn có thể tìm thấy, như tính trước \(N!\) cho mọi \(N\), tính trước nghịch đảo của mỗi số \(\pmod P\), tận dụng tính chu kỳ của các số trong giai thừa.
Điều chúng tôi muốn giới thiệu dưới đây là một định lý hay không được biết đến rộng rãi như nó nên có. Nó loại bỏ tất cả những lo lắng về các bội số của \(P\). Nó không phải là một định lý khó, nhưng trông rất đẹp và đặc biệt hữu ích cho bài toán này.

Định lý Lucas: Giả sử \((n_t n_{t-1} \dots n_0)\) và \((k_t k_{t-1} \dots k_0)\) là biểu diễn của \(n\) và \(k\) trong hệ cơ số \(P\), trong đó \(P\) là một số nguyên tố. Khi đó \((n \text{ chọn } k)\) tương đương với tích của \((n_i \text{ chọn } k_i)\) trong \(\mathbb{Z}_P\).

Dưới đây là hàm choose từ mã Haskell tuyệt đẹp của Reid.

choose :: Int -> Int -> Int10007
choose n k | k > n = 0
choose n k | n < 10007 = 
  product [ (fromIntegral i) :: Int10007 |  i <- [n-k+1..n] ]
  / product [ (fromIntegral i) :: Int10007 | i <- [1..k] ]
choose n k = choose qn qk * choose rn rk
  where (qn, rn) = n $\mathbf{divMod}$ 10007
        (qk, rk) = k $\mathbf{divMod}$ 10007

Thông tin thêm

• Nguyên lý bao hàm - loại trừ
• Định lý Lucas
• Bước đi trên cầu thang (Staircase walk)

Để nghiên cứu về các điểm lưới, chúng tôi khuyên bạn nên tham khảo bất kỳ văn bản chuẩn nào về Hình học rời rạc.

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