Test Set 1

Ràng buộc đủ nhỏ để mô phỏng trực tiếp các quy tắc. Phần lớn cài đặt tốn \(O(NK)\) và chạy ngay lập tức; ngay cả cách chậm \(O(N^2K)\) — thử mọi buồng cho người tiếp theo, rồi ở mỗi buồng trống lại quét sang cả hai phía để tìm người gần nhất — rất có thể vẫn kịp. Nhưng ở Test Set 2 và 3, thuật toán bậc hai theo số buồng không còn đủ nhanh.

Test Set 2: multiset độ dài đoạn trống

Nhận xét then chốt là tại mọi thời điểm, chỉ multiset độ dài các đoạn buồng trống liên tiếp có ý nghĩa. Người kế tiếp luôn chọn buồng giữa, hoặc một trong hai buồng giữa, của một đoạn trống dài nhất. Dạng output cũng gợi ý điều này: chọn buồng giữa bên phải thay vì bên trái, hay chọn một đoạn dài nhất khác thay vì đoạn ngoài cùng bên trái, đều không đổi đáp án. Vì vậy, với mục tiêu output, có thể thay quy tắc bằng:

1. Tìm bất kỳ đoạn buồng trống liên tiếp dài nhất nào.
2. Chọn buồng giữa hoặc một trong hai buồng giữa của đoạn đó.

Dù vẫn còn cách phá hòa, mọi cách cho cùng output và cùng multiset độ dài các đoạn còn lại; toàn bộ quá trình chỉ phụ thuộc vào multiset ấy. Mã giả:

  S = {N}  - This is a multiset!
  repeat K times:
    X = max(S)
    X0 = ceil((X - 1) / 2)
    X1 = floor((X - 1) / 2)
    if this is the last step:
      we are done; answer is X0 and X1
    else:
      remove one instance of X from S
      insert X0 and X1 into S

Nếu các thao tác trên \(S\) hiệu quả, mô phỏng chạy gần tuyến tính. Cây AVL, cây đỏ-đen và heap đều hỗ trợ chèn, lấy lớn nhất, xóa lớn nhất trong thời gian logarit; thư viện chuẩn thường có multiset/priority_queue của C++, TreeSet của Java hay heapq của Python. Mỗi trong \(K\) bước tốn \(O(\log K)\), tổng \(O(K\log K)\), đủ cho Test Set 2 nhưng chưa đủ cho Test Set 3.

Test Set 3: xử lý đồng thời các giá trị giống nhau

Ta đang lặp đi lặp lại các bước rất giống nhau. Người đầu tiên tách \(N\) thành \(\lceil(N-1)/2\rceil\) và \(\lfloor(N-1)/2\rfloor\), nên mọi số nằm giữa \(\lceil(N-1)/2\rceil\) và \(N\) sẽ không bao giờ xuất hiện trong \(S\); điều này gợi ý chỉ có logarit mức.

Chia xử lý thành các giai đoạn: giai đoạn đầu chỉ xử lý \(N\), giai đoạn \(i+1\) xử lý mọi giá trị do giai đoạn \(i\) sinh ra. Có thể chứng minh quy nạp rằng mỗi giai đoạn chỉ xử lý nhiều nhất hai số liên tiếp. Nếu giai đoạn \(i\) xử lý hai số liên tiếp, chúng có dạng \(2x,2x+1\) hoặc \(2x,2x-1\) — một chẵn, một lẻ — nên giai đoạn sau chỉ có thể sinh \(x\) và/hoặc \(x-1\). Giá trị lớn nhất giảm ít nhất một nửa sau mỗi giai đoạn, vậy có \(O(\log N)\) giai đoạn và chỉ \(O(\log N)\) giá trị khác nhau từng đi vào \(S\).

Một giá trị có thể xuất hiện rất nhiều lần. Tối ưu quyết định là xử lý đồng thời tất cả bản sao của nó, vì chúng cho cùng \(X_0,X_1\). Dùng set thường cùng bảng đếm số lần xuất hiện:

  S = {N}  - This is a set, not a multiset!
  C(N) = 1
  P = 0
  repeat:
    X = max(S)
    X0 = ceil((X - 1) / 2)
    X1 = floor((X - 1) / 2)
    P = P + C(X)
    if P ≥ K:
      we are done; the answer is X0 and X1.
    else:
      remove X from S
      insert X0 and X1 into S
      add C(X) to the counts of X0 and X1 in C

Các cấu trúc thao tác logarit cho tổng \(O(\log^2N)\). Có thể kết hợp cấu trúc của Test Set 2 với dictionary, như map C++, TreeMap Java, hoặc dùng thêm hash table — cách dễ nhất trong Python.

Thậm chí, tại mọi thời điểm \(S\) có nhiều nhất 4 phần tử vì chỉ giá trị từ hai giai đoạn liên tiếp có thể cùng tồn tại. Do kích thước cấu trúc bị chặn bởi hằng số, bất kỳ cài đặt set và dictionary nào cũng cho thời gian hằng số mỗi thao tác; tổng độ phức tạp là \(O(\log N)\).

Đây cũng là bài thích hợp để dùng thực nghiệm khi trực giác chưa đủ. Sau khi giải Test Set 1, in dãy giá trị với một \(N\) cố định có thể giúp nhận ra rằng \(S\) chỉ chứa ít giá trị, rồi từ đó xây dựng chứng minh tổng quát. Ở các vòng sau, kỹ thuật dùng thực nghiệm để gợi ý hoặc kiểm chứng ý tưởng trước khi cam kết còn quan trọng hơn; các thí sinh chung kết cũng thường xuyên làm như vậy.

Dựa trên phân tích chính thức của Google Code Jam 2018, Vòng luyện tập, bài Bathroom Stalls.