Drone thăm đồng (Đề tự luyện HSG Tin 12 – Bài 2)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhKhoảng cách ChebyshevXoay 45 độSắp xếpTổng tiền tố

Đề bài

Drone thăm đồng. Có $N$ thửa ruộng ở các ô $(x_i, y_i)$ đôi một khác nhau trên lưới. Mỗi giây drone bay từ ô đang đứng sang một trong $8$ ô xung quanh (chung cạnh hoặc chung đỉnh). Thời gian bay giữa hai thửa là số giây ít nhất. Tính tổng thời gian bay giữa mọi cặp thửa $i < j$.

Dữ liệu vào: dòng đầu $N$ ($1 \le N \le 2 \cdot 10^5$); $N$ dòng sau mỗi dòng $x_i, y_i$ ($0 \le x_i, y_i \le 10^8$).

Kết quả: tổng thời gian bay giữa mọi cặp thửa.

• Subtask 1 (20%): $N \le 2000$.
• Subtask 2 (30%): $y_1 = y_2 = \ldots = y_N$.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Input

4
7 4
1 1
9 3
4 2

Output

27

Giải thích

Thời gian bay của 6 cặp $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ lần lượt là $6, 2, 3, 8, 3, 5$ giây, tổng $27$. Ví dụ từ $(1, 1)$ sang $(4, 2)$: $(1,1) \to (2,2) \to (3,2) \to (4,2)$, mất $3$ giây.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Drone thăm đồng

Lời mở đầu

Bài này có hai bước suy nghĩ: (1) thời gian bay giữa hai thửa bằng bao nhiêu, (2) cộng cho $2 \cdot 10^{10}$ cặp thế nào cho nhanh.

Nhận xét 1 – thời gian bay. Đặt $dx = |x_i - x_j|$, $dy = |y_i - y_j|$. Mỗi giây drone chỉ đổi cột đi tối đa $1$ và đổi hàng đi tối đa $1$, nên cần ít nhất $\max(dx, dy)$ giây. Và $\max(dx, dy)$ giây là đủ: bay chéo $\min(dx, dy)$ bước (mỗi bước giảm cả hai khoảng cách), rồi bay thẳng nốt $|dx - dy|$ bước. Vậy

$$d(i, j) = \max\left(|x_i - x_j|,\ |y_i - y_j|\right).$$

Khoảng cách này có tên là khoảng cách Chebyshev (cũng là số nước đi ít nhất của quân Vua trên bàn cờ).

Hình 1. Thời gian bay giữa hai ô bằng $\max(dx, dy)$.

Nhận xét 2 – cái khó nằm ở phép cộng. Với $N = 2 \cdot 10^5$ có gần $2 \cdot 10^{10}$ cặp, không thể duyệt từng cặp. Nếu thời gian bay là $dx + dy$ (chỉ bay ngang/dọc) thì tổng tách đôi được: $\sum (dx + dy) = \sum dx + \sum dy$, mỗi tổng là bài toán một chiều. Nhưng với $\max$ thì không tách được: $\sum \max(dx, dy) \ne \max\left(\sum dx, \sum dy\right)$.

Ví dụ của đề "hiền" quá!

Trong ví dụ, cặp thửa nào cũng có $dx \ge dy$, nên tổng các $\max$ đúng bằng $\sum dx = 27$ – công thức sai $\max\left(\sum dx, \sum dy\right)$ vẫn ra $27$. Chỉ cần thêm một thửa ở $(7, 9)$ là lộ ngay. Bộ test thật có đủ kiểu điểm nên công thức này chỉ sống được ở subtask 2.

Ba cách dưới đây đi từ chậm đến nhanh:

Cách 1Duyệt mọi cặp · 20%Cách 2Cùng hàng: sắp xếp + tiền tố · 50%Cách 3Xoay 45° · 100%

Cách 1Duyệt mọi cặp – O(N²) · 20%

Cộng $\max(|x_i - x_j|, |y_i - y_j|)$ cho mọi cặp $i < j$. Với $N \le 2000$ là khoảng $2 \cdot 10^6$ cặp, rất nhanh. Lưu ý tổng có thể tới $2 \cdot 10^6 \cdot 10^8 = 2 \cdot 10^{14}$ – phải dùng long long.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    long long ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            ans += max(llabs(x[i] - x[j]), llabs(y[i] - y[j]));   // so giay bay giua 2 thua
    cout << ans << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = [int(t) for t in data[1:1 + 2 * n:2]]
    y = [int(t) for t in data[2:2 + 2 * n:2]]
    ans = 0
    for i in range(n):
        xi = x[i]; yi = y[i]
        for j in range(i + 1, n):
            dx = abs(xi - x[j]); dy = abs(yi - y[j])
            ans += dx if dx > dy else dy          # so giay bay giua 2 thua
    sys.stdout.write(str(ans) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 2Cùng một hàng: sắp xếp + tổng tiền tố – O(N log N) · 50%

Khi mọi thửa cùng hàng thì $dy = 0$, thời gian bay chỉ còn $|x_i - x_j|$. Bài toán "tổng $|a_i - a_j|$ trên mọi cặp" có một mẹo kinh điển: sắp xếp tăng dần. Khi đó với $j < i$ ta có $a_j \le a_i$, nên $|a_i - a_j| = a_i - a_j$ và phần đóng góp của $a_i$ với tất cả các số đứng trước nó là

$$\sum_{j < i} (a_i - a_j) = a_i \cdot i - (a_0 + a_1 + \ldots + a_{i-1}).$$

Duyệt $i$ từ trái sang phải, giữ biến pre là tổng các số đã đi qua là tính xong trong $O(N)$ sau khi sắp xếp.

Ví dụ $a = [1, 4, 7, 9]$ (đã sắp xếp): đóng góp lần lượt $0$, $4 \cdot 1 - 1 = 3$, $7 \cdot 2 - 5 = 9$, $9 \cdot 3 - 12 = 15$; tổng $27$ – đúng bằng $3 + 6 + 8 + 3 + 5 + 2$.

Tràn số ngầm

Biểu thức a[i] * i tới $10^8 \cdot 2 \cdot 10^5 = 2 \cdot 10^{13}$. Nếu a[i] và i đều là int thì phép nhân bị tràn trước khi cộng vào biến long long. Hãy để mảng kiểu long long.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    long long ans = 0;
    if (n <= 2000) {                                   // Cach 1
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                ans += max(llabs(x[i] - x[j]), llabs(y[i] - y[j]));
    } else {                                           // cung mot hang: chi con |dx|
        sort(x.begin(), x.end());
        long long pre = 0;                             // pre = x[0] + ... + x[i-1]
        for (int i = 0; i < n; i++) {
            ans += x[i] * i - pre;
            pre += x[i];
        }
    }
    cout << ans << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = [int(t) for t in data[1:1 + 2 * n:2]]
    y = [int(t) for t in data[2:2 + 2 * n:2]]
    ans = 0
    if n <= 2000:                                  # Cach 1
        for i in range(n):
            xi = x[i]; yi = y[i]
            for j in range(i + 1, n):
                dx = abs(xi - x[j]); dy = abs(yi - y[j])
                ans += dx if dx > dy else dy
    else:                                          # cung mot hang: chi con |dx|
        x.sort()
        pre = 0; i = 0                             # pre = x[0] + ... + x[i-1]
        for a in x:
            ans += a * i - pre
            pre += a; i += 1
    sys.stdout.write(str(ans) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N \log N)$

Cách 3Xoay 45 độ: biến max thành tổng – O(N log N) · 100%

Mấu chốt là đẳng thức sau, đúng với mọi số thực $a, b$:

$$\max(|a|, |b|) = \frac{|a + b| + |a - b|}{2}.$$

Chứng minh nhanh. Vai trò của $a, b$ như nhau và đổi dấu $a$ hay $b$ thì hai vế không đổi, nên giả sử $a \ge b \ge 0$. Khi đó $|a + b| + |a - b| = (a + b) + (a - b) = 2a = 2\max(|a|, |b|)$. ∎

Áp dụng với $a = x_i - x_j$, $b = y_i - y_j$ và đặt cho mỗi thửa

$$u = x + y, \qquad v = x - y,$$

thì $a + b = u_i - u_j$ và $a - b = v_i - v_j$, nên

$$d(i, j) = \frac{|u_i - u_j| + |v_i - v_j|}{2} \quad\Rightarrow\quad \text{Đáp án} = \frac{\sum |u_i - u_j| + \sum |v_i - v_j|}{2}.$$

Phép $\max$ đã biến thành tổng, tách được làm hai bài toán một chiều – mỗi bài giải bằng đúng Cách 2! (Hình học: đổi sang $(u, v)$ là xoay lưới đi $45°$ và phóng to; "hình vuông" khoảng cách Chebyshev biến thành "hình thoi" khoảng cách Manhattan.)

Hình 2. Tọa độ xoay của ví dụ. Kiểm tra cặp $(2, 4)$: $\frac{|2 - 6| + |0 - 2|}{2} = 3$ – đúng bằng $\max(3, 1)$.

Lưu ý $v = x - y$ có thể âm – không sao, sắp xếp và tổng tiền tố vẫn đúng. Tổng $\sum|u_i - u_j|$ không vượt quá $2 \cdot 10^{10} \cdot 2 \cdot 10^8 = 4 \cdot 10^{18}$, cộng thêm tổng của $v$ vẫn dưới giới hạn long long ($\approx 9{,}2 \cdot 10^{18}$). Tổng $\sum|u_i - u_j| + \sum|v_i - v_j|$ luôn chẵn (vì từng cặp đã cho $2 \cdot d(i, j)$) nên chia $2$ không mất gì.

Nhập thử các thửa ruộng để xem từng bước:

Các thửa x,y

Ví dụ nhanh:

Code hoàn chỉnh:

#include <bits/stdc++.h>
using namespace std;
// Tong |a_i - a_j| tren moi cap i < j (sap xep a roi dung tong tien to)
long long pairSum(vector<long long>& a) {
    sort(a.begin(), a.end());
    long long res = 0, pre = 0;               // pre = a[0] + ... + a[i-1]
    for (int i = 0; i < (int)a.size(); i++) {
        res += a[i] * i - pre;                // a[i] lon hon moi so dung truoc
        pre += a[i];
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> u(n), v(n);
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        u[i] = x + y;                         // xoay 45 do:
        v[i] = x - y;                         // max(|dx|,|dy|) = (|du| + |dv|) / 2
    }
    cout << (pairSum(u) + pairSum(v)) / 2 << "\n";
    return 0;
}

import sys


def pair_sum(a):
    # Tong |a_i - a_j| tren moi cap
    a.sort()
    res = 0; pre = 0; i = 0      # pre = a[0] + ... + a[i-1]
    for x in a:
        res += x * i - pre       # x lon hon moi so dung truoc
        pre += x; i += 1
    return res


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    u = [0] * n; v = [0] * n
    for i in range(n):
        x = int(data[1 + 2 * i]); y = int(data[2 + 2 * i])
        u[i] = x + y             # xoay 45 do:
        v[i] = x - y             # max(|dx|,|dy|) = (|du| + |dv|) / 2
    sys.stdout.write(str((pair_sum(u) + pair_sum(v)) // 2) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N \log N)$

C++▶ Chạy tay từng dòng codeTheo dõi tọa độ xoay u, v và tổng tiền tố trong hàm pairSum.

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

Dữ liệu mẫu:

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

2using namespace std;

3// Tong |a_i - a_j| tren moi cap i < j (sap xep a roi dung tong tien to)

4long long pairSum(vector<long long>& a) {

5 sort(a.begin(), a.end());

6 long long res = 0, pre = 0; // pre = a[0] + ... + a[i-1]

7 for (int i = 0; i < (int)a.size(); i++) {

8 res += a[i] * i - pre; // a[i] lon hon moi so dung truoc

9 pre += a[i];

10 }

11 return res;

12}

13int main() {

14 ios::sync_with_stdio(false); cin.tie(nullptr);

15 int n;

16 cin >> n;

17 vector<long long> u(n), v(n);

18 for (int i = 0; i < n; i++) {

19 long long x, y;

20 cin >> x >> y;

21 u[i] = x + y; // xoay 45 do:

22 v[i] = x - y; // max(|dx|,|dy|) = (|du| + |dv|) / 2

23 }

24 cout << (pairSum(u) + pairSum(v)) / 2 << "\n";

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 30 test: 10 test subtask 1 ($N \le 2000$), 9 test subtask 2 (mọi thửa cùng hàng, $N \approx 2 \cdot 10^5$), 11 test subtask 3 ($N \approx 2 \cdot 10^5$). Các test lớn có đủ kiểu phân bố: ngẫu nhiên, nhiều cụm, dải ngang mỏng, dải dọc mỏng, sát đường chéo chính, sát đường chéo phụ, dồn về các góc (đáp án gần $10^{18}$).

Cách làm	Sub 1 (20%)	Sub 2 (30%)	Sub 3 (50%)	Điểm
Cách 1 – duyệt mọi cặp	Đúng	TLE	TLE	20
Cách 2 – cùng hàng: sắp xếp + tiền tố	Đúng	Đúng	WA	50
Cách 3 – xoay 45°	Đúng	Đúng	Đúng	100
Sai 1 – $\max\left(\sum dx, \sum dy\right)$	5/10 test	Đúng	0/11 test	40
Sai 2 – tưởng drone không bay chéo: $\sum (dx + dy)$	1/10 test	Đúng	0/11 test	32
Sai 3 – xoay đúng nhưng dùng int (tích a[i] * i tràn)	4/10 test	0/9 test	0/11 test	8

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test còn lại; Cách 2 đúng hết hai subtask đầu và sai cả 11 test subtask 3; Cách 3 đúng 30/30 test, test lâu nhất chưa tới 0,1 giây. Hai công thức sai "tách tổng" đều ăn trọn subtask 2 (cùng hàng thì $dy = 0$) nhưng trượt toàn bộ subtask 3; lỗi tràn int gần như mất trắng vì chỉ đúng ở vài test nhỏ.

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 😇