Một hoán vị kích thước \(N\) là một dãy gồm \(N\) số, mỗi số nằm trong khoảng từ \(0\) đến \(N-1\), trong đó mỗi số xuất hiện đúng một lần. Chúng có thể xuất hiện theo bất kỳ thứ tự nào.

Có rất nhiều (\(N!\) hoán vị, chính xác là vậy, nhưng điều đó không quan trọng trong bài toán này) hoán vị kích thước \(N\). Đôi khi chúng ta chỉ muốn chọn ngẫu nhiên một hoán vị, và tất nhiên chúng ta muốn chọn ngẫu nhiên một cách đều: mỗi hoán vị kích thước \(N\) nên có cùng xác suất được chọn.

Dưới đây là mã giả cho một trong những thuật toán khả thi để đạt được mục tiêu đó (chúng ta sẽ gọi nó là thuật toán tốt bên dưới):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(k .. N-1)
  swap(a[k], a[p])

Trong đoạn mã trên, randint(a .. b) trả về một số nguyên ngẫu nhiên đều giữa \(a\) và \(b\), bao gồm cả hai đầu.

Nói cách khác, chúng ta bắt đầu với hoán vị đồng nhất: tất cả các số từ \(0\) đến \(N-1\) được viết theo thứ tự tăng dần. Sau đó, với mỗi \(k\) từ \(0\) đến \(N-1\), chúng ta chọn một số nguyên ngẫu nhiên đều độc lập \(p_k\) từ \(k\) đến \(N-1\), và tráo đổi phần tử tại vị trí \(k\) (tính từ 0) trong hoán vị của chúng ta với phần tử tại vị trí \(p_k\).

Ví dụ với \(N=4\). Chúng ta bắt đầu với hoán vị đồng nhất:
0 1 2 3

Bây giờ \(k=0\), và chúng ta chọn một \(p_0\) ngẫu nhiên từ \(0\) đến \(3\). Giả sử chúng ta chọn \(2\). Chúng ta tráo đổi phần tử thứ \(0\) và thứ \(2\), hoán vị trở thành:
2 1 0 3

Bây giờ \(k=1\), và chúng ta chọn một \(p_1\) ngẫu nhiên từ \(1\) đến \(3\). Giả sử chúng ta lại chọn \(2\). Chúng ta tráo đổi phần tử thứ \(1\) và thứ \(2\), hoán vị trở thành:
2 0 1 3

Bây giờ \(k=2\), và chúng ta chọn một \(p_2\) ngẫu nhiên từ \(2\) đến \(3\). Giả sử chúng ta chọn \(3\). Chúng ta tráo đổi phần tử thứ \(2\) và thứ \(3\), hoán vị trở thành:
2 0 3 1

Bây giờ \(k=3\), và chúng ta chọn một \(p_3\) ngẫu nhiên từ \(3\) đến \(3\). Lựa chọn duy nhất là \(3\). Chúng ta tráo đổi phần tử thứ \(3\) với chính nó, nghĩa là hoán vị không đổi:
2 0 3 1

Quá trình kết thúc, và đây là hoán vị ngẫu nhiên của chúng ta.

Có nhiều thuật toán khác cũng tạo ra hoán vị ngẫu nhiên đều. Tuy nhiên, cũng có nhiều thuật toán trông rất giống thuật toán này nhưng không đều — một số hoán vị có khả năng được tạo ra cao hơn những hoán vị khác.

Dưới đây là một thuật toán xấu thuộc loại này. Lấy thuật toán tốt ở trên, nhưng ở mỗi bước, thay vì chọn \(p_k\) ngẫu nhiên từ \(k\) đến \(N-1\), chúng ta chọn nó ngẫu nhiên từ \(0\) đến \(N-1\). Đây là một thay đổi rất nhỏ, nhưng giờ đây một số hoán vị có khả năng xuất hiện cao hơn những hoán vị khác!

Mã giả cho thuật toán này (chúng ta sẽ gọi là thuật toán xấu):

for k in 0 .. N-1:
  a[k] = k
for k in 0 .. N-1:
  p = randint(0 .. N-1)
  swap(a[k], a[p])

Trong mỗi trường hợp kiểm thử, bạn sẽ được cung cấp một hoán vị được tạo ra theo cách sau: đầu tiên, chúng tôi chọn thuật toán tốt hoặc xấu với xác suất \(50\%\) mỗi loại. Sau đó, chúng tôi tạo một hoán vị bằng thuật toán đã chọn. Bạn có thể đoán thuật toán nào đã được chọn chỉ bằng cách nhìn vào hoán vị không?

Giải bài toán này

Bài toán này hơi bất thường đối với Code Jam. Bạn sẽ được cung cấp \(T = 120\) hoán vị, mỗi hoán vị có \(N = 1000\) số, và bạn nên in ra câu trả lời cho mỗi hoán vị. Tuy nhiên, bạn không cần phải trả lời đúng tất cả! Lời giải của bạn sẽ được coi là đúng nếu bạn trả lời đúng ít nhất \(G = 109\) trường hợp. Tuy nhiên, bạn phải tuân thủ định dạng đầu ra cho mọi trường hợp. Điều duy nhất có thể sai là tráo đổi GOOD thành BAD hoặc ngược lại; nhưng bạn vẫn phải in GOOD hoặc BAD cho mỗi trường hợp.

Đảm bảo rằng các hoán vị được tạo ra theo phương pháp trên và độc lập với nhau.

Vì bài toán có tính ngẫu nhiên, ngay cả lời giải tốt nhất cũng có thể không đạt được \(109\) dự đoán đúng cho một đầu vào nhất định. Do đó, bài toán này không có bộ dữ liệu Large, và chỉ có bộ Small mà bạn có thể thử lại nếu thấy mình không may mắn. Lưu ý rằng vẫn có hình phạt 4 phút cho các lần nộp sai nếu sau đó bạn giải được.

Trong kinh nghiệm của chúng tôi, việc bị sai do ngẫu nhiên đã xảy ra; vì vậy nếu bạn tin tưởng vào thuật toán của mình mà vẫn thất bại, thử lại cùng một lời giải có thể là một chiến thuật hợp lý.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\) (luôn là \(120\)). Mỗi bộ test gồm hai dòng: dòng đầu chứa số nguyên \(N\) (luôn là \(1000\)), dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách - hoán vị được tạo ra.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng "Case #\(x\): \(y\)", trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là "GOOD" hoặc "BAD".

Ràng buộc

• \(T = 120\)
• \(G = 109\)
• \(N = 1000\)
• Mỗi số trong hoán vị từ \(0\) đến \(N-1\), và mỗi số xuất hiện đúng một lần.

Phân nhóm

Đề bài sử dụng một tập dữ liệu duy nhất với các giới hạn nêu trên.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
0 1 2
3
2 0 1

Case #1: BAD
Case #2: GOOD

Nguồn

Google Code Jam 2014, Vòng 1A, bài Proper Shuffle.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.