Test Set 1

Test Set 1 và 2 chỉ khác nhau ở kích thước vùng lưới khả dụng. Trong Test Set đầu tiên, mỗi tọa độ nơi một người đang đứng chỉ có thể nằm từ \(0\) đến \(10\), kể cả hai đầu. Hơn nữa, xe hàng cũng chỉ có thể nằm tại một ô trong vùng này. Theo quy tắc đề bài, cả hoành độ lẫn tung độ của xe đều phải không âm và không tọa độ nào có thể lớn hơn \(10\). Chẳng hạn, giả sử hoành độ xe lớn hơn \(10\); khi đó phải có ít nhất một người đứng tại hoành độ \(10\) và quay mặt về phía đông. Nếu không, theo quy tắc phá hòa, đặt xe tại hoành độ \(10\) sẽ còn tốt hơn. Nhưng đề bài không cho phép người ở tọa độ ngang/dọc \(10\) quay mặt về phía đông/bắc tương ứng.

Do đó, để giải Test Set 1, ta có thể tạo một mảng biểu diễn tất cả các ô trong vùng được phép và khởi tạo mỗi ô bằng \(0\). Với mỗi người, ta tăng tất cả các ô mà người đó đang đi về phía chúng. Cuối cùng, tìm ô có giá trị lớn nhất và áp dụng quy tắc phá hòa khi cần. Lời giải có độ phức tạp thời gian \(O(P \times Q^2)\).

Test Set 2: lời giải bậc hai

Trong những bài toán có nhiều chiều, thường rất đáng để kiểm tra xem các chiều có độc lập hay không. Ở đây, chúng thực sự độc lập! Chẳng hạn, một người đi về phía tây cho ta một "phiếu" rằng xe bánh crepe nằm về phía tây của họ, nhưng hoàn toàn không cho biết vị trí bắc–nam của xe. Vì vậy, ta có thể giải hai chiều thành hai bài toán một chiều riêng: bài toán ngang chỉ gồm người đi tây hoặc đông (cùng hoành độ của họ), còn bài toán dọc chỉ gồm người đi nam hoặc bắc (cùng tung độ của họ). Trước mắt hãy xét chiều ngang; các lập luận cũng áp dụng cho chiều dọc.

Ngay cả khi mọi người phân bố rất xa nhau trên trục ngang, xe bánh crepe cũng chỉ có thể nằm tại một số hữu hạn vị trí ngang cần xét. Thực ra, nó phải ở vị trí \(0\), hoặc tại một ô nằm ngay một ô về phía đông của một người nào đó. Để thấy điều này, giả sử xe nằm tại một ô khác \(C\) với \(1 \le C \le Q\). Gọi \(W\) là ô cách \(C\) một đơn vị về phía tây. Theo giả thiết, \(W\) không có người. Khi chuyển xe từ \(C\) sang \(W\), ta không mất phiếu nào (bất kỳ ai bỏ phiếu cho \(C\) cũng bỏ phiếu cho \(W\)), và thậm chí có thể nhận thêm phiếu (nếu có người ở \(C\) đang đi về phía tây). (Lưu ý rằng một người không bỏ phiếu cho chính ô họ đang đứng.) Ngay cả khi không nhận thêm phiếu, quy tắc phá hòa cũng tốt hơn. Vì vậy, ta luôn nên chuyển xe về phía tây cho đến khi nó ở \(0\) hoặc ngay phía đông của một người. Thao tác này có thể chỉ tìm ra một lời giải tối ưu cục bộ, nhưng nếu kiểm tra tất cả các ô dạng đó, chắc chắn ta sẽ tìm được lời giải tối ưu toàn cục.

Các nhận xét trên giảm số ô cần kiểm tra xuống \(O(P)\) thay vì \(O(Q)\). Để kiểm tra một ô, ta duyệt tuyến tính qua mọi người và đếm xem mỗi người có bỏ phiếu cho ô đó không; một lần kiểm tra tốn \(O(P)\). Sau đó chọn ô nhận nhiều phiếu nhất; nếu hòa, chọn ô xa về phía tây nhất. Độ phức tạp tổng thể là \(O(P^2)\) cho bài toán một chiều, và giải hai lần vẫn là \(O(P^2)\).

Test Set 2: lời giải (gần) tuyến tính

Mặc dù lời giải trên đủ nhanh cho Test Set 2, ta còn có thể làm tốt hơn bằng cách tránh duyệt tuyến tính toàn bộ dữ liệu cho từng người.

Trước tiên, xử lý dữ liệu thành một tập các bộ (tọa độ, số người tại tọa độ đó quay về tây, số người tại tọa độ đó quay về đông), ký hiệu \((C_i, W_i, E_i)\). (Trong bài toán con theo phương ngang, ta bỏ qua người quay về bắc hoặc nam.) Dùng từ điển dựa trên bảng băm, bước này tốn thời gian tuyến tính theo \(P\). Đồng thời, ta cũng xác định tổng số người \(W\) và \(E\) lần lượt quay về tây và đông.

Tiếp theo, sắp xếp các bộ theo thứ tự tăng dần của giá trị đầu tiên. Có lẽ thuận tiện nhất là dùng một thuật toán sắp xếp thông dụng (hoặc thuật toán có sẵn trong ngôn ngữ), khiến bước này không còn tuyến tính. (Cuộc tranh luận sôi nổi về những thuật toán sắp xếp nào thực sự tuyến tính xin để dành cho một ngày khác.)

Sau khi sắp xếp, trước hết xét ô \(0\) làm ứng viên và xác định số phiếu cho ô này. Số đó bằng \(W\) trừ số người trong ô \(0\), nếu có. Ta ghi lại số phiếu và đặt \(0\) làm ứng viên tốt nhất cho đến lúc đó. Sau đó xét bộ đầu tiên, đại diện cho người tại một ô \(C\) nào đó (có thể là ô \(0\)). Số phiếu cho ô \(C + 1\) (cách \(C\) một đơn vị về phía đông) bằng số phiếu hiện tại, cộng số người trong ô \(C\) quay về đông, rồi trừ số người trong ô \(C\) quay về tây. Nếu \(C + 1\) là ứng viên tốt hơn, ta lưu ô này cùng số phiếu của nó.

Ta làm như vậy với mọi bộ trong danh sách để thu được đáp án cuối cùng. Nếu có một hoặc nhiều người ở biên phía đông, không cần kiểm tra ô cách họ một đơn vị về phía đông, bởi vì (như giải thích ở đầu phần phân tích) xe không bao giờ có tọa độ lớn hơn \(Q\). Do kiểm tra mỗi bộ chỉ tốn thời gian hằng số, toàn bộ lượt duyệt tốn \(O(P)\).

Áp dụng tương tự cho chiều dọc, với nam là hướng giảm và bắc là hướng tăng tọa độ, rồi ghép hai tọa độ tối ưu. Tạo bảng băm tốn \(O(P)\) kỳ vọng, sắp xếp tốn \(O(P \log P)\), lượt quét tốn \(O(P)\) và bộ nhớ tốn \(O(P)\).

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