Đặt Trạm Phủ Sóng (MOBI – OLP 30/4 Khối 10)

Nguồn: OLP 30/4 Khối 10 (CLAOJ) Độ khó: Trung bình Cửa sổ trượt Mảng đánh dấu Hai con trỏ

Đề bài

MOBI – Đặt trạm phủ sóng (OLP 30/4 Khối 10)

Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte

Nhà cung cấp dịch vụ viễn thông Mobi đã khảo sát số lượng người sẽ dùng dịch vụ trên một con đường thẳng mới được xây dựng và đánh dấu lại những vị trí trên con đường này. Đầu con đường được đánh tọa độ bắt đầu từ 0. Tại vị trí có tọa độ $X$ ($X$ nguyên dương) có số lượng người sẽ sử dụng dịch vụ là $Y$. Trước mắt, nhà cung cấp dịch vụ cần đặt một trạm phát sóng có bán kính phủ sóng là $K$ đơn vị chiều dài để phủ sóng cho một số người sử dụng dịch vụ trên con đường này.

Yêu cầu: Bạn hãy xác định vị trí đặt trạm phát sóng (tọa độ nguyên dương) sao cho trạm có thể phục vụ được số lượng người sử dụng nhiều nhất có thể.

Dữ liệu:

• Dòng đầu tiên ghi hai số nguyên $N$ và $K$ $(0 \lt N \le 10^6,\ 0 \lt K \le 2 \cdot 10^6)$, trong đó $N$ là số điểm dân cư đã được đánh dấu, $K$ là bán kính phủ sóng của trạm.
• Trong $N$ dòng tiếp theo, dòng thứ $i$ $(i = 1..N)$ ghi hai số nguyên $X$ và $Y$ cho biết tại vị trí $X$ có số lượng người dùng là $Y$ $(0 \le X \le 10^6,\ 0 \le Y \le 10^4)$. Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả: một số nguyên cho biết số người dùng nhiều nhất sẽ được phục vụ.

Ví dụ – input

4 3
7 4
15 10
2 2
1 5

Ví dụ – output

11

Chọn vị trí đặt trạm phủ sóng tại $X = 4$. Như vậy có thể phủ sóng đến các vị trí có toạ độ $1, 2, 7$. Số lượng người sử dụng lớn nhất là $11$.

Lời mở đầu

Bài này áp dụng một kỹ thuật rất hay gặp có tên tiếng Anh là Sliding Window (tiếng Việt gọi đại khái là "cửa sổ trượt"). Bạn nào chưa biết kỹ thuật này thì cứ lấy từ khoá tiếng Anh đó search Google rồi đọc thêm các bài trên GeeksforGeeks nhé. Còn trong bài này mình áp dụng luôn, đọc xong là các bạn cũng hiểu được phần nào rồi 😉.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Bán kính $K = 3$, trên đường có 4 điểm dân cư: vị trí $1$ có $5$ người, vị trí $2$ có $2$ người, vị trí $7$ có $4$ người, vị trí $15$ có $10$ người. Nếu đặt trạm ở $X = 4$ thì trạm phủ sóng đoạn từ $4 - 3 = 1$ đến $4 + 3 = 7$, gom được các vị trí $1, 2, 7$ ⇒ $5 + 2 + 4 = 11$ người. Còn nếu ham vị trí $15$ (10 người) mà đặt trạm ở $X = 15$ thì đoạn phủ là $[12, 18]$, chỉ được đúng $10$ người thôi. Không có cách đặt nào được hơn $11$ nên đáp án là $11$.

Link nộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Nhận xétTrạm phủ đoạn [X − K, X + K]Cách 1Cửa sổ trượt O(10^6) · 100%Minh hoạBấm Tiếp xem cửa sổ trượt

Nhận xétTrạm phủ sóng một đoạn dài 2K

Các bạn xem nhé, trạm phát sóng đặt ở đâu thì phủ sóng được trong bán kính $K$ đơn vị. Vì mình đang xét trên một con đường thẳng, nên trạm đặt tại điểm $X$ sẽ phủ sóng đoạn đường từ điểm $X - K$ đến điểm $X + K$. Ví dụ $K = 3$, $X = 5$ thì phủ sóng đoạn từ $2$ đến $8$.

Vấn đề là đầu con đường bắt đầu từ $0$. Nếu đặt trạm ở $X = 0$ với $K = 3$ thì "về lý thuyết" nó phủ từ $-3$ đến $3$, nhưng thực tế chỉ là từ $0$ đến $3$ thôi, vì làm gì có các điểm $-3, -2, -1$. Đặt trạm sát đầu đường như vậy thì phí mất một phần sóng, nên ta chỉ cần quan tâm các vị trí có $X - K \ge 0 \Leftrightarrow X \ge K$. Khi đó:

Vị trí trạm X (K = 3)	Đoạn được phủ sóng
3	0 → 6
4	1 → 7
5	2 → 8
6	3 → 9
…	…

Các bạn có nhìn ra quy luật không? Đoạn đầu tiên bắt đầu từ $0$ và kết thúc ở $2K$. Đoạn tiếp theo thì cả đầu lẫn cuối cùng tăng lên 1 đơn vị: từ $1$ đến $2K + 1$, rồi từ $2$ đến $2K + 2$, và cứ thế… Tất cả các đoạn đều có cùng độ dài $2K + 1$ vị trí.

Vì sao bỏ qua X < K vẫn đúng?

Đặt trạm tại $X \lt K$ thì đoạn phủ thực tế là $[0, X + K]$, nằm gọn trong đoạn $[0, 2K]$ của trạm đặt tại $X = K$. Nên trạm tại $X = K$ luôn phục vụ được ít nhất bằng ⇒ không cần xét $X \lt K$. Tương tự, đặt trạm quá xa về bên phải (vượt khỏi $10^6$) cũng chẳng được thêm ai. Đề cũng chỉ đòi in ra số người, không cần in vị trí, nên ta chỉ quan tâm tổng lớn nhất.

Bài toán quy về

Gọi $a[x]$ là số người tại vị trí $x$ (vị trí không có ai thì $a[x] = 0$). Tìm tổng lớn nhất của $2K + 1$ phần tử liên tiếp trong mảng $a[0..10^6]$: $\max\limits_{s}\ \big(a[s] + a[s+1] + \dots + a[s + 2K]\big)$.

Cách 1Mảng đánh dấu + cửa sổ trượt – O(10^6)

Trước hết, vì toạ độ $X$ chỉ nằm trong $[0, 10^6]$, mình tạo mảng $a$ có $10^6 + 1$ (một triệu lẻ một) phần tử, chỉ số từ $0$ đến $10^6$ ứng với từng vị trí trên đường. Đọc mỗi điểm dân cư $(x, y)$ thì ghi $y$ vào ô $a[x]$ – đây chính là kỹ thuật mảng đánh dấu.

Tiếp theo, mình tính sum là tổng số người trong đoạn đầu tiên từ $0$ đến $2K$, rồi khởi tạo Max = sum. Sang đoạn tiếp theo từ $1$ đến $2K + 1$, ta không cần chạy vòng lặp cộng lại từ đầu cả đoạn. Bản chất là ta chỉ:

• bỏ đi vị trí $0$ ở đầu trái: sum -= a[0];
• nhận thêm vị trí $2K + 1$ ở đầu phải: sum += a[2K + 1].

Thế là có ngay sum của đoạn mới, đem so với Max, lớn hơn thì cập nhật. Tổng quát: đoạn thứ $i$ là $[i, 2K + i]$, cứ trừ đi ô đầu tiên của đoạn trước và cộng thêm 1 ô mới bên phải. Còn $2K + i \le 10^6$ thì còn xét tiếp, $2K + i \gt 10^6$ thì dừng.

Đoạn đang xét giống như một cánh cửa sổ có bề rộng cố định, trượt dần từ trái qua phải: mỗi bước một ô rơi ra bên trái, một ô lọt vào bên phải. Kỹ thuật này gọi là Sliding Window là vậy đó 😄.

Công thức trượt

Cửa sổ $[start, finish]$ với $finish - start = 2K$. Trượt 1 bước: $sum \mathrel{-}= a[start - 1],\quad sum \mathrel{+}= a[finish]$ (sau khi đã start++, finish++). Mỗi bước chỉ tốn $O(1)$ thay vì $O(K)$.

Đừng tính lại tổng cả đoạn mỗi lần!

Nếu với mỗi vị trí đặt trạm ta lại chạy vòng lặp cộng $2K + 1$ ô thì tổng số phép tính cỡ $10^6 \times 2K$, với $K$ lớn là cỡ $10^{12}$ ⇒ TLE chắc luôn. Cửa sổ trượt giúp mỗi bước chỉ còn 2 phép tính.

Minh hoạ cửa sổ trượt

Em nhập bán kính $K$ và các điểm dân cư dạng x y (cách nhau dấu ;), rồi bấm Tiếp để xem cửa sổ trượt. Để dễ nhìn, con đường được "thu ngắn" lại chỉ tới vị trí xa nhất cần xét (code thật thì chạy tới $10^6$, phần sau toàn số 0 nên không đổi kết quả).

K Các điểm (x y)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e6;
int a[SIZE + 1];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    while(n--){
        int x, y;
        cin >> x >> y;
        a[x] += y;
    }
    int start = 0;
    int finish = min(2 * k, SIZE);
    long long Max = 0, sum = 0;
    for(int i = start; i <= finish; ++i){
        sum += a[i];
    }
    Max = sum;
    start++;
    finish++;
    while(finish <= SIZE){
        sum -= a[start - 1];
        sum += a[finish];
        Max = max(Max, sum);
        start++;
        finish++;
    }
    cout << Max;
    return 0;
}

import sys

SIZE = int(1e6)
a = [0] * (SIZE + 1)

data = list(map(int, sys.stdin.read().split()))
ptr = 0
n = data[ptr]
ptr += 1
k = data[ptr]
ptr += 1
for _ in range(n):
    x = data[ptr]
    ptr += 1
    a[x] += data[ptr]
    ptr += 1

start = 0
finish = min(2 * k, SIZE)
Max = 0
sum_ = 0
for i in range(start, finish + 1):
    sum_ += a[i]
Max = sum_
start += 1
finish += 1
while finish <= SIZE:
    sum_ -= a[start - 1]
    sum_ += a[finish]
    Max = max(Max, sum_)
    start += 1
    finish += 1
print(Max)

Lưu ý với Python

Code Python nộp trên web bị TLE, mặc dù ý tưởng mọi thứ tương đương code C++. Vấn đề là Python chạy chậm hơn C++ rất nhiều (vòng while phải chạy cả triệu lần), nếu bài này cho thời gian giới hạn riêng cho Python (ví dụ 3 giây) thì sẽ AC.

Trong khung chạy tay dưới đây, vòng while thật sự chạy tới tận $10^6$, nên khi cửa sổ đã trượt qua hết các điểm dân cư (từ đó về sau chỉ toàn trừ 0 cộng 0), mình gộp phần còn lại thành một bước cho các bạn đỡ phải bấm cả triệu lần 😅.

C++▶ Chạy tay từng dòng codeMảng đánh dấu a[x], tính tổng đoạn đầu [0, 2K] rồi trượt cửa sổ tới hết đường.

Dữ liệu vào (stdin) – sửa thoải mái4 3 7 4 15 10 2 2 1 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const int SIZE = 1e6;

5int a[SIZE + 1];

6

7int main(){

8 ios::sync_with_stdio(0);

9 cin.tie(0);

10 int n, k;

11 cin >> n >> k;

12 while(n--){

13 int x, y;

14 cin >> x >> y;

15 a[x] += y;

16 }

17 int start = 0;

18 int finish = min(2 * k, SIZE);

19 long long Max = 0, sum = 0;

20 for(int i = start; i <= finish; ++i){

21 sum += a[i];

22 }

23 Max = sum;

24 start++;

25 finish++;

26 while(finish <= SIZE){

27 sum -= a[start - 1];

28 sum += a[finish];

29 Max = max(Max, sum);

30 start++;

31 finish++;

32 }

33 cout << Max;

34 return 0;

35}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code:

1. Mảng có $10^6 + 1$ phần tử là khá lớn, khai báo bên trong hàm main dễ bị tràn bộ nhớ stack, nên mình khai báo mảng làm biến toàn cục (vừa an toàn, vừa được tự khởi tạo toàn số 0).
2. while(n--) là cách viết gọn cho vòng lặp chạy đủ $n$ lần. Biến x nhận vị trí dân cư, chính là chỉ số của mảng a, nên a[x] chứa số người tại vị trí đó.
3. Mỗi đoạn ta xét có chỉ số từ start đến finish. Ban đầu start = 0, finish theo lẽ là $2K$. Nhưng đề cho $K$ tới $2 \cdot 10^6$, nên $2K$ có thể vượt quá chỉ số cuối cùng của mảng là $10^6$. Vì thế mình lấy min(2 * k, SIZE): nếu $2K$ quá lớn thì chỉ cộng hết toàn bộ mảng thôi.
4. Sau khi có sum của đoạn đầu thì gán Max = sum, rồi start++; finish++; để trượt qua đoạn tiếp theo. Vòng while kiểm tra finish <= SIZE, tức cửa sổ vẫn còn nằm trên đường, chưa trượt lố. Trong thân vòng lặp: trừ đi a[start - 1] (phải $-1$ vì start đã tăng rồi, $-1$ để trở về ô start cũ) và cộng thêm a[finish] (ô mới ngay sau ô finish cũ). Có sum mới thì so với Max và cập nhật. Khi vòng while kết thúc thì in Max.

Hai chỗ mình chỉnh nhẹ so với code gốc

• Code gốc của mình trên Facebook đọc thẳng cin >> a[x]. Đề không nói rõ các toạ độ $X$ có phân biệt hay không, nên mình đổi thành a[x] += y: lỡ có 2 dòng cùng toạ độ thì cộng dồn cả hai, không bị dòng sau ghi đè dòng trước. Nếu toạ độ phân biệt thì hai cách như nhau.
• Đề gốc thi offline đọc/ghi file MOBI.INP / MOBI.OUT (dùng freopen). Trên hệ thống chấm online thì đọc/ghi chuẩn (bàn phím/màn hình) nên code ở trên mình bỏ freopen đi. Đi thi offline thì các bạn nhớ thêm lại nhé.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(V)$ với $V = 10^6$ là toạ độ lớn nhất theo đề, vì mình tạo mảng $10^6 + 1$ phần tử.
• Thời gian: đọc $N$ điểm mất $O(N)$, cộng đoạn đầu và trượt cửa sổ thì mỗi ô của mảng được cộng vào đúng 1 lần, trừ ra tối đa 1 lần ⇒ $O(V)$. Tổng cộng $O(N + V)$, tức cỡ $O(10^6)$ trong bài này. (Ở đây ^ là ký hiệu lũy thừa nhé: $10^6$ là một triệu, chứ không phải phép xor bit đâu nha các bạn 😁.)

Không gian$O(10^6)$

Thời gian$O(N + 10^6)$

Với độ phức tạp này thì yên tâm không bị TLE: giới hạn 1 giây chạy được khoảng $(3 \to 5) \cdot 10^7$, cao lắm là $10^8$ phép tính, mà $10^6$ còn ít hơn ngưỡng đó cả 50 đến 100 lần.

Nhớ dùng long long cho sum, Max

Một đoạn có thể chứa tới $10^6$ điểm, mỗi điểm $10^4$ người ⇒ tổng tới $10^{10}$, vượt giới hạn int (khoảng $2.1 \cdot 10^9$). Vì vậy sum và Max phải là long long.

Ghi chú của mình: code C++ ở trên đã được kiểm tra với 300 bộ test ngẫu nhiên nhỏ (có cả điểm ở toạ độ 0, điểm sát $10^6$, $2K$ lớn hơn cả con đường), so với code vét cạn thử mọi vị trí đặt trạm – khớp hết; code Python được so trên một phần các bộ đó, cũng khớp. Với test lớn nhất $N = 10^6$ điểm: bản C++ tốn khoảng 0.3 giây CPU, còn bản Python tốn khoảng 2 giây CPU – đúng như lưu ý ở trên là Python dễ bị TLE với giới hạn 1 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇