Test Set 1

Test Set 1 đủ nhỏ để giải bằng tay. Ta có thể làm nhanh hơn nhờ vài nhận xét:

• Mọi vị trí có \((X+Y)\) chẵn (trừ gốc tọa độ) — sau đây gọi là vị trí "chẵn" — đều không thể đến được. Ban đầu \(X,Y\) tại \((0,0)\) đều chẵn; chỉ cú nhảy đầu dài \(1\) là lẻ, mọi cú sau đều chẵn. Vì vậy, dù nhảy bao nhiêu lần, ta không thể từ gốc đến vị trí "chẵn" nào khác.
• Ngược lại, mọi vị trí "lẻ" đều có thể đến bằng không quá \(3\) bước.
• Có thể tận dụng đối xứng như giải thích mẫu số 2. Nếu EEN giải được \((3,4)\) thì WWS giải được \((-3,-4)\), EES giải được \((3,-4)\), v.v. Nhờ đối xứng ngang, dọc và chéo, thực chất chỉ có sáu trường hợp khác nhau!
• Có thể kiểm tra tính tối ưu như ở mẫu số 1. Vị trí có khoảng cách Manhattan \(|X|+|Y|\) bằng \(1\) cần ít nhất một bước; khoảng cách không quá \(3\) và \(7\) lần lượt cần ít nhất hai và ba bước. Nếu độ dài lời giải đạt các cận dưới này — điều thường xảy ra trừ khi ta đi đường vòng khác thường — thì lời giải hợp lệ.

Test Set 2

Từ các nhận xét trên, ta có thể tìm kiếm theo chiều rộng trên mọi đường nhảy cho đến khi đạt mọi vị trí "lẻ" \((X,Y)\) với \(-100\le X,Y\le100\). Mỗi vị trí như vậy đạt được trong không quá \(8\) bước. Các lời giải ngắn tối ưu do bản chất của BFS.

Test Set 3

Giả sử \((X,Y)=(7,10)\). Cú nhảy đầu dài \(1\) nên theo hướng nào? \(X\) cuối phải lẻ nhưng hiện đang chẵn, và chỉ cú nhảy này có thể đổi chẵn thành lẻ. Đi bắc hoặc nam làm \(Y\) lẻ, rồi không còn cơ hội biến \(Y\) về chẵn và \(X\) thành lẻ. Vì vậy phải đi tây hoặc đông. Tạm đoán đi tây; ta sẽ xét khả năng kia sau.

Cú đó đưa ta đến \((-1,0)\), tiếp theo cần nhảy \(2\) đơn vị. Có thể đưa bài toán về dạng ban đầu bằng hai thay đổi:

1. Tịnh tiến \((-1,0)\) thành gốc \((0,0)\) mới; đích trở thành \((8,10)\) thay vì \((7,10)\).
2. Đổi tỉ lệ để cú nhảy \(2\) đơn vị (sang một ô "lân cận") thành cú nhảy mới dài \(1\); đích trở thành \((4,5)\) thay vì \((8,10)\).

Xét lại quyết định đi tây: nếu đi đông, ta ở \((1,0)\) và sau phép biến đổi, đích mới là \((3,5)\). Đây là vị trí "chẵn" sau đổi tỉ lệ nên không thể đến! Vậy ta không có lựa chọn: phải đi tây mới có thể đến đích. Thật may là ta đã đoán đúng!

Bài toán giờ được "đặt lại": ta ở \((0,0)\) và cần đến \((4,5)\). Ta phải đi dọc vì \(5\) lẻ và chỉ có "một cơ hội" đổi chẵn thành lẻ. Đi bắc cho đích \((2,2)\) sau lần đổi tỉ lệ tiếp theo; đi nam cho \((2,3)\), vị trí "lẻ" cần chọn. Từ đó, đi nam biến đích thành \((1,2)\), rồi đi đông biến nó thành \((0,1)\). Lúc này có thể đi bắc thẳng đến đích, hoặc đi nam rồi vẫn có thể đến đích sau vài bước nữa (chẳng hạn thêm một bước nam rồi một bước bắc). Bài yêu cầu lời giải ngắn nhất nên phải đi thẳng đến đích. Đáp án là WSSEN.

Phương pháp có tính xác định: luôn chỉ có một lựa chọn trong bốn hướng. Hai hướng không làm đúng tọa độ trở thành lẻ bị loại. Hai trạng thái mới từ hai hướng còn lại chỉ khác nhau đúng \(1\) ở một tọa độ, nên một trạng thái "lẻ", một trạng thái "chẵn". Nếu vị trí "chẵn" chính là đích thì nhảy đến đó; nếu không phải chọn vị trí "lẻ".

Phân tích cũng cho thấy chỉ có lựa chọn khi một phương án nhảy thẳng đến đích, và rõ ràng ta nên chọn nó. Vì vậy phương pháp cho lời giải ngắn nhất. Lời giải cũng duy nhất, vì bỏ qua cơ hội đến thẳng đích chỉ tạo lời giải dài hơn.

Thời gian chạy là logarit theo độ lớn tọa độ, nên giải Test Set này cực kỳ nhanh!

Một màn gợi nhắc Code Jam!

Bài này là biến thể của bài Pogo tại Round 1C năm 2013. Nếu quen bài đó, phần phân tích có thể giúp đôi chút... nhưng giống một cây gậy pogo được thiết kế tốt, Expogo dù sao cũng không quá khó để nắm bắt.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 1B — Expogo.