Phân tích

Thông thường khi bạn đếm trong hệ cơ số 2, mỗi bit có một giá trị cố định: \(\{..., 8, 4, 2, 1\}\). Vì vậy, khi bạn đếm \(0000, 0001, 0010, 0011\), v.v., bạn sẽ nhận được dãy \([0, 1, 2, 3, ...]\). Trong bài toán này, chúng ta xem xét điều gì sẽ xảy ra nếu các bit có các giá trị ẩn, gọi là "giá trị bit", do chúng ta quy định. Ví dụ, nếu các bit có giá trị là \(\{..., 200, 10, 1\}\), thì bạn có thể nhận được dãy \([0, 1, 10, 11, 200, 201, ...]\).

Yêu cầu của bài toán là tìm số tiếp theo trong dãy được tạo ra. Để làm mọi thứ khó khăn hơn, chúng ta không nhất thiết phải bắt đầu từ \(0000\) hay \(0001\), vì vậy những gì có vẻ hiển nhiên như:

[1, 10, 11, 200, 201, ?, ...]

...có thể không phải vậy. Nó có thể đến từ các giá trị bit \(\{..., 200, 10, 1\}\), cho ra kết quả 210; nhưng nó cũng có thể đến từ các giá trị bit \(\{..., -1180, 1190, 990, 190, 1\}\). Nếu chúng ta bắt đầu đếm từ \(10000\), điều đó sẽ cho:

[-1180, -1179, -990, -989, -190, -189, 0, 1, 10, 11, 200, 201, 1000]

Giải pháp

Làm thế nào để giải quyết bài toán này? Hãy nhìn vào dãy được tạo ra ở trên và tìm kiếm các đặc điểm thú vị. Một điều có thể đập vào mắt bạn là cứ mỗi số thứ hai lại lớn hơn số trước đó 1 đơn vị, vì vậy hãy nhìn vào dãy các hiệu số giữa các số liền kề:

(1, 189, 1, 799, 1, 189, 1, 9, 1, 189, 1, 799)

Các hiệu số bằng \(1\) rất có ý nghĩa: cứ mỗi lần tăng thứ hai trong một số nhị phân, bit thấp nhất chỉ thay đổi từ \(0\) thành \(1\). Vì vậy, nếu dãy các hiệu số của bạn trông giống như \((x, a, x, b)\), hoặc \((a, x, b)\), thì hiệu số tiếp theo phải là \(x\). Nhận ra điều này sẽ giúp bạn giải quyết được tập dữ liệu nhỏ.

Nhưng chúng ta có thể đẩy điều này đi bao xa? Hãy loại bỏ tất cả những lần chỉ có bit thấp nhất thay đổi. Điều này để lại cho chúng ta dãy các hiệu số sau:

(189, 799, 189, 9, 189, 799)

Ở đây, cứ mỗi số thứ hai lại là \(189\). Điều đó cũng có lý: cứ mỗi lần tăng thứ tư trong một số nhị phân là giống nhau, thay đổi hai bit thấp nhất từ \(01\) thành \(10\). Tương tự, cứ mỗi lần tăng thứ tám sẽ thay đổi ba bit thấp nhất từ \(011\) thành \(100\).

Vậy chúng ta đang ở đâu? Tìm kiếm sự lặp lại; xem liệu chúng ta có thể sử dụng nó không; và nếu không, hãy loại bỏ nó. Ví dụ, nếu dãy được tạo ra là:

[0, 1, 3, 4, 7, 8, 17, 18, 21, 22, 24, 25]

Dãy các hiệu số là:

(1, 2, 1, 3, 1, 9, 1, 3, 1, 2, 1)

Vì dãy kết thúc bằng số lặp lại, \(1\), chúng ta chưa biết số tiếp theo là gì. Loại bỏ các số \(1\), chúng ta đi đến:

(2, 3, 9, 3, 2)

Aha! Hiệu số tiếp theo phải là \(3\), và câu trả lời là \(28\). Nếu cách đó không hiệu quả, chúng ta sẽ tiếp tục đệ quy cho đến khi tìm thấy câu trả lời.

Nhưng nếu dãy các hiệu số là:

(1, 2, 1, 2, 1)

Ở đây, chúng ta không thể biết bit thấp nhất đang thay đổi cho hiệu số là \(1\) hay hiệu số là \(2\), vì vậy chúng ta không thể chắc chắn điều gì tiếp theo. Cuối cùng chúng ta cũng gặp vấn đề tương tự trong tất cả các dãy hiệu số sau:

(1, 2)
(3)
(4, 3, 4)
(5, 4, 5, 3, 5, 4, 5)
(6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6)

Ở đây KHÔNG THỂ tìm ra câu trả lời: \((1, 2)\) đó có thể là \((1, 2, 1)\) hoặc \((1, 2, 10, 2)\). \((4, 3, 4)\) có thể đến từ:

10001 10010 10011 10100 10101
(4, 3, 4, 3)

hoặc từ:

00100 00101 00110 00111 01000
(4, 3, 4, ?)

Không có cách nào để biết bạn đang ở đâu trong phạm vi \([0, 10^9]\), vì vậy bạn có thể sắp chạm vào một bit hoàn toàn mới mà bạn không hề biết.

Cách cài đặt và Độ phức tạp

Khi cộng các giá trị của các bit, chúng ta làm việc theo modulo \(10007\). Việc sử dụng số âm ở trên vẫn đúng trong không gian modulo: "-1180" mod \(10007\) là \(8827\), nghĩa là cộng \(8827\) vào bất kỳ số nào lớn hơn \(1180\) cũng giống như trừ đi \(1180\) từ nó.

Một điều hay của Code Jam là bạn có thể kiểm tra các giả định của mình. Khi viết bộ sinh dữ liệu cho bài toán này, tôi đã dùng một câu lệnh khẳng định rằng dãy hiệu phải có dạng \([x, a, x, b, x, c, ...]\) hoặc \([a, x, b, x, c, x, ...]\). Nhờ đó tôi phát hiện một lỗi trong mã của mình: tôi đã không lấy các hiệu theo modulo \(10007\)! Trong một cuộc thi trực tiếp, tôi vẫn sẽ có thời gian sửa lỗi đó và nộp bài.

Cuối cùng, có một giới hạn là "con cá đỏ" (thông tin gây nhiễu): đó là dãy không thể vượt quá \(10^9\). Không khó để thuyết phục bản thân rằng hạn chế này là vô nghĩa: bất kỳ dãy nào có độ dài \(1000\) không thể ảnh hưởng đến quá \(11\) bit riêng biệt, vì vậy không quan trọng nếu bit cao nhất là #13 hay #32.

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