Phân tích: Spiraling Into Control

Test Set 1 và 2

Có thể bạn từng gặp câu hỏi phỏng vấn kỹ thuật kinh điển yêu cầu đánh số mọi ô của lưới theo hình xoắn ốc. Trong bài này, làm vậy có thể hữu ích cho hai Test Set đầu. Tuy nhiên, Test Set cuối có thể và bắt buộc phải được giải mà không tạo và đánh số toàn bộ xoắn ốc; với \(N=9999\), ta phải lưu và đánh số gần \(10^8\) ô. Phần đó sẽ được xử lý sau.

Để tạo xoắn ốc đã đánh số, ta dựng lưới, bắt đầu ở ô góc trên trái và rẽ phải \(90\) độ mỗi khi gặp biên hoặc ô đã đánh số. Một cách gọn gàng là dùng mảng hướng \(((0,1),(1,0),(0,-1),(-1,0))\): hướng đầu \((0,1)\) giữ nguyên hàng và sang phải một cột; ba hướng còn lại lần lượt là xuống, trái và lên. Khi đang ở ô \((r,c)\) với hướng \((\Delta r,\Delta c)\), kiểm tra ô \((r+\Delta r,c+\Delta c)\). Nếu ô đó ngoài lưới hoặc đã đánh số, chuyển sang hướng kế tiếp, quay vòng khi hết mảng, rồi tính lại ô tiếp theo. Sau đó, dù có đổi hướng hay không, đánh nhãn ô hiện tại, tăng bộ đếm nhãn và đi tới ô kế. Dừng sau khi đánh nhãn ô thứ \(N^2\).

Với Test Set 1, có thể liệt kê vét cạn mọi đường đi hợp lệ, dùng cách đánh số xoắn ốc để biết bước nào được phép. Ta theo dõi các đường tắt trên mỗi đường đi và kiểm tra liệu có đường nào kết thúc sau đúng \(K\) bước. Vì gần như ở mỗi ô đều có lựa chọn dùng hoặc không dùng đường tắt, lời giải này có độ phức tạp hàm mũ.

Với Test Set 2, ta tinh chỉnh để không xét tường minh mọi đường đi. Ở mỗi ô, tạo một mảng có thể giữ tối đa một đường đi cho mỗi số bước đã dùng. Sau đó duyệt các ô theo thứ tự liên tiếp trên xoắn ốc. Với mỗi đường đi trong mảng của ô hiện tại, thử kéo dài nó sang mọi ô kề hợp lệ.

Ví dụ trong lưới \(5\times5\), ở ô \(1\) ban đầu chỉ có cách tới đó bằng \(0\) bước. Ta ghi cho hai hàng xóm hợp lệ \(2\) và \(16\) rằng có cách tới chúng trong \(1\) bước, bắt đầu từ ô \(1\). Sau đó, ở ô \(2\), ta ghi cho ô \(3\) và \(17\) rằng có cách tới chúng trong \(2\) bước với tiền tố \(1,2\), và tiếp tục tương tự. Khác biệt then chốt so với lời giải Test Set 1 là nếu một ô nhận một đường đi nhưng đã lưu đường đi khác có đúng cùng số bước, nó không lưu đường mới; nhờ đó số đường đi không bùng nổ.

Đây là một lời giải quy hoạch động hay ghi nhớ. Vì tại mỗi ô có nhiều nhất một đường tắt để cân nhắc, ta làm lượng công việc hằng số trên mỗi trạng thái. Bảng có kích thước \(N^2\times N\), nên thời gian là \(O(N^3)\).

Test Set 3

Để xử lý \(N\) tới \(9999\), ta phải làm hiệu quả ba việc:

• Với một giá trị \(K\), xác định liệu tồn tại đường đi đúng \(K\) bước hay không.
• Tìm đường đi như vậy.
• Từ tọa độ một ô, tìm số phòng của nó trên xoắn ốc.

Trước hết, các giá trị \(K\) sau là IMPOSSIBLE:

1. \(K<N-1\). Ngay cả khi đi thẳng về tâm nhất có thể và chỉ dùng đường tắt, vẫn không đủ số bước để tới đó.
2. \(K\) lẻ. Có thể thấy bằng lập luận bàn cờ: tưởng tượng lưới được tô như bàn cờ với ô góc trên trái màu đen. Đường chéo từ góc trên trái tới góc dưới phải toàn màu đen, nên ô trung tâm cũng đen. Mỗi bước đi theo phương ngang hoặc dọc đổi màu ô. Do đó, để kết thúc ở ô trung tâm màu đen, ta phải đi số bước chẵn.

Hóa ra đó là toàn bộ các trường hợp bất khả thi. Để thấy vì sao, hãy xem xoắn ốc gồm các vành vuông đồng tâm: vành \(0\) chỉ là ô trung tâm; vành \(1\) là tám ô bao quanh; vành \(2\) là mười sáu ô bao quanh vành \(1\); v.v. Với \(N=7\), các vành có dạng:

3333333
3222223
3211123
3210123
3211123
3222223
3333333

Trong vành \(1\), có ba đường tắt: đi vào vành \(0\) từ phía trên, phải hoặc dưới, lần lượt tiết kiệm \(6\), \(4\) hoặc \(2\) bước so với đi hết vành \(1\) rồi vào vành \(0\). Nhưng ta chỉ có thể dùng một trong ba.

Trong vành \(2\) và các vành ngoài hơn, để đơn giản chỉ xét những đường tắt cùng hàng hoặc cột với ô trung tâm. Có bốn đường như vậy, lần lượt tiết kiệm \(14,12,10,8\) bước. Nếu lấy đường tắt tiết kiệm \(8\) bước ở vành \(2\), ta không thể dùng đường tắt nào ở vành \(1\). Nhưng nếu lấy đường tiết kiệm \(14\) bước, ta vẫn có thể dùng cả ba đường tắt của vành \(1\).

Tương tự, ở vành \(3\), các đường tắt tiết kiệm \(22,20,18,16\) bước. Nếu dùng đường đầu tiên, ta vẫn còn quyền dùng cả bốn đường tắt ở vành \(2\).

Các quan sát này cho một lời giải dựng được cho mọi \(K\) chẵn có đáp án:

• Muốn tiết kiệm từ \(2\) đến \(22\) bước, lấy đúng đường tắt có mức tiết kiệm ấy.
• Muốn tiết kiệm từ \(24\) đến \(36\) bước, lấy đường tiết kiệm \(22\) bước rồi lấy đường cụ thể ở vành \(1\) hoặc \(2\) để đạt phần còn lại.
• Muốn tiết kiệm \(38\), \(40\) hoặc \(42\) bước, lấy các đường tiết kiệm \(22\) và \(14\) bước, rồi lấy đường tiết kiệm \(2\), \(4\) hoặc \(6\) ở vành \(1\).
• Không thể tiết kiệm từ \(44\) bước trở lên, vì khi đó \(K<N-1\) như đã chứng minh.

Tổng quát hóa chiến lược, gọi số bước cần tiết kiệm là \(s=N^2-1-K\), rồi đi từ vành ngoài cùng vào trong. Tại mỗi vành \(r\):

1. Nếu \(s\) không nhỏ hơn mức tiết kiệm của đường tắt lớn nhất, tức \(8r-2\), lấy đường đó, trừ \(8r-2\) khỏi \(s\), rồi sang vành \(r-1\).
2. Nếu \(s\) bằng mức tiết kiệm của một đường tắt khác trong vành \(r\), tức \(8r-4\), \(8r-6\) hoặc \(8r-8\), lấy đường ấy và dừng. Cần tránh trường hợp \(8r-8=0\), vì bước từ phòng \(N^2-1\) tới \(N^2\) không tiết kiệm gì và không phải đường tắt.
3. Nếu không thuộc hai trường hợp trên, bỏ qua mọi đường tắt ở vành \(r\) và sang vành \(r-1\).

Chỉ còn việc tìm số phòng ở hai đầu các đường tắt đã chọn. Không cần sinh toàn bộ xoắn ốc: số tại góc trên trái của các vành, bắt đầu từ tâm rồi đi ra ngoài, lần lượt là \(N^2\), \(N^2-8\), \(N^2-8-16\), \(N^2-8-16-24\), v.v. Công thức cho góc trên trái vành \(r\) là

Khi biết góc trên trái có số \(x\), ta dễ tìm các ô dùng cho đường tắt trên hàng hoặc cột trung tâm: chúng có số \(x+r\), \(x+3r\), \(x+5r\), \(x+7r\).

Có tổng cộng \((N+1)/2\) vành và mỗi vành chỉ cần \(O(1)\) công việc, nên lời giải là \(O(N)\) và dễ dàng vượt qua Test Set 3. Có những giá trị \(K\) buộc phải dùng một đường tắt ở mọi vành trừ ô trung tâm, nên nhìn chung không thể làm tốt hơn mức này.

Bài toán đã có thể còn tệ hơn

Nhóm tác giả từng cân nhắc trình bày bài mà không nhắc tới xoắn ốc: từ góc trên trái lưới \(N\times N\), hãy đưa ra đường đi tới ô trung tâm trong đúng \(K\) bước hoặc báo không thể. Một lời giải chính là tự nghĩ ra đường xoắn ốc và chiến lược của bài hiện tại. Tuy nhiên, cách trình bày ấy còn mở ra rất nhiều hướng đi tốn thời gian khác, trong khi bài vốn đã khó đối với bài đầu tiên của Vòng 2.

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 2, bài Spiraling Into Control.