Phân tích: Hot Dog Proliferation

Bối cảnh

Phân tích này sẽ không liên quan đến xúc xích. Thay vì một con phố dài với hàng tỷ góc đường, hãy nghĩ về một dòng các số nguyên; thay vì những người bán hàng, hãy nghĩ về các con chip (quân cờ) -- suy cho cùng, các con chip dễ điều khiển hơn nhiều so với những người thật với xe đẩy xúc xích!

Chúng ta ký hiệu tổng số chip là \(n\). Ngoài ra, hãy gọi một cấu hình là ổn định nếu không có hai con chip nào chiếm cùng một điểm nguyên.

Nếu bạn thử chơi trò chơi này một lúc hoặc nếu bạn có trực giác tốt, bạn có thể nhận ra rằng đề bài hơi gây hiểu lầm. Hóa ra là bất kể bạn thực hiện bước di chuyển nào ở mỗi bước, cấu hình cuối cùng cũng như tổng số bước di chuyển bạn cần thực hiện sẽ luôn giống nhau.

Thật vậy, đây là một định lý nổi tiếng cho "trò chơi bắn chip" (chip-firing games), và kịch bản của chúng ta là một loại trò chơi bắn chip đặc biệt. Một cách trực quan, lý do tại sao các lựa chọn của bạn không quan trọng là vì (a) nếu bạn bỏ qua một bước di chuyển bây giờ, bạn vẫn sẽ phải thực hiện nó sau này, và (b) một bước di chuyển sẽ không làm thay đổi hiệu quả của một bước di chuyển khác sau đó. Điều này có nghĩa là mặc dù bạn có thể kiểm soát thứ tự các bước di chuyển, cuối cùng bạn sẽ luôn thực hiện cùng một tập hợp các bước di chuyển và chúng sẽ luôn có cùng một kết quả.

Quan sát này đủ để giải quyết dữ liệu nhỏ (small input). Chỉ cần tiếp tục thực hiện các bước di chuyển cho đến khi cấu hình ổn định và đếm xem mất bao lâu. Tuy nhiên, đối với dữ liệu lớn (large input), cần có thêm hiểu biết sâu sắc hơn. Một cấu hình có thể yêu cầu hơn \(10^{13}\) bước di chuyển để ổn định, vì vậy việc mô phỏng từng bước một là không khả thi. Một cách tối ưu hóa hiển nhiên là thực hiện nhiều bước di chuyển cùng lúc cho các đống chip rất lớn. Tuy nhiên, đáng ngạc nhiên là điều này không giúp ích được nhiều.

Có một vài cách khác nhau để tiến hành, và chúng ta sẽ thảo luận về hai trong số đó.

Các quan sát sơ bộ

Một cách rất hữu ích để hiểu trò chơi này là thông qua các đại lượng bất biến. Đại lượng đầu tiên khá hiển nhiên, nhưng đại lượng thứ hai đòi hỏi một số hiểu biết đặc biệt hoặc kinh nghiệm. Trong mỗi bước di chuyển, chúng ta lấy hai con chip tại vị trí \(x\) và gửi chúng đến các vị trí \(x-1\) và \(x+1\). Lưu ý rằng:

Điều này ngay lập tức dẫn đến hai quan sát sau:

Quan sát 1. Tổng các vị trí của tất cả các con chip không bao giờ thay đổi.

Quan sát 2. Tổng bình phương các vị trí của tất cả các con chip tăng thêm 2 sau mỗi bước di chuyển.

Vậy làm thế nào để chúng ta sử dụng những quan sát này? Chúng không bắt buộc, nhưng chúng sẽ có công dụng như bạn sẽ thấy. Quan sát đầu tiên sẽ giúp chúng ta nhanh chóng xây dựng một cấu hình với các thuộc tính đã biết từ cấu hình ban đầu. Và với quan sát thứ hai, việc tính toán số bước di chuyển trở thành nhiệm vụ xây dựng cấu hình cuối cùng. Ví dụ, sử dụng Quan sát 2, chúng ta có thể dễ dàng ước tính rằng số bước di chuyển có thể ở bậc \(n^3\), từ đó xác định rằng mô phỏng trực tiếp thực sự là vô vọng.

Thêm từng con chip một

Một cách tiếp cận tốt là thêm từng con chip một, ở mỗi bước thực hiện đủ các bước di chuyển để ổn định hoàn toàn cấu hình. Câu hỏi là: làm thế nào để thực hiện phần cuối cùng này một cách hiệu quả? Hãy xem xét việc thêm một con chip vào một cấu hình ổn định.

Nếu con chip mới đến một vị trí chưa có con chip nào trước đó, chúng ta đã xong. Nếu không, nó rơi vào một đoạn (segment), và hình ảnh trông giống như thế này:

             *
?????????.***************.????????

Hai dấu "." đại diện cho các vị trí trống. Nếu bạn thử một vài ví dụ, bạn sẽ thấy rằng kết quả cuối cùng sẽ luôn là hai đoạn, một đoạn bắt đầu từ vị trí của dấu "." bên trái trong hình, và đoạn kia kết thúc tại vị trí của dấu "." bên phải. Chúng ta cũng có thể xem kết quả là một đoạn đơn lẻ có một lỗ hổng. Hơn nữa, bạn cũng có thể nhận ra rằng nếu có \(A\) điểm ở bên trái con chip mới của chúng ta trong cấu hình ban đầu, và \(B\) điểm ở bên phải, thì hai đoạn mới sẽ có độ dài lần lượt là \(B+1\) và \(A+1\), và tổng số bước di chuyển cần thiết sẽ là \((A+1) \times (B+1)\).

Chúng ta cũng có thể tính toán vị trí của lỗ hổng bằng Quan sát 1. Tổng các vị trí trong cấu hình ban đầu là \((1+2+...+15)+4\), và chúng ta biết trong cấu hình mới tổng là \((0+1+...+16)-H\), trong đó \(H\) là vị trí của lỗ hổng. Do đó, \(H\) phải là 12. Hình ảnh cuối cùng là:

?????????************.****????????

Sau đó, chúng ta có thể sử dụng Quan sát 2 để dễ dàng xác định cần bao nhiêu bước di chuyển để đạt được kết quả này.

Vì vậy, đây là một giải pháp khả thi cho bài toán. Thêm các con chip từng cái một. Ở mỗi giai đoạn, chúng ta có tối đa \(n\) đoạn rời nhau. Nếu con chip mới rơi vào một vị trí chưa bị chiếm đóng, nó sẽ tự tạo thành một đoạn; nếu không, nó sẽ biến đổi một đoạn thành hai đoạn như mô tả ở trên. Trong cả hai trường hợp, các đoạn mới có thể chạm vào các đoạn bên trái và/hoặc bên phải của chúng, và chúng ta sẽ hợp nhất chúng nếu điều đó xảy ra.

Tất cả những gì còn lại là tìm cách lưu trữ các đoạn này trong chương trình của bạn. Nếu bạn khéo léo, bạn có thể nhận ra rằng nếu chúng ta thêm các con chip từ trái sang phải, thì mỗi con chip mới sẽ luôn nằm trên hoặc cạnh một trong hai đoạn cuối cùng. Sau đó, bạn có thể sử dụng một ngăn xếp (stack) để lưu trữ tất cả các đoạn -- tất cả các hoạt động sẽ nằm trên hai phần tử trên cùng của ngăn xếp. Cách tiếp cận này cho giải pháp \(O(n)\). Nếu bạn bỏ lỡ hiểu biết cuối cùng này, bạn cũng có thể sử dụng cây tìm kiếm nhị phân (ví dụ: std::set trong C++) để có giải pháp \(O(n \log n)\).

Thêm từng đống chip

Trong bài toán của chúng ta, chúng ta có \(C\) đống chip, và thông thường \(C\) nhỏ hơn nhiều so với \(n\). Bây giờ chúng ta phác thảo một giải pháp cực nhanh chạy trong thời gian \(O(C)\). Mức độ hiểu biết này không nhất thiết phải có để giải bài toán, nhưng nó vẫn khá thú vị. Như bạn sẽ thấy, điều cần thiết là phải hiểu các chi tiết của giải pháp \(O(n)\) ở trên.

Thay vì thêm từng con chip một, chúng ta sẽ cố gắng xử lý tất cả các con chip từ một vị trí cùng một lúc.

Đầu tiên hãy giải quyết trường hợp chỉ có một đống \(n\) chip tại vị trí \(x\). Theo tính đối xứng và các cuộc thảo luận trong phần trước, dễ dàng thấy rằng cấu hình ổn định là một đoạn tập trung tại \(x\) nếu \(n\) lẻ; và một đoạn tập trung tại \(x\) với một lỗ hổng ở giữa nếu \(n\) chẵn.

Hãy định nghĩa một H-segment là một đoạn có một lỗ hổng. Nó là một bộ ba \((x, y, z)\), trong đó \(x < y \le z\), đại diện cho một đoạn chip từ vị trí \(x\) đến vị trí \(z\), bao gồm cả hai đầu, nhưng vị trí \(y\) trống. Lưu ý rằng, khi \(y = z\), lỗ hổng nằm ở ngay cuối cùng, và nó thực sự là một đoạn bình thường.

Giải pháp của chúng ta thêm các đống chip từng cái một. Và chúng ta giữ một ngăn xếp các H-segment hiện có từ trái sang phải. Khi một đống mới đến, nó được chuyển đổi thành một H-segment mới. Nếu H-segment không chồng lấn với bất kỳ H-segment hiện có nào, chúng ta đã xong. Nếu không, nó chồng lấn với H-segment trên cùng trong ngăn xếp; nghĩa là, nó tạo ra một số vị trí có hai con chip. Nhưng bằng cách sử dụng các quan sát từ phần trước, chúng ta biết rằng nếu chúng ta giải quyết các xung đột từng cái một, chúng ta sẽ luôn có tối đa một lỗ hổng. Điều đó có nghĩa là kết quả sẽ là một H-segment khác. Nếu cái mới chồng lấn với H-segment trên cùng hiện tại trong ngăn xếp, chúng ta tiếp tục với cùng một quy trình giải quyết. Chúng ta làm điều này cho đến khi ngăn xếp trống, hoặc H-segment rời rạc với phần tử trên cùng của ngăn xếp. Sau đó, chúng ta đẩy cái mới vào và chuyển sang đống tiếp theo.

Chỉ còn lại việc giải thích cách tính toán một H-segment mới một cách nhanh chóng. Và câu trả lời là: chỉ cần sử dụng lại Quan sát 1! Khi giải quyết hai H-segment, chúng ta biết \(S\) -- tổng các vị trí trong chúng; chúng ta cũng biết tổng số chip \(K\), vì vậy (nhớ cái lỗ), \(z = x+K\). Chúng ta cần quyết định vị trí bắt đầu \(x\). Tùy thuộc vào \(y\), tổng \(S\) thỏa mãn:

Có một giá trị \(x\) duy nhất thỏa mãn điều này, và nó có thể được giải trong thời gian hằng số. Sau đó, chúng ta có thể tìm \(y\) chính xác như chúng ta đã làm trong giải pháp \(O(n)\).

Thông tin thêm

Nếu bạn thích bài toán này, bạn cũng có thể thích đọc bài báo kinh điển sau đây về trò chơi bắn chip:

• Anders Björner, László Lovász, and Peter Shor Chip-firing games on graphs. European Journal of Combinatorics, Volume 12 , Issue 4 (July 1991).

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