Test Set 1

Ta cần nhận ra những worker nào không trả lại bit đã gửi. Hãy xem việc mất dữ liệu làm thay đổi các chuỗi bit như thế nào.

Giả sử có mười worker và ta gửi năm chuỗi bit ngẫu nhiên sau; bit thứ \(i\) của mỗi chuỗi được gửi tới worker thứ \(i\):

0101010110
0101010101
0010100100
0110110101
0100100100

Giả sử worker \(3\) và \(6\) bị hỏng. Khi đó, ở mỗi hàng ta mất đúng bit tại hai cột tương ứng:

0101010110
0101010101
0010100100
0110110101
0100100100

Các phản hồi nhận được là:

01001110
01001101
00110100
01111101
01010100

Nhìn theo cột, ta thấy các worker hỏng đã làm mất trọn vẹn một số cột bit. Nếu mỗi cột ban đầu khác nhau, chỉ cần nhìn những cột nào biến mất là biết chính xác worker nào bị hỏng.

Trong Test Set 1, \(N\le1024\) và ta được gửi \(F=10\) chuỗi. Mỗi worker vì thế có thể nhận một cột dài 10 bit. Vì \(2^{10}=1024\), ta gán cho worker \(i\) biểu diễn nhị phân 10 bit của chính số \(i\). Chẳng hạn năm cột đầu, đại diện các số từ 0 đến 4, có thể được tạo bởi các hàng:

01010...
00110...
00001...
00000...
00000...
00000...
00000...
00000...
00000...
00000...

Sau khi nhận đủ phản hồi, ghép các bit ở cùng một vị trí trong mười phản hồi thành một cột. Những biểu diễn nhị phân nào không còn xuất hiện chính là ID của các worker hỏng.

Test Set 2

Ở Test Set 2, chỉ được gửi \(F=5\) chuỗi, nên mỗi cột chỉ có 5 bit và chỉ biểu diễn được \(2^5=32\) giá trị. Không thể làm cho cả 1024 cột đôi một khác nhau như trước.

Ta chưa sử dụng điều kiện \(B\le15\). Đặc biệt, ít hơn 32 cột bị mất. Hãy sắp 32 giá trị biểu diễn được thành một khối tăng dần

0, 1, ..., 31

rồi lặp khối này cho đủ \(N\) worker:

0, 1, ..., 31, 0, 1, ..., 31, 0, 1, ..., 31, ...

Năm bit của mỗi số trong dãy cho ta năm chuỗi truy vấn. Vì có ít hơn 32 worker hỏng, không một khối đầy đủ nào có thể biến mất hoàn toàn.

Trong mỗi khối, các số tăng dần. Sau khi xóa một số phần tử, ranh giới từ một khối sang khối kế tiếp vẫn được nhận biết bởi một lần giảm. Ví dụ, một đoạn quanh ranh giới có thể trở thành

..., 27, 5, ..., 31, ...

Trong ví dụ này, các số giữa 27 và 5 đã biến mất nhưng \(27>5\) vẫn đánh dấu ranh giới. Giả sử ngược lại rằng giá trị cuối còn lại của khối trước là \(X\) và giá trị đầu còn lại của khối sau là \(Y\) với \(X\le Y\). Giữa hai vị trí ấy ban đầu có ít nhất 31 số khác, nên để xảy ra trường hợp này phải xóa ít nhất 31 worker; điều đó trái với \(B\le15\).

Vì vậy, sau khi ghép năm phản hồi thành các số còn lại, ta quét từ trái sang phải. Mỗi khi số hiện tại nhỏ hơn số trước đó, ta chuyển sang khối kế tiếp. Biết chỉ số khối và giá trị trong khối cho phép khôi phục ID gốc của mọi worker còn hoạt động. Ví dụ, giá trị 16 trong khối thứ năm tương ứng với vị trí toàn cục \((5-1)\cdot32+16=144\) nếu đánh số từ 0. Các ID không được khôi phục chính là đáp án.

Thực ra, vì \(B<2^4=16\), bốn truy vấn cũng đủ nếu lặp các khối 0, 1, ..., 15. Khi đó có thể xóa toàn bộ 15 giá trị nằm giữa hai giá trị bằng nhau ở hai khối kề nhau. Do đó ranh giới khối phải được nhận ra khi giá trị hiện tại nhỏ hơn hoặc bằng giá trị trước, thay vì chỉ khi nhỏ hơn.

Việc dựng truy vấn, ghép phản hồi và quét kết quả đều tốn \(O(FN)\) thời gian. Ta dùng \(O(N)\) bộ nhớ để lưu các chuỗi hoặc ID đã khôi phục; có thể giảm phần phụ xuống \(O(1)\) nếu xử lý tuần tự.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2019, Qualification Round, bài Dat Bae; kho Google Coding Competitions (Apache-2.0).