Google Code Jam 2020 - Security Update
Xem PDFSecurity Update
Công ty Apricot Rules vừa cài đặt một bản cập nhật bảo mật quan trọng cho mạng của mình. Mạng có một máy nguồn, và mọi máy tính khác trong mạng đều kết nối với máy nguồn qua một dãy gồm một hoặc nhiều kết nối trực tiếp hai chiều.
Loại bản cập nhật này tự lan truyền: ngay khi một máy tính nhận bản cập nhật lần đầu tiên, máy đó lập tức bắt đầu truyền bản cập nhật tới tất cả các máy kết nối trực tiếp với nó. Mỗi kết nối trực tiếp có một giá trị độ trễ: số giây cần thiết để kết nối ấy truyền bản cập nhật (giống nhau theo cả hai chiều). Vì vậy, bản cập nhật không lan đến tất cả các máy ngay lập tức.
Các kỹ sư của Apricot Rules không biết bất kỳ giá trị độ trễ nào, nhưng họ biết tất cả chúng đều là số nguyên dương. Họ muốn bạn giúp xác định các giá trị độ trễ có thể là bao nhiêu, dựa trên những gì họ quan sát được về sự lan truyền của bản cập nhật trong một thí nghiệm gần đây.
Các kỹ sư của Apricot Rules chỉ cài đặt bản cập nhật trên máy nguồn, rồi chờ nó lan truyền khắp hệ thống cho đến khi mọi máy đều được cập nhật. Họ ghi lại một số thông tin về quá trình lan truyền. Cụ thể, với mỗi máy K không phải máy nguồn, bạn biết chính xác một trong hai điều sau:
- Khoảng thời gian chính xác, tính bằng giây, từ lúc máy nguồn nhận bản cập nhật đến lúc K nhận bản cập nhật lần đầu tiên.
- Số máy khác (bao gồm cả máy nguồn) nhận bản cập nhật lần đầu tiên sớm hơn K một cách nghiêm ngặt.
Lưu ý rằng nhiều máy có thể nhận bản cập nhật vào đúng cùng một thời điểm.
Bạn phải tính độ trễ theo giây cho mỗi kết nối trực tiếp giữa hai máy. Mỗi giá trị độ trễ phải là một số nguyên dương không lớn hơn \(10^6\). Tập các độ trễ bạn đưa ra phải phù hợp với toàn bộ thông tin đã biết. Đề bài bảo đảm có ít nhất một cách gán độ trễ phù hợp.
Dữ liệu vào
Dòng đầu tiên cho biết số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(C\) và \(D\): lần lượt là số máy tính và số kết nối trực tiếp. Các máy được đánh số từ 1 đến \(C\), trong đó máy 1 là máy nguồn.
Dòng tiếp theo chứa \(C-1\) số nguyên \(X_2, X_3, \ldots, X_C\). Giá trị \(X_i\) dương cho biết máy \(i\) nhận bản cập nhật sau máy 1 đúng \(X_i\) giây. Giá trị \(X_i\) âm cho biết có \(-X_i\) máy khác nhận bản cập nhật sớm hơn máy \(i\) một cách nghiêm ngặt; con số này bao gồm cả máy nguồn.
Sau đó có thêm \(D\) dòng biểu diễn \(D\) kết nối trực tiếp trong mạng. Dòng thứ \(i\) chứa hai số nguyên \(U_i\) và \(V_i\), cho biết máy \(U_i\) và máy \(V_i\) kết nối trực tiếp với nhau.
Dữ liệu ra
Với mỗi bộ test, in một dòng có dạng Case #x: y1 y2 ... yD, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn \(y_i\) là một số nguyên dương không lớn hơn \(10^6\), biểu diễn độ trễ tính bằng giây được gán cho kết nối trực tiếp thứ \(i\).
Ràng buộc
- \(1 \le T \le 100\).
- \(2 \le C \le 100\).
- \(C-1 \le D \le 1000\).
- \(1 \le U_i < V_i \le C\) với mọi \(i\).
- \((U_i,V_i) \ne (U_j,V_j)\) với mọi \(i \ne j\).
- Mọi máy (ngoại trừ máy nguồn) đều kết nối với máy nguồn qua một dãy gồm một hoặc nhiều kết nối trực tiếp.
- Tồn tại ít nhất một cách gán các giá trị độ trễ phù hợp với dữ liệu vào.
Phân nhóm
Test Set 1 (Phán quyết hiển thị)
\(-C < X_i < 0\) với mọi \(i\). (Bạn nhận được loại thông tin thứ hai cho tất cả các máy.)
Test Set 2 (Phán quyết ẩn)
- \(-C < X_i \le 1000\) với mọi \(i\).
- \(X_i \ne 0\) với mọi \(i\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 9/20 | 45% |
| Test Set 2 | 11/20 | 55% |
Ví dụ
Ví dụ 1
Dữ liệu mẫu và phần giải thích chính thức được trình bày đầy đủ ngay bên dưới.
Giải thích
Dữ liệu vào mẫu
3
4 4
-1 -3 -2
1 2
1 3
2 4
3 4
4 4
-1 -1 -1
1 4
1 2
1 3
2 3
3 2
-2 -1
2 3
1 3
Dữ liệu ra mẫu
Case #1: 5 10 1 5
Case #2: 2020 2020 2020 2020
Case #3: 1000000 1000000
Trong test mẫu số 1, hình sau biểu diễn mạng máy tính được minh họa bởi dữ liệu ra mẫu. Máy thứ \(i\) được biểu diễn bằng hình tròn mang nhãn \(i\). Một đường nối hai hình tròn biểu diễn một kết nối trực tiếp. Số trên mỗi đường biểu diễn độ trễ của kết nối trực tiếp đó.
Trong test mẫu số 2, ba kết nối đầu tiên phải có cùng độ trễ, còn kết nối thứ tư có thể có bất kỳ độ trễ hợp lệ nào. Lưu ý rằng \(-2\), \(0\), \(1000001\) và \(3.14\) là các ví dụ về độ trễ không hợp lệ.
Trong test mẫu số 3, hãy nhớ rằng các kết nối là hai chiều, nên bản cập nhật có thể truyền từ máy 3 sang máy 2. Bất kỳ hai giá trị độ trễ hợp lệ nào cũng dùng được ở đây.
Trường hợp sau không thể xuất hiện trong Test Set 1, nhưng có thể xuất hiện trong Test Set 2:
1
6 9
10 -2 -5 15 20
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6
Một trong các dữ liệu ra đúng là 10 12 4 15 8 3 9 7 5, như minh họa trong hình dưới đây.
Nguồn
Google Code Jam 2020, Vòng 2, bài Security Update.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2020 - Round 2 (16 Tháng năm, 2020)
Bình luận