Phân tích: Fair Warning

Đây hóa ra là bài khó nhất trong vòng loại. Một lý do có thể là lời giải cần số học với độ chính xác lớn. Việc dùng số lớn trong các cuộc thi lập trình tính giờ đôi khi bị xem là không công bằng, vì một số ngôn ngữ như Python hoặc Java có thư viện tích hợp để xử lý chúng, còn với các ngôn ngữ khác, bạn có thể phải tự viết hoặc tìm một thư viện bên ngoài như GNU Multi-Precision Library. Vì vòng loại kéo dài 24 giờ, chúng tôi nhân cơ hội này đưa ra một lời cảnh báo — và là một lời cảnh báo công bằng: từ giờ trở đi, số lớn là hoàn toàn hợp lệ, vì vậy hãy chuẩn bị sẵn một thư viện!

Bài toán nói về ước và bội, nên gợi ý rằng ta cần dùng khái niệm ước chung lớn nhất theo một cách nào đó. Để giải bài toán, trước hết ta cần tìm (T), rồi từ đó có thể dễ dàng tìm (y).

Hãy đơn giản hóa bài toán và chỉ xét hai số (a) và (b). Trong trường hợp này, ta cần tìm (T) lớn nhất sao cho tồn tại một (y) dương mà (a+y) và (b+y) đều là bội của (T). Khi đó

$
(a+y) mod T = (b+y) mod T,
$

suy ra

$
(a-b) mod T = 0.
$

Vì vậy, (T) phải là một ước của (|a-b|).

Quay lại bài toán với (N) số, ta đã chứng minh rằng (T) phải chia hết mọi (|t_i-t_j|). Điều này có nghĩa là đáp án là ước chung lớn nhất của tất cả các số (|t_i-t_j|).

Một nhận xét đơn giản có thể cải thiện thuật toán từ (O(N^2)) xuống còn (O(N)) lần lặp của thuật toán Euclid. Giả sử (a le b le c), khi đó

$
gcd(b-a,c-a)=gcd(b-a,c-a,c-b).
$

Để chứng minh, hãy xét bước đầu tiên của thuật toán Euclid. Vì (a le b le c), ta có (b-a le c-a), nên ở bước đầu tiên ta trừ (b-a) khỏi (c-a):

$
gcd(b-a,c-a)=gcd(c-b,b-a).
$

Điều này chứng minh nhận xét trên. Vì thế, để tìm (T), ta chỉ cần tính ước chung lớn nhất của tất cả các số (|t_i-t_1|).

Sau khi biết (T), ta dễ dàng tìm được (y) nhỏ nhất: nếu (t_1) đã chia hết cho (T) thì (y=0); nếu không thì (y=T-(t_1 mod T)).

Dưới đây là mã Python của Xiaomin Chen để giải một test:

def Gcd(a, b):
  if b == 0:
    return a
  return Gcd(b, a % b)

def Solve(L):
  y = L[0]
  L1 = [abs(x - y) for x in L]
  g = reduce(Gcd, L1)
  if y % g == 0:
    return 0
  else:
    return g - (y % g)

Các khái niệm hữu ích: ước chung lớn nhất, thuật toán Euclid, và số học độ chính xác tùy ý.

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Fair Warning, thuộc kho Google Coding Competitions (Apache-2.0).