The Time When the Network Becomes Idle (LeetCode 2039)
Đề bài
LeetCode 2039 – The Time When the Network Becomes Idle (Thời điểm mạng trở nên rảnh) – độ khó Medium.
Có một mạng gồm $n$ máy chủ (server), được đánh số từ $0$ đến $n - 1$. Cho mảng số nguyên 2 chiều edges, trong đó edges[i] = [ui, vi] cho biết có một kênh truyền tin giữa hai máy chủ $u_i$ và $v_i$, qua kênh này hai máy có thể gửi bao nhiêu tin nhắn cho nhau cũng được, mỗi tin đi trực tiếp mất đúng một giây. Cho thêm mảng số nguyên patience độ dài $n$ (đánh số từ 0).
Mọi máy chủ đều liên thông, tức là một tin nhắn có thể đi từ một máy chủ bất kỳ tới mọi máy chủ khác, trực tiếp hoặc gián tiếp qua các kênh truyền tin.
Máy chủ số $0$ là máy chủ chính (master). Các máy còn lại là máy chủ dữ liệu (data). Mỗi máy chủ dữ liệu cần gửi tin nhắn của mình tới máy chủ chính để xử lý và chờ phản hồi. Tin nhắn di chuyển giữa các máy chủ một cách tối ưu, tức là mỗi tin nhắn đi tới máy chủ chính trong thời gian ít nhất. Máy chủ chính xử lý mọi tin nhắn vừa tới ngay lập tức và gửi phản hồi về máy chủ đã gửi tin theo đường đi ngược lại đường mà tin nhắn đã đi.
Tại đầu giây thứ $0$, mỗi máy chủ dữ liệu gửi tin nhắn của mình đi để được xử lý. Bắt đầu từ giây thứ $1$, tại đầu mỗi giây, mỗi máy chủ dữ liệu sẽ kiểm tra xem nó đã nhận được phản hồi cho tin nhắn mình gửi chưa (tính cả những phản hồi vừa mới tới):
- Nếu chưa, nó sẽ gửi lại tin nhắn theo chu kỳ. Máy chủ dữ liệu $i$ sẽ gửi lại tin nhắn mỗi
patience[i]giây, tức là máy $i$ sẽ gửi lại tin nhắn nếu đã trôi quapatience[i]giây kể từ lần gần nhất máy này gửi tin. - Ngược lại, máy chủ này sẽ không gửi lại nữa.
Mạng được gọi là rảnh (idle) khi không còn tin nhắn nào đang di chuyển giữa các máy chủ hoặc đang tới một máy chủ nào.
Yêu cầu: trả về giây sớm nhất mà bắt đầu từ đó mạng trở nên rảnh.
Ràng buộc:
n == patience.length- $2 \le n \le 10^5$
patience[0] == 0- $1 \le$
patience[i]$\le 10^5$ với $1 \le i \lt n$ - $1 \le$
edges.length$\le \min(10^5, \dfrac{n(n-1)}{2})$ edges[i].length == 2- $0 \le u_i, v_i \lt n$
- $u_i \ne v_i$
- Không có cạnh lặp.
- Mỗi máy chủ đều có thể tới được mọi máy chủ khác, trực tiếp hoặc gián tiếp.
Ví dụ 1:
Input: edges = [[0,1],[1,2]], patience = [0,2,1]
Output: 8Giải thích (xem hình minh hoạ bên dưới khối đề):
Tại (đầu) giây 0:
- Máy dữ liệu 1 gửi tin nhắn của nó (ký hiệu 1A) tới máy chủ chính.
- Máy dữ liệu 2 gửi tin nhắn của nó (ký hiệu 2A) tới máy chủ chính.
Tại giây 1:
- Tin 1A tới máy chủ chính. Máy chủ chính xử lý 1A ngay lập tức và gửi phản hồi 1A ngược về.
- Máy 1 chưa nhận được phản hồi nào. Mới trôi qua 1 giây ($1 \lt$
patience[1]$= 2$) kể từ lần gửi gần nhất, nên nó không gửi lại. - Máy 2 chưa nhận được phản hồi nào. Đã trôi qua 1 giây ($1 =$
patience[2]$= 1$) kể từ lần gửi gần nhất, nên nó gửi lại tin nhắn (ký hiệu 2B).
Tại giây 2:
- Phản hồi 1A tới máy 1. Máy 1 sẽ không gửi lại nữa.
- Tin 2A tới máy chủ chính. Máy chủ chính xử lý 2A ngay lập tức và gửi phản hồi 2A ngược về.
- Máy 2 gửi lại tin nhắn (ký hiệu 2C).
...
Tại giây 4:
- Phản hồi 2A tới máy 2. Máy 2 sẽ không gửi lại nữa.
...
Tại giây 7, phản hồi 2D tới máy 2.
Bắt đầu từ đầu giây 8, không còn tin nhắn nào đi giữa các máy chủ hoặc đang tới máy chủ nào. Đây chính là thời điểm mạng trở nên rảnh.
Ví dụ 2:
Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
Output: 3Giải thích: máy dữ liệu 1 và 2 nhận được phản hồi cho tin nhắn của mình vào đầu giây 2. Từ đầu giây 3, mạng trở nên rảnh.
2039. The Time When the Network Becomes Idle – Medium
There is a network of n servers, labeled from 0 to n - 1. You are given a 2D integer array edges, where edges[i] = [ui, vi] indicates there is a message channel between servers ui and vi, and they can pass any number of messages to each other directly in one second. You are also given a 0-indexed integer array patience of length n.
All servers are connected, i.e., a message can be passed from one server to any other server(s) directly or indirectly through the message channels.
The server labeled 0 is the master server. The rest are data servers. Each data server needs to send its message to the master server for processing and wait for a reply. Messages move between servers optimally, so every message takes the least amount of time to arrive at the master server. The master server will process all newly arrived messages instantly and send a reply to the originating server via the reversed path the message had gone through.
At the beginning of second 0, each data server sends its message to be processed. Starting from second 1, at the beginning of every second, each data server will check if it has received a reply to the message it sent (including any newly arrived replies) from the master server:
- If it has not, it will resend the message periodically. The data server
iwill resend the message everypatience[i]second(s), i.e., the data serveriwill resend the message ifpatience[i]second(s) have elapsed since the last time the message was sent from this server. - Otherwise, no more resending will occur from this server.
The network becomes idle when there are no messages passing between servers or arriving at servers.
Return the earliest second starting from which the network becomes idle.
Constraints:
n == patience.length2 <= n <= 105patience[0] == 01 <= patience[i] <= 105for1 <= i < n1 <= edges.length <= min(105, n * (n - 1) / 2)edges[i].length == 20 <= ui, vi < nui != vi- There are no duplicate edges.
- Each server can directly or indirectly reach another server.
Example 1:
Input: edges = [[0,1],[1,2]], patience = [0,2,1]
Output: 8Explanation (see the figure below the statement):
At (the beginning of) second 0,
- Data server 1 sends its message (denoted 1A) to the master server.
- Data server 2 sends its message (denoted 2A) to the master server.
At second 1,
- Message 1A arrives at the master server. Master server processes message 1A instantly and sends a reply 1A back.
- Server 1 has not received any reply. 1 second (1 < patience[1] = 2) elapsed since this server has sent the message, therefore it does not resend the message.
- Server 2 has not received any reply. 1 second (1 == patience[2] = 1) elapsed since this server has sent the message, therefore it resends the message (denoted 2B).
At second 2,
- The reply 1A arrives at server 1. No more resending will occur from server 1.
- Message 2A arrives at the master server. Master server processes message 2A instantly and sends a reply 2A back.
- Server 2 resends the message (denoted 2C).
...
At second 4,
- The reply 2A arrives at server 2. No more resending will occur from server 2.
...
At second 7, reply 2D arrives at server 2.
Starting from the beginning of the second 8, there are no messages passing between servers or arriving at servers. This is the time when the network becomes idle.
Example 2:
Input: edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
Output: 3Explanation: Data servers 1 and 2 receive a reply to their messages at the beginning of second 2. From the beginning of the second 3, the network becomes idle.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
class Solution (và 2 mảng toàn cục phía trên nó). Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), code trong bài có thêm hàm main đọc từ bàn phím theo định dạng: dòng 1 gồm $n$ và $m$ (số máy chủ, số cạnh); $m$ dòng tiếp theo, mỗi dòng 2 số $u_i, v_i$; dòng cuối gồm $n$ số của mảng patience. In ra một số nguyên là đáp án. Ví dụ 1 sẽ nhập là:3 2
0 1
1 2
0 2 1Tóm tắt đề bài cho bạn nào đọc đề gốc thấy rối: cho một đồ thị gồm $N$ đỉnh đánh số từ $0$ đến $N - 1$ và $M$ cạnh 2 chiều. Trạm chính để trả lời tin nhắn được đặt tại đỉnh $0$. Những đỉnh còn lại, mỗi đỉnh sẽ gửi 1 tin nhắn và những tin nhắn này sẽ hướng đến đỉnh $0$ theo đường đi ngắn nhất. Ban đầu, toàn bộ các đỉnh từ $1$ đến $N - 1$ đều gửi 1 tin nhắn. Đỉnh thứ $i$ cứ sau mỗi patience[i] giây sẽ tiếp tục gửi 1 tin nhắn. Các tin nhắn đi đến đỉnh $0$, đỉnh $0$ lập tức trả lời lại và tin nhắn trả lời về lại đỉnh đã gửi cũng theo đường đi ngắn nhất. Khi một đỉnh nhận được tin nhắn trả lời thì sẽ dừng việc gửi tin nhắn. Hỏi sau bao nhiêu giây thì hệ thống hoàn toàn ngưng, không còn tin nhắn nào chạy trên mạng nữa.
Xét lại ví dụ 1: đỉnh 1 cách đỉnh 0 một cạnh ⇒ tin nhắn đi rồi về mất 2 giây; patience[1] = 2 nên tới giây 2 (đúng lúc phải gửi lại) thì phản hồi đã về rồi ⇒ đỉnh 1 chỉ gửi đúng 1 tin. Đỉnh 2 cách đỉnh 0 hai cạnh ⇒ đi rồi về mất 4 giây, mà patience[2] = 1 nên nó gửi ở các giây 0, 1, 2, 3 (giây 4 phản hồi đầu tiên đã về nên thôi). Tin gửi lúc giây 3 phải tới giây $3 + 4 = 7$ mới có phản hồi về ⇒ từ giây 8 mạng rảnh.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào để nhảy tới:
Cách 1BFS + công thức thời điểm gửi cuối cùng – O(N + M)
Bước 1: BFS tìm đường đi ngắn nhất từ đỉnh 0
Vì các tin nhắn đều di chuyển đến đỉnh $0$ theo đường đi ngắn nhất, mà mỗi cạnh đi mất đúng 1 giây (đồ thị không trọng số), nên ta có thể sử dụng thuật toán BFS để tìm đường đi ngắn nhất từ đỉnh $0$ đến mỗi đỉnh. Ta tạm gọi dist[i] là độ dài đường đi ngắn nhất từ $0$ đến $i$.
Lưu ý là các tin nhắn không ảnh hưởng gì nhau (một kênh truyền bao nhiêu tin cùng lúc cũng được), nên từng đỉnh có thể xét độc lập: thời gian để một tin nhắn xuất phát từ $i$ đi đến đỉnh $0$ rồi quay về lại đỉnh $i$ luôn là 2 * dist[i].
Bước 2: đỉnh i gửi tin nhắn cuối cùng lúc nào?
Đặt $T = 2 \cdot dist[i]$ (thời gian khứ hồi) và $p$ = patience[i]. Đỉnh $i$ gửi tin ở các giây $0, p, 2p, 3p, \ldots$ cho đến khi phản hồi đầu tiên về tới, tức là tới giây $T$. Trong thời gian này, cứ sau $p$ giây thì đỉnh $i$ lại gửi ra thêm 1 tin nhắn, nên số lần gửi lại là 2 * dist[i] / p (chia nguyên).
Tuy nhiên, nếu 2 * dist[i] chia hết cho $p$, có nghĩa là đúng giây phải gửi lại thì tin nhắn trả lời đã về tại đỉnh $i$ kịp lúc (đỉnh kiểm tra phản hồi ở đầu giây, tính cả phản hồi vừa tới), nên tin nhắn cuối cùng đó không được gửi đi nữa. Do đó số lần gửi lại sẽ bị giảm đi 1 nếu 2 * dist[i] chia hết cho $p$.
Tin nhắn cuối cùng được gửi lúc giây $d \cdot p$ và phản hồi của nó về tới đỉnh $i$ lúc giây $time_i = T + d \cdot p = 2 \cdot dist[i] + d \cdot p$.
Trong các giá trị $time_i$, ta chọn giá trị lớn nhất; mạng rảnh từ giây sau đó ⇒ đáp án $= \max(time_i) + 1$.
Đỉnh 2: $T = 4$, $p = 1$ ⇒ $4 / 1 = 4$, chia hết ⇒ $d = 3$ ⇒ $time_2 = 4 + 3 \cdot 1 = 7$.
Đáp án $= \max(2, 7) + 1 = 8$ ✔.
Minh hoạ
Em nhập các cạnh (mỗi cạnh là 2 số $u\ v$, các cạnh cách nhau dấu phẩy) và mảng patience, rồi bấm Tiếp để xem: đầu tiên BFS loang từ đỉnh 0 để có dist (đồ thị được vẽ theo từng "lớp" khoảng cách), sau đó với từng đỉnh, bảng dòng thời gian tô các giây đỉnh đó gửi tin (vàng), các giây còn tin của nó đang chạy trên mạng (xanh), giây phản hồi cuối cùng về (xanh lá), và cuối cùng là giây mạng rảnh (đỏ):
Source code để các bạn tham khảo nếu làm theo hướng này (code của mình đã AC trên LeetCode, các bạn chỉ cần nộp phần từ 2 mảng toàn cục đến hết class Solution):
#include <bits/stdc++.h>
using namespace std;
int dist[100005];
vector <int> adj[100005];
class Solution {
public:
int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& a) {
int n = (int) a.size();
for (int i = 0; i < n; i++) {
adj[i].clear();
dist[i] = -1;
}
for (int i = 0; i < (int) edges.size(); i++) {
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
queue <int> q;
q.push(0);
dist[0] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < (int) adj[u].size(); i++) {
int v = adj[u][i];
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
int ans = 0;
for (int u = 1; u < n; u++) {
int r = (2 * dist[u]) % a[u];
int d = (2 * dist[u]) / a[u];
if (r == 0) {
d--;
}
int time = 2 * dist[u] + d * a[u];
ans = max(ans, time);
}
return ans + 1;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> edges(m, vector<int>(2));
for (int i = 0; i < m; i++) cin >> edges[i][0] >> edges[i][1];
vector<int> patience(n);
for (int i = 0; i < n; i++) cin >> patience[i];
Solution sol;
cout << sol.networkBecomesIdle(edges, patience);
return 0;
}import sys
from collections import deque
from typing import List
class Solution:
def networkBecomesIdle(self, edges: List[List[int]], a: List[int]) -> int:
n = len(a)
adj = [[] for _ in range(n)]
dist = [-1] * n
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
q = deque([0])
dist[0] = 0
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
ans = 0
for u in range(1, n):
r = (2 * dist[u]) % a[u]
d = (2 * dist[u]) // a[u]
if r == 0:
d -= 1
time = 2 * dist[u] + d * a[u]
ans = max(ans, time)
return ans + 1
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [[int(data[2 + 2 * i]), int(data[3 + 2 * i])] for i in range(m)]
patience = [int(x) for x in data[2 + 2 * m:2 + 2 * m + n]]
print(Solution().networkBecomesIdle(edges, patience))
main()dist, adj khai báo toàn cục, mà LeetCode gọi hàm nhiều lần (mỗi test một lần) trên cùng một chương trình, nên đầu hàm phải clear lại adj[i] và gán lại dist[i] = -1 cho các đỉnh $0..n-1$ – đó là vòng lặp đầu tiên trong code.Đánh giá độ phức tạp của cách làm này:
- Không gian: danh sách kề lưu $2M$ phần tử, cộng mảng
distvà hàng đợi $N$ phần tử ⇒ $O(N + M)$. - Thời gian: BFS thăm mỗi đỉnh 1 lần và duyệt mỗi cạnh 2 lần ⇒ $O(N + M)$; phần tính công thức cho từng đỉnh là $O(1)$ mỗi đỉnh ⇒ tổng cộng $O(N + M)$ nha các bạn.
int thoải mái.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét