Bài này thiên về phân tích một thuật toán có sẵn hơn là viết một thuật toán mới. Khi hiểu tác phẩm ở độ phức tạp cao phụ thuộc vào chuỗi gốc như thế nào, phần cài đặt sẽ rất ngắn.

Điều đầu tiên cần nhận ra là nếu chuỗi gốc toàn L, tác phẩm luôn toàn L với mọi \(C\). Nếu một tập vị trí đều cho kết quả L đối với một chuỗi gốc khác chuỗi toàn L, đáp án không hợp lệ vì ta không phân biệt được hai trường hợp đó. Do vậy phải chọn các vị trí sao cho mọi chuỗi gốc không toàn L đều làm ta thấy ít nhất một G.

Test Set nhỏ

Vì được kiểm tra số ô bằng độ dài chuỗi gốc, ta có thể nghĩ đến việc khôi phục cả chuỗi. Điều đó làm được, nhưng có cách dễ hơn: luôn in các số từ 1 đến \(K\). Gọi chuỗi gốc là \(O\), và \(A_i\) là tác phẩm độ phức tạp \(i\) ứng với \(O\). Ta chứng minh bằng hai trường hợp.

1. Nếu \(O\) bắt đầu bằng L, mọi \(A_i\) đều bắt đầu bằng \(O\). Điều này đúng hiển nhiên với \(A_1=O\). Nếu \(A_i\) bắt đầu bằng \(O\), nó bắt đầu bằng L; phép biến đổi thay viên L đầu tiên bằng một bản \(O\), nên \(A_{i+1}\) cũng bắt đầu bằng \(O\). Theo quy nạp, khi kiểm tra các vị trí 1 đến \(K\), ta đang kiểm tra một bản sao của \(O\) và sẽ thấy G nếu \(O\) có G.

2. Nếu \(O\) bắt đầu bằng G, mọi \(A_i\) đều bắt đầu bằng G. Điều này đúng với \(A_1\); mỗi phép biến đổi thay G đầu tiên bằng \(K\) viên G, nên cũng đúng với \(A_{i+1}\). Vì kiểm tra vị trí 1, ta chắc chắn thấy G.

Vậy mọi chuỗi không toàn L đều cho ít nhất một G, còn chuỗi toàn L chỉ cho L; câu hỏi được trả lời và Small không có trường hợp bất khả thi.

Chứng minh trên gợi ý một cách khác có thể thu đủ thông tin để biết toàn bộ \(O\). Ta trình bày vì nó thú vị và là bước đệm cho Large.

Vị trí 1 của mọi \(A_i\) luôn bằng vị trí 1 của \(O\). Với vị trí 2, ở \(A_1=O\) nó là ô 2. Khi tạo \(A_2\), ô 2 của \(A_1\) quyết định các ô \(K+1\) đến \(K+K\); ô thứ hai trong số đó, tức \(K+2\), bằng ô 2 của \(A_1\). Tiếp đó ô \(K+2\) sinh các vị trí \(K(K+2-1)+1\) đến \(K(K+2)\) trong \(A_3\), và ô thứ hai, \(K(K+2-1)+2\), vẫn là bản sao vị trí 2 của \(O\). Có thể tiếp tục hoặc viết chương trình để tìm vị trí tương ứng trong \(A_C\). Tương tự, mỗi vị trí của \(O\) có đúng một vị trí “điểm cố định” trong \(A_C\) luôn cùng giá trị. Kiểm tra tất cả các điểm đó cho kết quả khác nhau với mọi \(O\), nên cũng hợp lệ.

Test Set lớn

Lập luận về điểm cố định giúp giải Large. Mỗi vị trí trong \(A_i\) sinh \(K\) vị trí trong \(A_{i+1}\), gián tiếp sinh \(K^2\) vị trí trong \(A_{i+2}\), \(K^3\) trong \(A_{i+3}\), v.v. Gọi một ô trong \(A_{i+d}\) là hậu duệ của vị trí \(p\) trong \(A_i\) nếu nó được sinh qua chuỗi các thế hệ trung gian từ \(p\).

Một G ở bất kỳ \(A_i\) nào khiến mọi hậu duệ của nó là G. Nếu vị trí \(p\) của \(A_i\) là L, hậu duệ \((p-1)K+d\) (\(1\le d\le K\)) trong \(A_{i+1}\) bằng vị trí \(d\) của \(O\). Vì thế ô đó là L khi và chỉ khi cả ô \(p\) và ô \(d\) của \(O\) là L. Tiếp tục suy luận, mọi vị trí của mọi \(A_i\) là L khi và chỉ khi một tập vị trí xác định trong \(O\) đều là L.

Ta tìm tập đó bằng thứ tự hậu duệ ở từng mức. Chẳng hạn với \(K=3\), vị trí 8 của \(A_3\) là hậu duệ số 2 của vị trí 3 trong \(A_2\), còn vị trí 3 ấy là hậu duệ số 3 của vị trí 1 trong \(A_1\). Do đó vị trí 8 của \(A_3\) là L khi và chỉ khi các vị trí 2, 3 và 1 của \(O\) đều là L. Chỉ nhìn ô này đã cho biết trong ba vị trí ấy có G hay không.

Tổng quát, bắt đầu ở vị trí \(p_1\) của \(A_1=O\), chọn hậu duệ thứ \(p_2\) trong \(A_2\), rồi hậu duệ thứ \(p_3\), cho đến hậu duệ thứ \(p_C\) trong \(A_C\), ta nhận được một ô cho biết trong các vị trí \(p_1,p_2,\ldots,p_C\) của \(O\) có G hay không. Ngược lại, mỗi vị trí của \(A_C\) tương ứng với một dãy \(C\) vị trí như vậy. Mỗi ô kiểm tra bao phủ tối đa \(C\) vị trí của \(O\), và có thể bao phủ đúng \(C\) nếu chọn phù hợp.

Ta phải bao phủ cả \(K\) vị trí, nên bất khả thi chính xác khi \(SC<K\). Trong các trường hợp còn lại, gán danh sách \([1,2,\ldots,C]\) cho ô kiểm tra thứ nhất, \([C+1,C+2,\ldots,2C]\) cho ô thứ hai, và tiếp tục đến \(K\). Nếu danh sách cuối ngắn hơn \(C\), điền thêm bản sao của bất kỳ số nào từ 1 đến \(K\). Đổi mỗi danh sách thành vị trí trong \(A_C\) bằng cách đi theo đường hậu duệ; các hậu duệ của \(p\) luôn là \((p-1)K+1\) đến \((p-1)K+K\). Mã Python chính thức biểu diễn ý tưởng này:

def Solve(k, c, s):
  if c*s > k:
    return []  # returns an empty list for impossible cases
  tiles = []
  # the list for the last tile choice is filled with copies of k
  # i is the first value of the list of the current tile choice
  for i in xrange(1, k + 1, c):
    p = 1
    # j is the step in the current list [i, i+1, ..., i+C-1]
    for j in xrange(c):
      # the min fills the last tile choice's list with copies of k
      p = (p - 1) * k + min(i + j, k)
    tiles.append(p)
  return tiles

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Qualification Round - Fractiles, kho Google Coding Competitions (Apache-2.0).