Tập dữ liệu nhỏ (Small dataset)

Tập dữ liệu nhỏ không yêu cầu tìm giải pháp tối ưu, thay vào đó chấp nhận bất kỳ giải pháp nào giải quyết được vấn đề trong vòng 500 bước nhảy. Điều này cho phép nhiều cách tiếp cận khác nhau. Một trong những cách tiếp cận đó là: lưu ý rằng với hai bước nhảy liên tiếp theo hai hướng ngược nhau, bạn có thể di chuyển một đơn vị theo một hướng đã chọn. Bằng một chuỗi tối đa 200 cặp như vậy (tổng cộng tối đa 400 bước nhảy), bạn có thể đạt được bất kỳ điểm nào có \(|X|, |Y| \le 100\).

Cũng có những cách tiếp cận khác khả thi, ví dụ như tìm kiếm đường đi ngắn nhất, nếu người ta có thể chứng minh hoặc đoán rằng việc giới hạn không gian tìm kiếm là ổn. Hóa ra người ta thực sự có thể chỉ cần tìm kiếm một đường đi trong các điểm có \(|x|, |y| \le 100\), chúng ta sẽ thấy lý do tại sao ở phần tiếp theo. Do đó, thuật toán Dijkstra hoặc chỉ đơn giản là tìm kiếm theo chiều rộng (BFS) sẽ cung cấp một đường đi đủ ngắn đến mục tiêu.

Tập dữ liệu lớn (Large dataset)

Đối với tập dữ liệu lớn, chúng ta không chỉ cần trả về giải pháp tốt nhất có thể, mà còn phải xử lý các mục tiêu xa hơn, vì vậy không có cách tiếp cận nào ở trên sẽ hoạt động. Chúng ta sẽ bắt đầu với một vài quan sát đơn giản:

• Đầu tiên, nếu muốn đạt được mục tiêu trong \(N\) bước nhảy, ta phải có \(1 + 2 + \dots + N \ge |X| + |Y|\).
• Hơn nữa, nếu muốn đạt được mục tiêu trong \(N\) bước nhảy, tính chẵn lẻ của các số \(1 + 2 + \dots + N\) và \(|X| + |Y|\) phải giống nhau. Điều này là do tính chẵn lẻ của tổng độ dài các bước nhảy theo hướng Bắc-Nam phải khớp với tính chẵn lẻ của \(|Y|\), và tổng độ dài các bước nhảy Tây-Đông phải khớp với tính chẵn lẻ của \(|X|\).

Hóa ra nếu \(N\) thỏa mãn hai điều kiện này, thì có thể đạt được \((X, Y)\) với \(N\) bước nhảy.

Hãy xem xét một điểm \((X, Y)\) và bất kỳ \(N\) nào thỏa mãn hai điều kiện trên. Để ngắn gọn, giả sử \(|X| \ge |Y|\) và \(X \ge 0\) (dễ dàng đưa ra các lập luận đối xứng cho bốn trường hợp còn lại). Trong trường hợp này, chúng ta sẽ giả định bước di chuyển cuối cùng là sang hướng Đông (East). Điều này có nghĩa là \(N-1\) bước di chuyển đầu tiên phải đạt được \((X-N, Y)\). Chúng ta sẽ tiến hành đệ quy, vì vậy chúng ta chỉ cần chứng minh rằng \((X-N, Y)\) và \(N-1\) thỏa mãn các điều kiện trên.

Với \(N = 1\) hoặc \(2\), thật dễ dàng để liệt kê tất cả các \(X\) và \(Y\) khả thi. Với \(N = 1\), có bốn khả năng, và trong mỗi trường hợp, chiến lược của chúng ta đều tạo ra bước di chuyển chính xác. Với \(N = 2\), nếu chúng ta giả định \(X\) dương và lớn hơn \(|Y|\), các khả năng duy nhất là \((3, 0), (2, 1), (2, -1)\) và \((1, 0)\); sau bước di chuyển, chúng chuyển thành \((1, 0), (0, 1), (0, -1)\) và \((-1, 0)\) — tất cả đều thỏa mãn các điều kiện cho \(N = 1\).

Đối với \(N\) lớn hơn, điều kiện về tính chẵn lẻ là hiển nhiên — cả hai tính chẵn lẻ đang xét đều giữ nguyên nếu \(N\) chẵn, và cả hai đều thay đổi nếu \(N\) lẻ. Đối với điều kiện bất đẳng thức, nếu \(N \le X\), cả hai vế chỉ đơn giản là giảm đi \(N\), vì vậy trường hợp thú vị duy nhất là nếu \(X < N\). Tuy nhiên, trong trường hợp này, chúng ta di chuyển đến \((X - N, Y)\), và tổng các giá trị tuyệt đối là \(|X - N| + |Y| = N - X + |Y| \le N - X + X = N \le 1 + \dots + N - 1\). Do đó, các điều kiện được thỏa mãn sau một bước di chuyển, và chúng ta có thể tiếp tục với chiến lược của mình.

Logic này một lần nữa được chuyển thành mã đơn giản:

def Solve(x, y):
  N = 0
  sum = 0
  while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1:
    N += 1
    sum += N
  result = ""
  while N > 0:
    if abs(x) > abs(y):
      if x > 0: 
        result += 'E'
        x -= N
      else:
        result += 'W'
        x += N
    else:
      if y > 0:
        result += 'N'
        y -= N
      else:
        result += 'S'
        y += N
    N -= 1
  return result.reversed()

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