Go, Gopher!

Go, Gopher! là một bài toán không khó, nhưng khá thú vị ở mặt problem setting. Nội dung của nó như sau:

• Cho một bảng 2D có kích thước 1000 x 1000 và hai số tự nhiên $ A $, $ m $ cho trước.

• Các ô trên bảng có hai trạng thái là bật và tắt. Ban đầu, tất cả các ô đều đang ở trạng thái tắt.

• Ở mỗi lần deploy gopher vào ô (i, j), một ô nằm trong block 3x3 có ô (i, j) là trung tâm sẽ được chọn với phân phối đều và được chuyển sang trạng thái bật (nếu đang tắt) hoặc giữ nguyên trạng thái nếu đang bật.

Bài toán đặt ra là làm sao để tạo được một hình chữ nhật hoàn chỉnh mà trong đó tất cả các ô đều có trạng thái bật, và có diện tích lớn hơn hoặc bằng $ A $ với ít hơn $ m $ lần deploy.

Lời giải

Chọn $ \lceil \frac{A}{9} \rceil $ blocks 3x3 liên tiếp nhau và lần lượt deploy gopher vào các ô trung tâm của những blocks đó. Như vậy, ta sẽ luôn tạo được một hình chữ nhật hoàn chỉnh với diện tích lớn hơn hoặc bằng $ A $. Ví dụ, với $ A = 200 $ như test case lớn của đề bài, các ô trung tâm cần để chọn fill là: (2, 2), (5, 2), (8, 2), …, (68, 2).

Câu hỏi đặt ra là: Thời gian kỳ vọng để có thể bật được hết một block trống là bao nhiêu lần deploy?

Bài toán con: Trong bọc kẹo có $ n $ loại kẹo khác nhau, mỗi loại có vô hạn viên. An mỗi lần được lấy đúng 1 viên kẹo, và xác xuất để An lấy được mỗi loại kẹo là $ \frac{1}{n} $. Số lần kỳ vọng để An có thể lấy đủ n loại kẹo là bao nhiêu?

Gọi $ X $ là số lần An phải bốc để có đủ n loại kẹo, và gọi $ X_i $ là số kẹo mà An cần phải lấy để có loại kẹo mới, sau khi đã có đủ $ i-1 $ loại kẹo. Dễ thấy $ X_i $ sẽ là một biến ngẫu nhiên hình học với $ p_i = \frac{n - (i-1)}{n} $. Vậy nên $ E(X_i) = \frac{1}{p_i} $ và theo tính tuyến tính của hàm kỳ vọng, ta có:

$$ E(X) = \sum E(X_{i}) = n (1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}) \approx n ln(n) $$

$$ Var(X) = \sum _{i=1}^{n} Var(X_{i}) \leq \sum _{i=1}^{n} E^2(X_{i}) = \sum _{i=1}^{n} \frac{1}{p^2_{i}} = n^2 \sum _{i=1}^{n} \frac{1}{i^2} \leq n^2 \sum _{i=1}^{\infty} \frac{1}{i^2} = \frac{n^2 \pi^2}{6} $$

Với $ n = 9 $, ta có $ E(X) = n ln(n) = 9 ln(9) \approx 20 $, $ std(X) = \sqrt{\frac{9^2 \pi^2}{6}} \approx 11.54 $ và với giá trị $ A = 200 $, $ m = 1000 $ trong test case lớn, số blocks cần phải deploy là $ \lceil \frac{200}{9} \rceil = 23 $. Vậy tổng số lần deploy sẽ vào khoảng $ 23 * 20 \approx 460 < m = 1000 $.

Chebyshev's denial hay là Dùng dao mổ trâu giết gà

Nhưng liệu deploy $ n ln(n) $ lần có thật sự đã đủ? Phân tích về giá trị kỳ vọng chỉ cho ta chặn dưới của số lần phải deploy, nhưng không đảm bảo rằng sau đúng $ n ln(n) $ lần thì block sẽ được filled. Một câu hỏi khá tự nhiên được đặt ra: Với bao nhiêu lần deploy thì xác suất để một block được fill là nhiều hơn 80%? Nhiều hơn 90%? Nhiều hơn 99%?

Nếu ta deploy liên tục $ n ln(n) + cn $ lần, với $ c $ là tham số, thì xác suất $ X \geq nln(n) + cn $ sẽ bé hơn xác suất $ |X - nln(n)| \geq cn $. Áp dụng bất đẳng thức Chebyshev, ta được:

$$ P(|X - nln(n)| \geq cn) = P(|X - nln(n)| \geq \frac{c \sqrt{6}}{\pi} \sqrt{\frac{n^2 \pi^2}{6}}) \leq \frac{\pi^2}{6c^2} $$

Nếu $ c = 3 $, số lần deploys khoảng $ 9 ln(9) + 3 * 9 = 46 $, xác suất một block được filled chỉ là 82%. Trong khi đó, số lần cần phải deploy cho cả bảng là $ 46 * 23 > 1000 $. Như vậy, có hai khả năng xảy ra:

1. Thuật toán được mô tả bên trên chưa đủ tốt, còn có chỗ phải cải tiến
2. Cái chặn có được từ bất đẳng thức Chebyshev chưa thật sự đủ chặt

Giả thuyết 1. sớm bị bác bỏ sau khi tác giả nhắm mắt submit code và AC :) Câu hỏi còn lại là: Làm sao để tìm được một cái chặn tốt hơn cho giải thuật này?

Sức mạnh của union bound

Để tìm được cái chặn tốt hơn thực ra rất đơn giản. Nghĩ khác đi một tí:

• Giả sử ta deploy liên tục $ k $ lần vào ô trung tâm của một block.

• Xác suất một ô bất kỳ chưa được filled sẽ là $ (1 - \frac{1}{9})^k $.

• Xác suất có ít nhất một ô trong block chưa được filled sẽ là $ n (1 - \frac{1}{9})^k < n e^{-\frac{k}{n}} $.

Nếu ta chọn $ k = nln(n) + cn $ thì xác suất để một ô chưa được filled sau $ k $ lần deploys là bé hơn $ n e^{- \frac{k}{n}} = n e^{-ln(n) - c} < \frac{1}{e^c} $.

Nếu chọn $ c = 3 $ như lúc nãy thì xác suất thành công sau k lần deploys lúc này đã lớn hơn 95%. Hay như ở đây còn có cái chặn $ 1 - e^{-e^{-c}} $ tốt hơn nữa.

Bài học

• Bất đẳng thức Chebyshev không quá mạnh như bạn (thực ra là mình) nghĩ.

• Nghĩ đơn giản: Phần lớn các bài toán trong các kỳ thi competitive programming được nghĩ ra với tinh thần solvable trong vài giờ đồng hồ. Đừng phức tạp hóa vấn đề quá mức cần thiết.

• Google cho giới hạn quá đẹp. Xem bảng dưới đây, với xác suất thành công được tính theo $ e^{-e^{-c}} $:

Đây chỉ là worst-case scenario. Thí nghiệm của Google ở đây cho thấy bạn không thực sự cần nhiều hơn 850 lần deploys. Như “kỳ vọng”, số lần phải deploys trung bình vào khoảng 450-460.