Phân tích

Các cặp có thứ tự tạo thành một đồ thị có hướng, trong đó mỗi người là một đỉnh và mỗi đường truyền tin là một cạnh. Ta có thể xử lý riêng từng thành phần liên thông vì các thành phần độc lập với nhau. Trong phần còn lại, giả sử đồ thị liên thông.

Một nhận xét nữa: nếu một cạnh của đồ thị vô hướng tương ứng là một cầu — tức cạnh không nằm trên chu trình nào — thì bài toán vô nghiệm. Điều này suy ra từ điều kiện cân bằng tại các đỉnh khi mở rộng cho một tập đỉnh: gom các đỉnh ở mỗi phía của cầu thành một nhóm, tổng cân bằng của mỗi nhóm phải bằng \(0\), còn các cạnh nội bộ không ảnh hưởng đến tổng ấy. Vì cầu là cạnh duy nhất đi ra ngoài nhóm, giá trị của nó buộc phải bằng \(0\), trái với đề bài. Nói hình thức hơn, tính chất cân bằng tin được bảo toàn khi đồng nhất các đỉnh; đồng nhất toàn bộ đỉnh ở mỗi phía của cầu sẽ dẫn tới mâu thuẫn.

Vì mỗi cạnh có thể mang tin dương hoặc âm, ta có thể bỏ qua hướng và xét đồ thị vô hướng. Nếu đồ thị có hướng có hai cạnh ngược chiều \((v,w)\) và \((w,v)\), đồ thị vô hướng chỉ cần giữ hai cạnh song song giữa \(v\) và \(w\). Sau khi giải trên đồ thị vô hướng, ta đổi dấu giá trị của từng cạnh nếu cần để khớp với hướng ban đầu.

Test Set 1

Bộ nhỏ có nhiều nhất \(4\) người nên có thể có tới \(12\) cạnh. Nếu thử mọi giá trị hợp lệ, mỗi cạnh có tới \(2\times4^2=32\) lựa chọn và có thể có \(32^{12}\) đáp án — quá lớn để vét cạn. Tin tốt là chỉ có cỡ \(2^{12}\) đồ thị cần xét; ta loại các đồ thị có cầu rồi chạy phương pháp dự kiến trên mọi đồ thị còn lại để kiểm tra xem có tìm được nghiệm hay không.

Có thể ta không cần toàn bộ đoạn \([-16,16]\). Hãy thử hạn chế giá trị vào một tập nhỏ hơn. Test mẫu 5 cho thấy đôi khi cần số âm, nên chẳng hạn có thể thử \(\{-2,-1,1,2,3\}\). Thực tế, riêng tập này đủ giải mọi trường hợp nhỏ không có cầu; vì vậy có thể vét cạn mọi phép gán từ tập đó.

Test Set 2

Từ lời giải bộ nhỏ, ta có thể phỏng đoán mọi đồ thị không cầu đều có nghiệm. Điều này đúng, như lời giải 2 dưới đây chứng minh.

Lời giải 1: ngẫu nhiên hóa trên cây khung

Dùng DFS để dựng một cây khung của đồ thị vô hướng nền. Gán cho mọi cạnh ngoài cây một giá trị ngẫu nhiên khác \(0\) trong \([-K,K]\). Khi đó mỗi đỉnh có một độ lệch cân bằng nguyên. Xử lý các đỉnh theo thứ tự từ lá lên gốc, dùng cạnh chưa gán duy nhất còn lại để đưa độ lệch của đỉnh về \(0\). Sau khi cân bằng \(F-1\) đỉnh không phải gốc, gốc tự động cân bằng vì tổng độ lệch trên mọi đỉnh luôn bằng \(0\): một cạnh giá trị \(v\) đóng góp \(v\) ở một đầu và \(-v\) ở đầu kia.

Có thể đúng lúc cần sửa một đỉnh thì độ lệch của nó đã bằng \(0\), khiến cạnh cây tương ứng không thể nhận giá trị khác \(0\). Cũng có thể độ lệch quá lớn làm giá trị cần gán vượt phạm vi. Tuy nhiên, thực nghiệm cho thấy chọn \(K\) cỡ \(F\) khiến cả hai xác suất đều nhỏ. Nếu gặp lỗi, chỉ cần chạy lại. Miễn xác suất thành công là một hằng số không quá nhỏ, đủ nhiều lần thử cuối cùng sẽ tạo ra phép gán hợp lệ. Mỗi lần chạy tuyến tính, giới hạn lại nhỏ, nên có thể thử hàng nghìn lần cho mỗi bộ test, thậm chí nhiều hơn. Dù dữ liệu thực nghiệm về xác suất chưa mạnh, ta vẫn có thể đạt độ tin cậy cao. Cũng có thể không kiểm tra cầu tường minh: coi việc thất bại sau khoảng \(1000\) lần thử là dấu hiệu vô nghiệm.

Lời giải 2: phép dựng tất định

Một lần nữa, tìm cây khung DFS và đánh số các đỉnh theo thứ tự khám phá. Trong DFS trên đồ thị vô hướng, mọi cạnh ngoài cây đều nối một đỉnh với một tổ tiên của nó. Định hướng tất cả cạnh từ gốc xuống lá; sau khi giải xong ta đảo hoặc tách cạnh như đã giải thích. Gán giá trị \(1\) cho mọi cạnh ngoài cây, nghĩa là chúng gửi tin dương từ tổ tiên xuống hậu duệ. Gán giá trị âm cho các cạnh cây. Xử lý đỉnh theo thứ tự khám phá đảo ngược: giống lời giải ngẫu nhiên, mỗi đỉnh có đúng một cạnh kề chưa được gán, và ta gán giá trị duy nhất làm đỉnh cân bằng.

Ta chứng minh rằng nếu không có cầu thì mọi giá trị vừa gán đều âm, còn nếu có cầu thì sẽ xuất hiện giá trị \(0\). Ngay trước khi cân bằng đỉnh \(x\), tạm coi các cạnh chưa gán có giá trị \(0\). Gọi \(A\) là tập gồm \(x\) và mọi hậu duệ của \(x\). Có đúng một cạnh cây đi vào \(A\): cạnh \(e\) đang cần gán. Mọi cạnh khác đi vào \(A\) đều là cạnh ngoài cây và có giá trị \(1\). Vì vậy tổng độ lệch hiện tại của \(A\) bằng số cạnh ngoài cây đi vào \(A\). Do xử lý từ lá lên gốc, mọi đỉnh trong \(A\) trừ \(x\) đã cân bằng, nên độ lệch của \(A\) chính là độ lệch của \(x\).

Nếu số đó bằng \(0\), ngoài \(e\) không có cạnh nào đi vào \(A\), nên \(e\) là cầu. Nếu số đó dương — nó là số lượng cạnh nên không thể âm — độ lệch hiện tại của \(x\) dương và ta gán số đối của nó, một giá trị âm, cho \(e\). Giá trị này luôn thuộc \([-F^2,F^2]\): độ lớn của nó bằng một số cạnh trong đồ thị, trong khi tổng số cạnh không vượt \(F(F-1)<F^2\).

Lời giải 3: cộng theo chu trình

Luôn duy trì mọi đỉnh cân bằng. Ban đầu gán \(0\) cho mọi cạnh. Với mỗi cạnh vô hướng vẫn có giá trị \(0\), tìm một chu trình chứa nó rồi cộng \(-K\) vào mọi cạnh trên chu trình, trong đó \(K\) là số nguyên khác giá trị hiện tại của mọi cạnh thuộc chu trình. Cách chọn này không biến cạnh khác \(0\) thành \(0\), đồng thời luôn biến ít nhất cạnh đang xét từ \(0\) thành khác \(0\), nên quá trình chắc chắn kết thúc. Cộng cùng một lượng dọc một chu trình vẫn giữ cân bằng tại mọi đỉnh.

Nếu chọn \(K\) có giá trị tuyệt đối nhỏ nhất và chu trình ngắn nhất có thể, các giá trị được kỳ vọng không vượt phạm vi. Một cận trên dễ chứng minh cho trị tuyệt đối là \(FP/2\): luôn có thể chọn \(K\in[-F/2,F/2]\) vì không quá \(F\) giá trị bị cấm, và có nhiều nhất \(P\) bước. Tuy nhiên, nhiều kết quả cho biết đồ thị nhiều cạnh có rất nhiều chu trình ngắn, nên nhóm tác giả tin rằng không thể dựng trường hợp làm vượt phạm vi. Hơn nữa, có thể ngẫu nhiên hóa thứ tự sửa cạnh và thử lại nhiều lần để tránh các trường hợp cố tình dồn tải lên một cạnh; các trường hợp ấy có thể đồng thời sinh nhiều chu trình nhỏ, giúp sửa các cạnh khác với chi phí thấp. Ý tưởng dùng cây DFS để sửa cân bằng trong hai lời giải trước thực chất cũng là ý tưởng này, nhưng dùng các chu trình cơ sở của đồ thị thay vì mọi chu trình có thể.

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2017, Vòng 3, bài Good News and Bad News.