Phân tích: Security Update

Gọi \(R_i\) là số máy nhận bản cập nhật trước máy \(i\), và \(T_i\) là khoảng thời gian từ lúc máy 1 nhận bản cập nhật đến lúc máy \(i\) nhận được nó. Với mỗi \(i\), dữ liệu vào cho ta chính xác một trong hai số này. Để thuận tiện, ta có thể đặt \(R_1=T_1=0\).

Một bài toán đơn giản hóa

Trước tiên, giả sử ta biết tất cả các giá trị \(T_i\). Nếu máy \(i\) và máy \(j\) có một kết nối trực tiếp và \(T_i=T_j\), thì mọi đường đi đến máy \(i\) trong thời gian \(T_i\) đều không đi qua máy \(j\), và ngược lại, bởi vì tất cả các độ trễ đều dương. Do đó, ta có thể gán bất kỳ độ trễ dương nào cho tất cả những kết nối như vậy. Nếu máy \(i\) có giá trị \(T_i\) đã cho, thì mọi kết nối đi từ máy \(j\) với \(T_j<T_i\) phải có độ trễ ít nhất là \(T_i-T_j\); nếu không, bản cập nhật có thể đến máy \(i\) trong thời gian nhỏ hơn \(T_i\) bằng cách đến máy \(j\) trong thời gian \(T_j\) rồi sử dụng kết nối đó. Ngoài ra, với ít nhất một máy \(j\), độ trễ của kết nối giữa \(i\) và \(j\) phải bằng chính xác \(T_i-T_j\); nếu không, thời gian để bản cập nhật đến máy \(i\) sẽ lớn hơn \(T_i\). Một cách đơn giản để giải bài toán này là đặt độ trễ của mọi kết nối giữa hai máy có giá trị \(T\) khác nhau bằng chính xác \(|T_i-T_j|\); cách này mất thời gian \(O(D)\).

Lưu ý rằng thuật toán trên tìm được một cách gán hợp lệ cho bất kỳ tập giá trị \(T_i\) nào. Để giải các test thực tế, ta chỉ còn bài toán sau: khi biết một số giá trị \(T_i\) và một số giá trị \(R_i\) khác, hãy gán mọi giá trị chưa biết sao cho việc sắp xếp các máy theo \(T_i\) cũng khiến chúng được sắp xếp theo \(R_i\), và ngược lại. Đặc biệt, các máy có giá trị \(T\) bằng nhau phải có giá trị \(R\) bằng nhau, và ngược lại.

Test Set 1

Trong test set này, ta có thể giải bài toán con ở phần trước bằng cách đặt \(T_i:=R_i\).

Test Set 2

Với Test Set 2, ta lại tập trung giải bài toán con. Trước tiên, ta sắp thứ tự các máy theo giá trị \(T_i\) cuối cùng của chúng (hay tương đương, theo giá trị \(R_i\) cuối cùng). Ta có thể chia tập các máy không phải máy nguồn thành hai phần: những máy mà ta biết \(R_i\) (phần R) và những máy mà ta biết \(T_i\) (phần T). Ta sắp xếp riêng từng phần theo thứ tự không giảm của giá trị đã biết. Lúc này ta có hai tập đã có đúng thứ tự tương đối và cần trộn chúng như bước cuối của Merge Sort. Ta xếp máy nguồn trước tiên. Sau đó, ta lần lượt duyệt qua \(C-1\) vị trí còn lại theo thứ tự. Giả sử ta đã trộn \(N\) máy và máy \(k\) là máy cuối cùng trong số đó. Gọi \(i\) và \(j\) lần lượt là các máy đầu tiên còn lại trong phần R và phần T. Nếu \(R_i \le N\), ta lấy máy \(i\) tiếp theo và đặt \(T_i:=T_k\) nếu \(R_i=R_k\), còn nếu không thì đặt \(T_i:=T_k+1\). Nếu \(R_i>N\), ta lấy máy \(j\) tiếp theo và đặt \(R_j:=R_k\) nếu \(T_j=T_k\), còn nếu không thì đặt \(R_j:=N\).

Ta có thể chứng minh rằng nếu tập giá trị ban đầu phù hợp với ít nhất một cách gán độ trễ (điều mà đề bài bảo đảm), quy trình này tạo ra một thứ tự và một cách gán các giá trị còn thiếu hợp lệ; hơn nữa, nó tạo ra một cách mà giá trị \(T\) của máy cuối cùng trong thứ tự là nhỏ nhất. Ta chứng minh bằng quy nạp theo số lượng máy. Với một máy, điều này hiển nhiên đúng. Giả sử ta có \(C>1\) máy. Theo giả thuyết quy nạp, \(C-1\) máy đầu tiên trong thứ tự đã được sắp xếp và gán giá trị một cách phù hợp, với giá trị \(T\) của máy cuối cùng là nhỏ nhất trong mọi phương án. Giả sử máy cuối cùng trong toàn bộ thứ tự là máy \(i\), còn máy áp chót là máy \(j\). Theo định nghĩa của cách ta gán các giá trị còn thiếu, \(R_i=R_j\) khi và chỉ khi \(T_i=T_j\). Nếu quả thực \(R_i=R_j\) và \(T_i=T_j\), thì điều kiện đối với cách gán cuối cùng tương đương với giả thuyết quy nạp. Nếu máy \(i\) và máy \(j\) thuộc cùng một phần, lựa chọn thứ tự giữa chúng đã được cố định, và cách gán các giá trị \(T\) nếu cần rõ ràng là nhỏ nhất. Vì vậy, ta xét tiếp trường hợp máy \(i\) thuộc phần khác với máy \(j\), đồng thời các giá trị \(R\) và \(T\) của chúng khác nhau. Có hai trường hợp: máy \(i\) thuộc phần R hoặc thuộc phần T.

Nếu máy \(i\) thuộc phần R, thì theo định nghĩa, giá trị \(T\) được gán cho nó là lớn nhất trong tất cả các máy, và đó là giá trị nhỏ nhất có thể để nó đứng sau máy \(j\), mà giá trị của máy \(j\) là nhỏ nhất theo giả thuyết quy nạp. Xét về thứ tự, theo giới hạn ta có \(R_i \le C-1\). Vì máy \(j\) thuộc phần T và đã được chọn cho vị trí \(C-1\) (khi \(N=C-2\)), điều đó có nghĩa là \(R_i>C-2\). Do đó, \(R_i=C-1\), và vị trí được chọn là đúng.

Mặt khác, nếu máy \(i\) thuộc phần T, thì giá trị \(T\) của nó là nhỏ nhất vì \(T_i\) đã cố định. Xét về thứ tự, lưu ý rằng mọi máy khác hoặc có giá trị \(T\) nhỏ hơn nghiêm ngặt \(T_i\), hoặc có giá trị \(R\) nhỏ hơn nghiêm ngặt \(C-1\), nên không máy nào trong số đó có thể đứng cuối. Theo giả thuyết quy nạp, \(T_j\) là nhỏ nhất trong mọi thứ tự khả dĩ; do tồn tại một cách gán đầy đủ, điều này có nghĩa là phải có \(T_j<T_i\), kéo theo thứ tự cuối cùng và cách gán giá trị là phù hợp.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 2 — Security Update.