Phân tích

Đối với tập dữ liệu nhỏ, chúng ta có thể mô phỏng trực tiếp quá trình đi bộ qua khu rừng. Quá trình này có thể mất bao nhiêu bước? Có \(2^{10}\) trạng thái mà các cây trong các khoảng trống có thể có, và 10 trạng thái có thể có cho khoảng trống chúng ta đang đứng. Vì vậy, nếu chúng ta đến được khoảng trống cuối cùng, nó không thể mất quá \(10 \times 2^{10}\) bước, và nếu chúng ta thực hiện nhiều bước như vậy mà không đến được khoảng trống cuối cùng, chúng ta biết câu trả lời là Infinity.

Đối với tập dữ liệu lớn, \(40 \times 2^{40}\) bước là quá nhiều để mô phỏng trực tiếp, nhưng liệu một bộ test có thể đạt đến con số này không?

Một bộ test có thể được thiết kế để làm cho các khoảng trống mô phỏng một bộ đếm \(N-1\) bit. Khoảng trống đầu tiên có cả hai lối đi dẫn đến khoảng trống thứ hai. Mỗi khoảng trống sau đó tạo thành một chuỗi trong đó một lối đi dẫn đến khoảng trống tiếp theo và một lối đi dẫn ngược lại khoảng trống đầu tiên. Bất cứ khi nào đường đi dẫn ngược lại khoảng trống đầu tiên, trạng thái của các khoảng trống sẽ cho ra số \(N-1\) bit tiếp theo, và sau khi tất cả các số đó đã được tạo ra, nó mới có thể đến được khoảng trống cuối cùng. Điều này sẽ mất ít nhất \(2^{39}\) bước.

Vì vậy, chúng ta cần một giải pháp không mô phỏng từng bước riêng lẻ. Trong ví dụ trước, chúng ta dành \(2^{21}-2\) bước trong 20 khoảng trống đầu tiên giữa mỗi lần chúng ta ghé thăm bất kỳ khoảng trống nào trong 20 khoảng trống cuối cùng. Nếu chương trình của chúng ta có thể phát hiện ra rằng điều này luôn xảy ra, nó có thể mô phỏng \(2^{21}-2\) bước đó mà không cần thực hiện tất cả chúng một cách riêng lẻ. Chúng ta sẽ chỉ thực hiện \(2^{20}-3\) bước từ bất kỳ khoảng trống nào trong số 20 khoảng trống thứ hai, vì vậy tổng thời gian chạy sẽ hợp lý.

Một cách cài đặt cho phương pháp này là chia các khoảng trống thành hai tập \(A\) và \(B\) có kích thước xấp xỉ bằng nhau. Sau đó, chúng ta sử dụng quy hoạch động để tính toán, cho mỗi vị trí trong \(A\) và mỗi trạng thái trong \(2^{|A|}\) trạng thái của các khoảng trống trong \(A\), sẽ mất bao nhiêu bước để rời khỏi \(A\), khoảng trống nào trong \(B\) mà chúng ta sẽ hướng tới khi rời đi, và trạng thái mà các khoảng trống trong \(A\) sẽ để lại.

Sau khi thực hiện DP này, giải pháp của chúng ta sẽ mất một khoảng thời gian tỷ lệ thuận với số bước chúng ta thực hiện từ các khoảng trống trong \(B\) -- đối với mỗi bước đó, chúng ta mô phỏng bước đó, và nếu bước đó đưa chúng ta đến một khoảng trống trong \(A\), chúng ta tra cứu kết quả thích hợp của DP từ một bảng. Vì vậy, để làm cho giải pháp này hiệu quả, chúng ta cần chọn \(A\) và \(B\) sao cho chỉ có một số lượng nhỏ các bước được thực hiện từ các khoảng trống trong \(B\).

Tìm khoảng cách từ mỗi khoảng trống đến khoảng trống cuối cùng, trong đó khoảng cách được định nghĩa là số lượng lối đi bạn cần đi, giả sử trạng thái của các khoảng trống là tối ưu. Nếu không thể đến được khoảng trống cuối cùng từ một số khoảng trống, hãy đưa chúng vào một tập riêng biệt. Nếu chúng ta từng đến một trong số đó, câu trả lời là Infinity.

Chọn \(B\) là một nửa số khoảng trống còn lại gần nhất (với khoảng trống cuối cùng). Có thể có tối đa \(|B| \times 2^{|B|}\) bước được thực hiện từ các khoảng trống trong \(B\), bởi vì chúng ta không thể lặp lại một trạng thái của \(B\) mà không đến được khoảng trống cuối cùng. Con số này chỉ tối đa là \(20 \times 2^{20}\), vì vậy giải pháp này đủ nhanh.

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