Mô phỏng các đoạn

Khi chọn trong đoạn trống dài \(X\), nó tách thành

Luôn lấy đoạn dài nhất; điều này đúng chính xác với hai tiêu chí đề bài.

  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

Dùng multiset/priority queue mô phỏng \(K\) người, \(O(K\log K)\), đủ cho tập nhỏ.

Gộp các đoạn cùng kích thước

Chỉ có \(O(\log N)\) kích thước khác nhau. Lưu map count[x] và max-heap các kích thước. Khi lấy kích thước lớn nhất \(X\) có \(c\) bản, cả \(c\) người tiếp theo tạo \(c\) đoạn \(X_0\) và \(c\) đoạn \(X_1\). Cộng dồn số người đã xử lý; nhóm đầu tiên làm tổng đạt hoặc vượt \(K\) cho đáp án \((X_0,X_1)\).

  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

Mỗi mức giảm gần một nửa, nên \(O(\log N)\) trạng thái và \(O(\log^2N)\) với map/heap (hoặc \(O(\log N)\) bằng công thức tầng cây).

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

Test Set 1: mô phỏng trực tiếp

Với giới hạn đầu tiên, có thể mô phỏng đúng các quy tắc trong đề. Một cài đặt thông thường tìm các đoạn trống và chọn vị trí tốt nhất trong \(O(NK)\). Ngay cả cách chậm \(O(N^2K)\) — thử mọi buồng trống rồi quét hai phía để tìm người gần nhất — nhiều khả năng vẫn đủ nhanh cho \(N\le1000\). Hai Test Set sau không cho phép thời gian tuyến tính hay bậc hai theo số buồng cho mỗi người.

Test Set 2: chỉ cần độ dài các đoạn trống

Người kế tiếp luôn chọn ô giữa, hoặc một trong hai ô giữa, của một đoạn trống dài nhất. Việc chọn ô 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, không đổi hai giá trị cần xuất. Quan trọng hơn, đa tập độ dài các đoạn còn lại cũng không đổi, nên toàn bộ quá trình đối với output chỉ phụ thuộc đa tập này.

Với đoạn dài \(X\), hai đoạn sinh ra có độ dài

Mô phỏng tối ưu hóa như sau:

S = {N}  // đây là một multiset
lặp K lần:
    X = max(S)
    X0 = ceil((X - 1) / 2)
    X1 = floor((X - 1) / 2)
    nếu đây là lần cuối: trả lời X0, X1
    nếu không:
        xóa một bản sao X khỏi S
        chèn X0 và X1 vào S

AVL tree, red-black tree, heap hay các cấu trúc thư viện như multiset, priority_queue, TreeSet, heapq hỗ trợ chèn/lấy/xóa cực đại trong thời gian logarit. Có \(K\) vòng nên độ phức tạp là \(O(K\log K)\), đủ cho \(K\le10^6\) nhưng chưa đủ cho \(10^{18}\).

Test Set 3: xử lý đồng thời các bản sao

Lần đầu, \(N\) sinh ra \(\lceil(N-1)/2\rceil\) và \(\lfloor(N-1)/2\rfloor\); không giá trị nào nằm giữa chúng và \(N\) có thể xuất hiện về sau. Chia mô phỏng thành các tầng: tầng đầu xử lý \(N\), tầng sau xử lý mọi giá trị do tầng trước sinh.

Mỗi tầng có nhiều nhất hai giá trị liên tiếp. Thật vậy, nếu một tầng có hai số liên tiếp thì chúng có dạng \(2x\) với \(2x+1\) hoặc \(2x-1\); sau khi tách, tầng sau chỉ có thể chứa \(x\) và \(x-1\). Giá trị lớn nhất giảm ít nhất khoảng một nửa mỗi tầng, nên chỉ có \(O(\log N)\) tầng và \(O(\log N)\) giá trị khác nhau, dù số bản sao của một giá trị có thể rất lớn.

Lưu tập các kích thước cùng bộ đếm \(C(X)\) và xử lý cả nhóm:

S = {N}  // set, không phải multiset
C(N) = 1
P = 0
lặp:
    X = max(S)
    X0 = ceil((X - 1) / 2)
    X1 = floor((X - 1) / 2)
    P = P + C(X)
    nếu P >= K: trả lời X0, X1
    nếu không:
        xóa X khỏi S
        chèn X0 và X1 vào S
        cộng C(X) vào bộ đếm của X0 và X1

Với set và map cân bằng, thời gian là \(O(\log^2 N)\). Thực ra tại mọi lúc \(S\) chứa nhiều nhất bốn giá trị — chỉ từ hai tầng liên tiếp — nên mọi thao tác trên cấu trúc kích thước hằng có thể xem là \(O(1)\), cho tổng \(O(\log N)\).

Đây cũng là một bài thích hợp để dùng thực nghiệm: sau khi giải Test Set 1, in dãy kích thước cho một \(N\) cố định sẽ gợi ra hiện tượng chỉ có rất ít giá trị trong \(S\); từ đó mới xây dựng chứng minh quy nạp. Phân tích chính thức nhấn mạnh rằng thử nghiệm để gợi ý và kiểm chứng trực giác là kỹ năng hữu ích cả ở các vòng khó hơn.