Phân tích

Test Set 1

Với \(N \le 500\), ta luôn có thể dựng đáp án bằng cách đi qua các vị trí ngoài cùng bên trái: \((1,1),(2,1),\ldots,(\mathbf{N}-1,1),(\mathbf{N},1)\). Mọi số trên cạnh trái đều bằng 1, các vị trí liên tiếp kề nhau và đường đi có đúng \(N\) vị trí, nên tổng bằng \(N\).

Ta xử lý \(N=501\) bằng cách đi vòng để lấy số 2 ở hàng thứ ba rồi quay lại cạnh trái. Đường đi là \((1,1),(2,2),(3,3),(3,2),(3,1),(4,1),\ldots,(498,1)\). Năm vị trí đầu có tổng \(1+1+1+2+1=6\); từ \((4,1)\) đến \((498,1)\) có 495 số 1, nên tổng là 501 và số vị trí là \(5+495=500\).

Cách dựng cần \(O(N)\) thời gian và dữ liệu đầu ra, cùng \(O(1)\) bộ nhớ phụ ngoài kết quả.

Test Set 2

Vì chỉ có 1000 giá trị đầu vào có thể xét, ta có thể tìm trước một đáp án cho từng giá trị rồi mới nộp bài. Một cách là duyệt tam giác, chẳng hạn theo chiều rộng hoặc ngẫu nhiên, đồng thời không bao giờ dùng lại vị trí hay ghé quá 500 vị trí. Ta theo dõi tổng tích lũy; mỗi khi gặp một tổng chưa từng thấy, ta ghi lại dãy vị trí tạo ra nó. Khi tổng vượt 1000, ta quay lui hoặc bắt đầu lại bằng một đường ngẫu nhiên mới, rồi tiếp tục đến khi có đáp án cho mọi \(N\). Khó chứng minh trước rằng cách này chắc chắn thành công, nhưng ta có thể lạc quan vì vài hàng đầu có nhiều giá trị nhỏ để kết hợp. Trên thực tế, nó tìm được đầy đủ lời giải rất nhanh. Chi phí tiền xử lý phụ thuộc chiến lược duyệt; sau đó mỗi đáp án cần \(O(S)\) thời gian để xuất, với \(S \le 500\).

Một cách khác dựa trên việc các vị trí ngay bên phải cạnh trái — \((x,2)\) với \(x \ge 2\) — lần lượt mang các giá trị \(1,2,3,4,5,\ldots\). Ta đi từ đỉnh xuống số 1 tại \((2,1)\), rồi theo đường này đến số 2 tại \((3,2)\), số 3 tại \((4,2)\), v.v., cho tới khi bước kế tiếp làm tổng vượt mục tiêu. Khi đó, thay vì tiếp tục, ta đi sang trái tới số 1 trên cạnh trái rồi đi xuống cạnh ấy và lấy đúng số lượng số 1 còn thiếu.

Cách này đúng vì tổng trên đường các số tự nhiên không vượt \(N\); sau khi rẽ, mỗi bước tăng tổng đúng 1 nên ta đạt chính xác \(N\). Các bước luôn nối ô kề và không quay lại ô cũ. Vì tổng 45 số tự nhiên đầu tiên lớn hơn 1000, ta không cần quá 45 số 1 bổ sung, cũng không ghé quá 45 vị trí trên đường số tự nhiên. Do đó đường đi không quá 90 vị trí. Thuật toán chạy trong \(O(\sqrt N)\) thời gian và dùng \(O(1)\) bộ nhớ phụ ngoài kết quả.

Test Set 3

Có nhiều cách giải Test Set 3, nhưng một cách được ưa thích tận dụng tính chất: tổng các phần tử hàng thứ \(r\) bằng \(2^{r-1}\). Điều này xuất phát từ cách dựng hàng kế tiếp: mỗi phần tử của một hàng đóng góp vào hai phần tử ở hàng sau, nên tổng tăng gấp đôi.

Tính chất đó gợi ý viết \(N\) ở dạng nhị phân và xét từ bit thấp nhất. Nếu bit thấp thứ \(r\) (đếm từ 1) bằng 1, đường đi lấy toàn bộ hàng \(r\); nếu bằng 0, ta muốn bỏ qua hàng ấy. Chỉ cần 30 hàng đầu vì tổng hàng 31 là \(2^{30}\), lớn hơn \(N\) tối đa \(10^9\). Ngay cả lấy mọi ô trong 30 hàng đầu cũng chỉ dùng \(1+2+\cdots+30=465\) vị trí, không quá 500.

Mô tả này chưa dùng trực tiếp được vì đường đi phải liên tục nên không thể bỏ qua hẳn một hàng. Ta sửa lại như sau: đi xuống một cạnh toàn số 1 khi gặp các bit 0. Khi gặp bit 1, đi ngang qua toàn bộ hàng tương ứng và sang cạnh kia. Hai đầu của hàng kế tiếp luôn kề cạnh hiện tại nên đường đi liên tục. Cách này gần tạo được số cần tìm, nhưng có thể vượt vì đã lấy thêm một số 1 ở mỗi hàng ứng với bit 0. Số các số 1 thừa chắc chắn nhỏ hơn 30 vì ta chỉ ghé tối đa 30 hàng.

Vì vậy, ta dùng biến thể ấy để dựng \(N-30\) thay cho \(N\). Sau khi xong, ta nối thêm các số 1 trên cạnh hiện tại cho đến khi đạt \(N\). Với \(N \le 30\), chỉ cần đi xuống một cạnh qua \(N\) ô.

Cụ thể khi \(N>30\), đặt \(X=\mathbf{N}-30\) và xét 30 bit ứng với các hàng \(r=1,2,\ldots,30\). Nếu bit \(r-1\) của \(X\) bằng 1, đi ngang qua toàn bộ hàng \(r\) từ cạnh hiện tại sang cạnh kia; nếu bit bằng 0, chỉ lấy ô bằng 1 trên cạnh hiện tại. Gọi \(b\) là số bit 1 của \(X\). Các hàng đầy đủ đóng góp đúng \(X\); \(30-b\) hàng còn lại đóng góp \(30-b\), nên tổng sau 30 hàng là \(X+30-b=\mathbf{N}-b\). Đi tiếp \(b\) ô bằng 1 trên cạnh hiện tại sẽ đạt đúng \(N\).

Đường đi hợp lệ vì trong mỗi hàng đầy đủ ta đi đơn điệu từ cạnh này sang cạnh kia; trong hàng còn lại chỉ dùng một ô cạnh; điểm cuối mỗi hàng kề ô thích hợp của hàng kế tiếp. Ta không quay lên và không ghé lại ô nào. Phần 30 hàng dùng nhiều nhất 465 vị trí, đoạn cuối có \(b \le 30\) vị trí, nên tổng không quá \(495 \le 500\). Thuật toán tổng quát cần \(O((\log N)^2)\) thời gian và số vị trí đầu ra do có thể lấy trọn các hàng, cùng \(O(1)\) bộ nhớ phụ nếu xuất trực tiếp; với giới hạn bài, nó xuất tối đa 495 vị trí.

Còn có những cách ít cầu kỳ hơn. Một cách là đi xuống trung tâm các hàng, chẳng hạn \((1,1)\), \((2,1)\), \((3,2)\), \((4,2)\), \((5,3)\), v.v. Các số lớn nhất nằm ở đó nên tổng tăng rất nhanh. Khi bước xuống tiếp sẽ làm tổng tăng quá nhiều, ta chuyển sang đường cách trung tâm một bước rồi tiếp tục zíc zắc xuống dưới, và cứ thế. Cuối cùng ta tới cạnh toàn số 1 và lấy thêm đúng lượng còn thiếu.

Với cách thay thế này, phải cẩn thận không tăng tổng nhanh đến mức không thể "thoát" ra cạnh số 1. Cũng không được tới cạnh quá sớm, vì ta chỉ có thể lấy hữu hạn số 1 trong giới hạn 500 vị trí. Tuy vậy, không quá khó để làm cho phương pháp này hoạt động.

Dịch đầy đủ từ phân tích chính thức của Google Code Jam; các chứng minh và độ phức tạp được trình bày tường minh theo các cách dựng trên.