Phân tích: Candy Splitting

Bước chính cần thiết để giải bài này là hiểu thuật toán cộng kỳ lạ của Patrick. Chẳng hạn, ta có thể mô tả điều gì xảy ra khi Patrick cộng nhiều số thay vì chỉ hai số hay không? Hóa ra là có: ta viết tất cả các số ở dạng nhị phân, căn thẳng theo bit thấp nhất, rồi viết 1 tại những vị trí mà trong các số hạng (các số được cộng) có một số lẻ bit 1.

Xét ví dụ sau: giả sử Patrick cần cộng 5, 7 và 9. Trước hết, cậu cộng 5 và 7 bằng cách viết chúng ở dạng nhị phân rồi cộng từng chữ số mà không nhớ, đúng như mô tả trong đề:

  101

+ 111
-----
  010

Kết quả là 010 trong hệ nhị phân, tức 2. Bây giờ cậu cộng 2 và 9:

  0010

+ 1001
------
  1011

Kết quả là 1011 trong hệ nhị phân, tức 11. Điều đáng xem nhất là chuyện xảy ra ở bit thấp nhất: sau khi cộng hai số đầu, bit thấp nhất là 0 vì cả hai số hạng đều có bit 1 tại đó. Tuy nhiên, bit thấp nhất của kết quả cuối cùng là 1 vì số thứ ba cũng có bit 1 tại đó. Không khó để thấy điều này tổng quát hóa đúng như trên: với bất kỳ bit nào, bit ấy trong tổng cuối cùng bằng 1 khi và chỉ khi nó được đặt thành 1 trong một số lẻ các số hạng.

Sau khi xác lập điều đó, ta có thể hiểu nhiệm vụ của Sean rõ hơn. Cậu cần chia tập số đã cho thành hai phần sao cho tại mọi vị trí bit, một trong hai trường hợp sau xảy ra:

• Ở cả hai phần, có một số lẻ số hạng mang bit 1 tại vị trí ấy, nên bit tương ứng trong tổng của cả hai phần đều là 1; hoặc
• Ở cả hai phần, có một số chẵn số hạng mang bit 1 tại vị trí ấy, nên bit tương ứng trong tổng của cả hai phần đều là 0.

Nhưng yêu cầu hai số hoặc cùng lẻ, hoặc cùng chẵn tương đương với yêu cầu tổng của chúng phải chẵn!

Điều đó cho phép phát biểu lại nhiệm vụ của Sean một cách đơn giản: cậu cần chia tập số đã cho thành hai phần sao cho tại mọi vị trí bit, trên cả hai phần gộp lại có một số chẵn số hạng mang bit 1. Đột nhiên ta thấy điều kiện này hoàn toàn không phụ thuộc vào cách chia các số thành hai phần! Hoặc tại mọi vị trí bit, trong toàn bộ các số hạng có một số chẵn bit 1, khi đó bất kỳ cách chia nào thành hai đống không rỗng cũng làm Patrick hài lòng; hoặc tồn tại một bit bằng 1 trong một số lẻ các số hạng, khi đó không có cách nào làm Patrick hài lòng.

Ví dụ, giả sử Sean có các viên kẹo trị giá 5, 7, 9 và 11. Nếu cậu lấy 5 và 7 cho mình, còn đưa 9 và 11 cho Patrick, Patrick sẽ cộng 5 và 7 thành \(5+7=101_2+111_2=010_2=2\), và cộng 9 với 11 thành \(9+11=1001_2+1011_2=0010_2=2\), nên Patrick hài lòng. Nhưng ngay cả khi Sean lấy 7, 9 và 11, chỉ để lại 5 cho Patrick, Patrick sẽ cộng 7, 9 và 11 thành \(7+9+11=0111_2+1001_2+1011_2=0101_2=5\), nên cậu bé vẫn hài lòng! Không khó để kiểm tra rằng trong mọi trường hợp khác Patrick cũng hài lòng.

Toàn bộ lập luận trên có thể đơn giản hơn nếu nhận ra phép cộng kỳ lạ của Patrick chính là phép XOR theo bit. Điều kiện để Patrick hài lòng có thể được phát biểu lại là XOR theo bit của tất cả giá trị kẹo bằng 0. Trong nhiều ngôn ngữ lập trình, XOR theo bit đã có sẵn dưới toán tử ^, nên việc kiểm tra điều này rất dễ!

Vậy lời giải tổng thể hoạt động thế nào? Trước tiên, ta cần kiểm tra Patrick có hài lòng hay không; như đã chỉ ra ở trên, điều này không phụ thuộc vào cách Sean chia các đống. Nếu không, ta chỉ việc in NO cho test case này. Nếu có, Sean cần tối đa hóa đống của mình, và cách đạt được điều đó là lấy tất cả các viên kẹo ngoại trừ viên có giá trị nhỏ nhất.

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