Phân tích: Charging Chaos

Bài toán yêu cầu tìm số lượng công tắc tối thiểu cần bật sao cho tất cả các thiết bị đều có thể được sạc cùng lúc. Tất cả các thiết bị có thể được sạc cùng lúc nếu mỗi ổ cắm có thể được ghép cặp với đúng một thiết bị và ngược lại. Một ổ cắm có thể ghép cặp với một thiết bị nếu cả hai có cùng dòng điện sau khi bật một số công tắc.

Chúng ta nhận thấy rằng việc bật cùng một công tắc hai lần (hoặc một số chẵn lần) tương đương với việc không bật công tắc đó. Tương tự, bật một công tắc một số lẻ lần tương đương với việc bật nó đúng một lần. Do đó, chúng ta chỉ cần xem xét việc bật công tắc thứ \(i\) một lần hoặc không bật.

Hãy định nghĩa một chuỗi-bật gồm các ký tự 0 và 1 độ dài \(L\) là một cách để bật các công tắc. Nếu ký tự thứ \(i\) của chuỗi là 1, nghĩa là ta bật công tắc thứ \(i\) (ngược lại thì không). Một chuỗi-bật là tốt nếu dòng điện tại các ổ cắm sau khi bật cho phép sạc tất cả các thiết bị cùng lúc. Chúng ta có thể kiểm tra xem một chuỗi-bật có tốt hay không bằng cách đảo các bit trong dòng điện của ổ cắm theo chuỗi-bật đó, sau đó kiểm tra xem tập hợp các dòng điện mới có khớp hoàn toàn với tập hợp dòng điện yêu cầu của các thiết bị hay không. Có thể sử dụng băm (hashing) hoặc sắp xếp để thực hiện việc kiểm tra này với độ phức tạp \(O(LN \log N)\) hoặc \(O(LN)\). Lưu ý rằng ta có thể mã hóa chuỗi-bật thành một số nguyên 64-bit để giảm độ phức tạp kiểm tra xuống \(O(N \log N)\) hoặc \(O(N)\).

Thuật toán vét cạn:

Một giải pháp vét cạn ngây thơ là thử tất cả \(2^L\) chuỗi-bật có thể, kiểm tra xem chuỗi nào tốt và giữ lại chuỗi có ít số 1 nhất. Độ phức tạp thời gian là \(O(2^L \cdot LN)\). Với Small dataset (\(L \le 10\)), thuật toán này là đủ. Tuy nhiên, nó quá chậm cho Large dataset (\(L \le 40\)).

Thuật toán cải tiến:

Để cải thiện thuật toán vét cạn, chúng ta cần hai quan sát quan trọng. Thứ nhất là chỉ có một số ít chuỗi-bật là "tốt". Nếu có thể tạo ra các chuỗi-bật tốt một cách hiệu quả, ta sẽ cải thiện đáng kể độ phức tạp. Quan sát thứ hai là: với một dòng điện của thiết bị (độ dài \(L\)) và một dòng điện của ổ cắm (độ dài \(L\)), luôn tồn tại duy nhất một chuỗi-bật để biến đổi dòng điện ổ cắm đó thành dòng điện thiết bị đó. Có \(N^2\) cặp thiết bị và ổ cắm như vậy. Do đó, chỉ có tối đa \(N^2\) chuỗi-bật ứng viên cần được tạo ra.

Lưu ý rằng các chuỗi-bật được tạo ra có thể tốt hoặc không. Tuy nhiên, bất kỳ chuỗi-bật tốt nào chắc chắn phải nằm trong số các chuỗi-bật tạo ra từ việc ghép một thiết bị cụ thể nào đó (ví dụ thiết bị đầu tiên) với tất cả các ổ cắm có thể. Với quan sát này, ta có thể giảm số lượng ứng viên xuống còn \(N\).

Cách cài đặt:

1. Chọn một thiết bị bất kỳ (ví dụ thiết bị thứ 0).
2. Với mỗi ổ cắm \(j\) từ \(0\) đến \(N-1\):
   a. Xác định chuỗi-bật \(S\) cần thiết để biến dòng điện của ổ cắm \(j\) thành dòng điện của thiết bị 0.
   b. Áp dụng chuỗi-bật \(S\) lên tất cả \(N\) ổ cắm ban đầu.
   c. Kiểm tra xem tập hợp các dòng điện mới của các ổ cắm có trùng khớp với tập hợp các dòng điện yêu cầu của \(N\) thiết bị hay không.
   d. Nếu khớp, đếm số lượng bit 1 trong \(S\) và cập nhật kết quả tối thiểu.
3. Nếu không tìm thấy chuỗi-bật nào thỏa mãn, kết luận NOT POSSIBLE.

Độ phức tạp:

Độ phức tạp của thuật toán này là \(O(N^2 \cdot L)\) hoặc \(O(N^2 \cdot (L + \log N))\) tùy vào cách kiểm tra tập hợp (dùng hash hoặc sắp xếp), hoàn toàn đủ nhanh cho Large dataset với \(N=150, L=40\).

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