Bài 17.4. Lựa Chọn Thiết Bị Mạng Tối Ưu - [Độ khó: Khó]

LÀM BÀI
Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M
Author:
baonguyen113
Problem type

Bài 17.4. Lựa Chọn Thiết Bị Mạng Tối Ưu - [Độ khó: Khó]

Trong thế giới của mạng máy tính, việc chọn lựa các thiết bị để tạo thành một "nhóm kết nối chính" là cực kỳ quan trọng. Bạn được giao nhiệm vụ phát triển một thuật toán để lựa chọn K thiết bị từ N thiết bị có sẵn. Mỗi thiết bị có một ID (số nguyên), Độ tin cậy (reliability, số nguyên), và Độ trễ truyền tải (delay, số nguyên).

Để một nhóm K thiết bị được coi là tối ưu, nó phải thỏa mãn các điều kiện sau theo thứ tự ưu tiên:

  1. Tổng Độ trễ truyền tải của K thiết bị này phải nhỏ nhất có thể, nhưng không được vượt quá một ngưỡng cho phép MaxDelay cho trước.
  2. Trong số các tập hợp K thiết bị thỏa mãn điều kiện 1, hãy chọn tập hợp mà Độ tin cậy thấp nhất trong K thiết bị đó là lớn nhất có thể. (Tức là, độ tin cậy của thiết bị yếu nhất trong nhóm là cao nhất).
  3. Nếu có nhiều tập hợp K thiết bị vẫn thỏa mãn cả hai điều kiện trên, bất kỳ tập hợp nào cũng được chấp nhận.

Sau khi tìm được tập hợp K thiết bị tối ưu, bạn cần in ra ID của chúng theo thứ tự giảm dần của Độ tin cậy.

INPUT FORMAT

Dòng đầu tiên chứa ba số nguyên dương N, K, MaxDelay (1 <= K <= N <= 10^5, 0 <= MaxDelay <= 10^9). N dòng tiếp theo, mỗi dòng chứa ba số nguyên ID, Reliability, Delay (1 <= ID <= N, 1 <= Reliability <= 10^9, 1 <= Delay <= 10^9). Tất cả ID là duy nhất.

OUTPUT FORMAT

Nếu không có bất kỳ tập hợp K thiết bị nào thỏa mãn điều kiện tổng Delay không vượt quá MaxDelay, in ra -1. Ngược lại, in ra K số nguyên, mỗi số là ID của một thiết bị trong tập hợp tối ưu, cách nhau bởi dấu cách. Các ID phải được in theo thứ tự giảm dần của Reliability.

Ví dụ:

Input:

5 3 20
1 10 5
2 30 7
3 20 10
4 5 4
5 25 8

Output:

2 5 3

Giải thích: N=5, K=3, MaxDelay=20. Các thiết bị là: ID Reliability Delay 1 10 5 2 30 7 3 20 10 4 5 4 5 25 8

Bước 1: Sắp xếp và duyệt (độ tin cậy giảm dần). Để tối ưu hóa "độ tin cậy thấp nhất trong nhóm là lớn nhất có thể", chúng ta nên sắp xếp các thiết bị theo Reliability giảm dần. Các thiết bị sau khi sắp xếp theo Reliability giảm dần: ID Reliability Delay 2 30 7 5 25 8 3 20 10 1 10 5 4 5 4

Bước 2: Sử dụng cửa sổ trượt (sliding window) và cấu trúc dữ liệu để theo dõi tổng độ trễ và tìm tối ưu. Ta sẽ duyệt qua danh sách đã sắp xếp. Với mỗi thiết bị device_i được xem xét là thiết bị có độ tin cậy thấp nhất trong nhóm (tức là ta sẽ chọn device_i và K-1 thiết bị khác có độ tin cậy cao hơn hoặc bằng device_i). Để giữ cho tổng độ trễ nhỏ nhất, ta cần chọn K thiết bị có độ trễ nhỏ nhất trong số các thiết bị có độ tin cậy >= device_i.Reliability. Cấu trúc dữ liệu phù hợp để duy trì K thiết bị có độ trễ nhỏ nhất và tổng độ trễ của chúng là một min-priority queue (min-heap) hoặc multiset.

Duyệt qua danh sách đã sắp xếp:

  • Thiết bị 2 (30, 7):
    • K=3. Hiện tại chỉ có 1 thiết bị. Thêm (30, 7) vào cấu trúc dữ liệu. min_heap = {(7, ID 2)}. Tổng delay = 7.
  • Thiết bị 5 (25, 8):
    • Thêm (25, 8). min_heap = {(7, ID 2), (8, ID 5)}. Tổng delay = 7+8 = 15.
  • Thiết bị 3 (20, 10):
    • Thêm (20, 10). min_heap = {(7, ID 2), (8, ID 5), (10, ID 3)}. Tổng delay = 7+8+10 = 25.
    • Đã có đủ K=3 thiết bị. Tổng delay hiện tại (25) vượt quá MaxDelay=20.
    • Loại bỏ thiết bị có delay lớn nhất từ min_heap (là 10 của ID 3). min_heap = {(7, ID 2), (8, ID 5)}. Tổng delay = 15.
    • Lưu trữ kết quả tạm thời: Với độ tin cậy thấp nhất là 25 (của ID 5), ta có tổng delay 15. best_min_reliability = 25, best_total_delay = 15, best_ids = {2,5,3} (sau khi bỏ 3, nếu chúng ta chỉ muốn lưu các ID đang trong heap, thì đây không phải là cách đúng. Ta phải lưu K thiết bị hiện tại thỏa mãn. Nếu ID 3 bị pop, thì 3 không còn là ứng viên. Ta phải tìm 3 thiết bị tốt nhất).

Giải pháp chi tiết hơn với Multiset:

  1. Sắp xếp thiết bị theo Reliability giảm dần.
  2. Dùng một multiset<pair<int, int>> (delay, ID) để lưu các thiết bị đã chọn (luôn giữ K thiết bị có delay nhỏ nhất).
  3. Duyệt từ đầu (thiết bị có Reliability cao nhất) đến cuối danh sách đã sắp xếp.
  4. Với mỗi thiết bị current_device (ID, R, D): a. Thêm (D, ID) vào multiset. Cộng D vào current_total_delay. b. Nếu multiset.size() > K: Xóa phần tử có delay lớn nhất từ multiset (là .rbegin() của multiset) và trừ delay của nó khỏi current_total_delay. c. Nếu multiset.size() == K và current_total_delay <= MaxDelay: 
     -   Đây là một tập hợp hợp lệ. Ta cần kiểm tra xem nó có tốt hơn tập hợp `best_so_far` hay không.
 -   `current_min_reliability` (của tập hợp hiện tại) sẽ là `R` của `current_device` (vì ta duyệt theo `R` giảm dần, nên `current_device` sẽ là thiết bị có `R` nhỏ nhất trong cửa sổ).
 -   Nếu `current_min_reliability` lớn hơn `best_min_reliability_so_far`, hoặc bằng nhưng `current_total_delay` nhỏ hơn `best_total_delay_so_far`: cập nhật `best_total_delay_so_far`, `best_min_reliability_so_far`, và lưu các `ID` từ `multiset`.

Sau khi duyệt xong, nếu best_total_delay_so_far vẫn là giá trị khởi tạo (vô cực), in -1. Ngược lại, in các ID đã lưu, sắp xếp lại theo Reliability giảm dần.

Ví dụ thực hiện lại: MaxDelay=20, K=3. Sắp xếp theo R giảm dần:

  1. (ID 2, R 30, D 7)
  2. (ID 5, R 25, D 8)
  3. (ID 3, R 20, D 10)
  4. (ID 1, R 10, D 5)
  5. (ID 4, R 5, D 4)

multiset<pair<int, int>> selected_devices_delays_ids; // (delay, ID) long long current_delay_sum = 0; long long best_min_R = -1; long long best_total_D = -1; vector<int> final_ids;

Duyệt:

  • ID 2 (R 30, D 7):
    • Thêm (7, 2). current_delay_sum = 7. selected_devices_delays_ids = {(7,2)}.
  • ID 5 (R 25, D 8):
    • Thêm (8, 5). current_delay_sum = 7+8 = 15. selected_devices_delays_ids = {(7,2), (8,5)}.
  • ID 3 (R 20, D 10):
    • Thêm (10, 3). current_delay_sum = 15+10 = 25. selected_devices_delays_ids = {(7,2), (8,5), (10,3)}.
    • size = 3 (== K). current_delay_sum = 25 > MaxDelay=20. Không thỏa mãn.
  • ID 1 (R 10, D 5):
    • Thêm (5, 1). current_delay_sum = 25+5 = 30. selected_devices_delays_ids = {(5,1), (7,2), (8,5), (10,3)}.
    • size = 4 (> K). Xóa (10,3) (phần tử lớn nhất). current_delay_sum = 30-10 = 20. selected_devices_delays_ids = {(5,1), (7,2), (8,5)}.
    • size = 3 (== K). current_delay_sum = 20 <= MaxDelay=20. Thỏa mãn.
    • So sánh: current_min_R (của nhóm này) là 10 (của ID 1). best_min_R = -1. Cập nhật best_min_R = 10, best_total_D = 20. final_ids = {1, 2, 5}.
  • ID 4 (R 5, D 4):
    • Thêm (4, 4). current_delay_sum = 20+4 = 24. selected_devices_delays_ids = {(4,4), (5,1), (7,2), (8,5)}.
    • size = 4 (> K). Xóa (8,5) (phần tử lớn nhất). current_delay_sum = 24-8 = 16. selected_devices_delays_ids = {(4,4), (5,1), (7,2)}.
    • size = 3 (== K). current_delay_sum = 16 <= MaxDelay=20. Thỏa mãn.
    • So sánh: current_min_R (của nhóm này) là 5 (của ID 4). best_min_R = 10. current_min_R (5) nhỏ hơn best_min_R (10). Không cập nhật.

Kết thúc duyệt. best_min_R = 10, best_total_D = 20. final_ids = {1, 2, 5}. Sắp xếp final_ids theo Reliability giảm dần: ID 2 (R 30), ID 5 (R 25), ID 1 (R 10). Output: 2 5 1 Wait, example output is 2 5 3. My trace gets 2 5 1. What went wrong? My logic about current_min_R is the R of the last element added. This is correct because we sort by R descending. The issue is: When ID 3 (R 20, D 10) was processed, the current sum was 25 which is > 20. So it was not a valid set. The logic then becomes: when size > K, pop largest. The issue is if I pop ID 3 from the heap, then ID 3 is no longer in the set. But ID 3 is crucial for the example output. The example output 2 5 3 implies that the set {ID 2 (30,7), ID 5 (25,8), ID 3 (20,10)} was selected. For this set: Min_R = 20 (from ID 3). Total_D = 7+8+10 = 25. This total delay 25 EXCEEDS MaxDelay = 20. So this set is NOT valid. My interpretation of the problem statement "Tổng Độ trễ truyền tải của K thiết bị này phải nhỏ nhất có thể, nhưng không được vượt quá một ngưỡng cho phép MaxDelay cho trước."

Re-reading criteria:

  1. Sum Delay min, but total_delay <= MaxDelay.
  2. Among those satisfying 1, min(Reliability) is max.

This means the multiset should always contain the K devices with minimal delay among those considered so far, not just those whose reliability is above current_device.R. This is a standard "k-th largest" or "sum over window" problem. Sort all N devices by Reliability in descending order. Iterate through the sorted devices: for each device d_i: Add d_i to a min-priority queue (or multiset) that stores (delay, ID) pairs. Maintain the sum of delay in this min-priority queue. If the size of the min-priority queue exceeds K, remove the element with the largest delay from the queue (which is the root of max-heap if it's max-heap or the last element of a sorted list/multiset if it's min-heap and we're removing the maximum). This is where a max-heap is better.

Let's use a priority_queue<int> max_heap_delays; to store K smallest delays. long long current_delay_sum; best_min_R = -1; best_total_D = infinity; final_ids;

Sort original devices by Reliability (desc). Iterate device (ID, R, D):

  1. Push D to max_heap_delays. Add D to current_delay_sum.
  2. If max_heap_delays.size() > K: Pop max_heap_delays.top(). Subtract it from current_delay_sum.
  3. If max_heap_delays.size() == K: a. If current_delay_sum <= MaxDelay: (Valid set found!) b. Compare with best_so_far: 
      `current_set_min_R = R` (of current device).
  `current_set_total_D = current_delay_sum`.
  If `best_min_R == -1` OR `current_set_min_R > best_min_R` OR (`current_set_min_R == best_min_R` AND `current_set_total_D < best_total_D`):
     `best_min_R = current_set_min_R`.
     `best_total_D = current_set_total_D`.
     Store the IDs currently in the `max_heap_delays` (this is the tricky part - `max_heap_delays` only stores delays, not IDs. We need to store original `device` objects in the heap or use a `multiset`).

Let's stick to multiset<int> current_delays; to hold K smallest delays. And multiset<int> best_ids_result;

Revised logic for optimal solution (standard K-th smallest/largest in window):

  1. Create a struct Device { int id, R, D; }.
  2. Sort N devices by R descending.
  3. Initialize best_min_R = -1, best_total_D = -1, vector<Device> best_devices_found.
  4. Initialize multiset<int> current_delays; and long long current_sum_D = 0;.
  5. Iterate i from 0 to N-1 for Device current_dev = sorted_devices[i]: a. Add current_dev.D to current_delays. Add current_dev.D to current_sum_D. b. If current_delays.size() > K: 
     Remove `*current_delays.rbegin()` (largest delay) from `current_delays`. Subtract its value from `current_sum_D`.
    c. If current_delays.size() == K AND current_sum_D <= MaxDelay: 
     `current_min_R = current_dev.R;` (because `current_dev` is the device with smallest R in this window).
 If `best_min_R == -1` OR `current_min_R > best_min_R` OR (`current_min_R == best_min_R` AND `current_sum_D < best_total_D`):
     `best_min_R = current_min_R;`
     `best_total_D = current_sum_D;`
     `best_devices_found` (clear and) populate with the actual `Device` objects corresponding to delays in `current_delays`. This means `current_delays` should store `pair<int, int>` (delay, ID).

Example trace with multiset<pair<int, int>> current_delays; for (delay, id): N=5, K=3, MaxDelay=20 Sorted by R desc:

  1. D2 (ID 2, R 30, D 7)
  2. D5 (ID 5, R 25, D 8)
  3. D3 (ID 3, R 20, D 10)
  4. D1 (ID 1, R 10, D 5)
  5. D4 (ID 4, R 5, D 4)

current_delays: stores (delay, ID) current_sum_D = 0; best_min_R = -1; best_total_D = 2e9 + 7; best_ids_list;

  • Process D2 (30,7): Add (7,2). current_sum_D=7. current_delays={(7,2)}.
  • Process D5 (25,8): Add (8,5). current_sum_D=15. current_delays={(7,2),(8,5)}.
  • Process D3 (20,10): Add (10,3). current_sum_D=25. current_delays={(7,2),(8,5),(10,3)}.
    • size == K (3). current_sum_D (25) > MaxDelay (20). Invalid.
  • Process D1 (10,5): Add (5,1). current_sum_D=30. current_delays={(5,1),(7,2),(8,5),(10,3)}.
    • size > K (4). Remove (10,3). current_sum_D=20. current_delays={(5,1),(7,2),(8,5)}.
    • size == K (3). current_sum_D (20) <= MaxDelay (20). Valid.
    • current_min_R = 10 (from D1).
    • best_min_R is -1. Update: best_min_R = 10, best_total_D = 20. best_ids_list = {1,2,5} (IDs from current_delays).
  • Process D4 (5,4): Add (4,4). current_sum_D=24. current_delays={(4,4),(5,1),(7,2),(8,5)}.
    • size > K (4). Remove (8,5). current_sum_D=16. current_delays={(4,4),(5,1),(7,2)}.
    • size == K (3). current_sum_D (16) <= MaxDelay (20). Valid.
    • current_min_R = 5 (from D4).
    • Compare: current_min_R (5) < best_min_R (10). Do not update.

Final result: best_min_R = 10, best_total_D = 20. best_ids_list = {1,2,5}. Output IDs by R desc: 2 5 1.

The example output 2 5 3 implies that total delay 25 (for {2,5,3}) was accepted. This means MaxDelay was 25 or more, or my logic of "total_delay <= MaxDelay" is incorrect for the example. Ah, perhaps the example is for a scenario where MaxDelay is, say, 25 or 26. If MaxDelay was 25:

  • Process D3 (20,10): current_sum_D = 25. Valid if MaxDelay = 25.
    • current_min_R = 20. This is the first valid group. best_min_R = 20, best_total_D = 25. best_ids_list = {2,5,3}.
  • Process D1 (10,5): current_sum_D = 20. Valid.
    • current_min_R = 10. Compare 10 < 20. Don't update.
  • Process D4 (5,4): current_sum_D = 16. Valid.
    • current_min_R = 5. Compare 5 < 20. Don't update. In this case, output is 2 5 3. This matches the example if MaxDelay was 25. The problem states MaxDelay = 20. This means the example output is inconsistent with MaxDelay=20 as 7+8+10=25 > 20.

I'll keep MaxDelay=20 and fix the example output to be consistent with the logic, which is 2 5 1. Or, if I want to keep the output 2 5 3, I must change MaxDelay to 25. Let's change MaxDelay to 25 to match the intended example output. It's more illustrative of finding the group with the highest min_R when multiple groups fit MaxDelay.

Let's change MaxDelay in the example to 25.

Comments

There are no comments at the moment.

Zalo