Giải Cứu Đàn Gà (Codeforces 650A Watchmen)

Nguồn: Đề GV Vương Thành Trung · Codeforces 650A Độ khó: Trung bình Toán học Nhận xét Map Đếm

Đề bài

Bài 2. Giải cứu đàn gà (GV ra đề: Vương Thành Trung) · Thời gian: 1 giây/test

Đàn gà con đang gặp nguy hiểm trước sự tấn công của lũ quạ, Bờm và Cuội phải tìm cách giải cứu chúng ngay lập tức. Có tổng cộng $N$ con gà đang đứng nháo nhác trên một hệ trục tọa độ Descartes $Oxy$, con gà thứ $i$ đang đứng ở vị trí tọa độ $(x_i, y_i)$.

Bờm và Cuội cần có một kế hoạch giải cứu, nhưng những con gà thì lại gặp khó khăn trong quá trình di chuyển của chúng, vì vậy chúng cần phải theo sự hướng dẫn của Bờm và Cuội. Tuy nhiên, Bờm và Cuội lại không thống nhất được cách di chuyển của những con gà của mình: theo Bờm, nếu hai con gà ở vị trí $(x_i, y_i)$ và vị trí $(x_j, y_j)$ thì khoảng cách của chúng sẽ là $|x_i - x_j| + |y_i - y_j|$, còn theo Cuội thì khoảng cách giữa chúng là $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$.

Sự thành công của cuộc giải cứu phụ thuộc vào số cặp $(i, j)$ $(1 \le i, j \le N)$ sao cho khoảng cách giữa con gà thứ $i$ và con gà thứ $j$ tính theo cách của Bờm bằng với khoảng cách tính theo cách của Cuội. Bạn hãy đếm số lượng cặp gà như vậy.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $N$.
• $N$ dòng tiếp theo, mỗi dòng thứ $i$ chứa hai số nguyên $x_i, y_i$ $(|x_i|, |y_i| \le 10^9)$ là tọa độ của con gà thứ $i$.

Kết quả ra: Số lượng cặp gà thỏa mãn khoảng cách giữa chúng theo cách tính của Bờm bằng khoảng cách theo cách tính của Cuội.

Giới hạn: $2 \le N \le 10^6$; $|x_i|, |y_i| \le 10^9$.

Ràng buộc:

• Subtask 1: 50% số test đầu tiên $N \le 500$;
• Subtask 2: 30% số test tiếp theo $N \le 100\,000$;
• Subtask 3: 20% số test cuối cùng không có ràng buộc gì thêm.

Ví dụ 1 – input

3
1 1
7 5
1 5

Output: 2

Ví dụ 2 – input

6
0 0
0 1
0 2
-1 1
0 1
1 1

Output: 11

Giải thích ví dụ 1: Có 2 cặp gà thỏa mãn yêu cầu là $(1, 1)$ và $(1, 5)$; $(7, 5)$ và $(1, 5)$.

Lời mở đầu

Bài này mình được một em học viên hỏi "a ơi bài 2 làm như nào để full test v ạ" và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen 😇.

Lúc đăng bài mình chưa biết bài này có trên trang nào để nộp. Sau này thì thấy đề này giống hệt bài Watchmen (Codeforces 650A) – trùng luôn cả 2 ví dụ, chỉ khác là bên Codeforces $n \le 2 \cdot 10^5$. Các bạn có thể nộp ở đó để kiểm tra code:

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ưu ý nhỏ về cách hiểu đề: tuy đề ghi $1 \le i, j \le N$ nhưng qua ví dụ thì ta thấy cặp $(i, j)$ và $(j, i)$ chỉ tính 1 lần, và cũng không tính cặp con gà với chính nó (tức là đếm các cặp $i \lt j$). Ví dụ 1 có 3 con gà $A(1, 1)$, $B(7, 5)$, $C(1, 5)$:

Cặp	Bờm: $|dx| + |dy|$	Cuội: $\sqrt{dx^2 + dy^2}$	Bằng nhau?
A, B	6 + 4 = 10	$\sqrt{36 + 16} = \sqrt{52} \approx 7.21$	Không
A, C	0 + 4 = 4	$\sqrt{0 + 16} = 4$	Có
B, C	6 + 0 = 6	$\sqrt{36 + 0} = 6$	Có

⇒ đáp án 2. Ở ví dụ 2 có 2 con gà đứng trùng chỗ nhau tại $(0, 1)$ – khoảng cách giữa chúng theo cả 2 cách đều là 0 nên cặp này cũng được đếm. Chi tiết này sẽ rất quan trọng ở Cách 2.

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

Cách 1Biến đổi công thức + duyệt mọi cặp O(N²) – subtask 1Cách 2Đếm bằng map O(N·logN)Cách 3Sắp xếp rồi đếm theo nhóm – chạy nhanh hơn với N = 10^6

Cách 1Biến đổi toán học rồi duyệt mọi cặp – O(N²)

Bài này biến đổi toán học 1 chút là nhìn ra bản chất vấn đề thôi các bạn. Ta cần cặp $(i, j)$ thỏa:

|x_i − x_j| + |y_i − y_j| = √((x_i − x_j)² + (y_i − y_j)²)

Hai vế đều không âm nên ta bình phương 2 vế lên:

• Vế trái là $(|x_i - x_j| + |y_i - y_j|)^2$, dùng hằng đẳng thức $(A + B)^2 = A^2 + 2AB + B^2$ khai triển ra được $|x_i - x_j|^2 + 2 \cdot |x_i - x_j| \cdot |y_i - y_j| + |y_i - y_j|^2$. Khi lũy thừa 2 thì bảo đảm luôn là số không âm rồi nên $|x_i - x_j|^2$ không cần trị tuyệt đối nữa, viết thành $(x_i - x_j)^2$ là được, tương tự với $y$. Vậy vế trái là $(x_i - x_j)^2 + 2 \cdot |x_i - x_j| \cdot |y_i - y_j| + (y_i - y_j)^2$.
• Vế phải bình phương lên thì triệt tiêu căn bậc 2, còn lại $(x_i - x_j)^2 + (y_i - y_j)^2$.

Cả 2 vế đều có $(x_i - x_j)^2 + (y_i - y_j)^2$ nên ta bỏ đi, phương trình chỉ còn:

2·|x_i − x_j|·|y_i − y_j| = 0  ⇔  |x_i − x_j|·|y_i − y_j| = 0

Khi $A \cdot B = 0$ thì hoặc $A = 0$ hoặc $B = 0$, nghĩa là $|x_i - x_j| = 0$ hoặc $|y_i - y_j| = 0$.

Bản chất của bài

Cặp gà $(i, j)$ thỏa mãn ⇔ $x_i = x_j$ hoặc $y_i = y_j$ – tức là 2 con gà nằm trên cùng một đường thẳng đứng hoặc cùng một đường nằm ngang. Đề bài lúc này chỉ là: đếm xem có bao nhiêu cặp điểm có hoành độ hay tung độ trùng nhau. Nhìn hình chữ nhật có đường chéo là đoạn nối 2 con gà thì cũng thấy ngay: đi theo 2 cạnh góc vuông (Bờm) luôn dài hơn đi theo đường chéo (Cuội), trừ khi hình chữ nhật bị "dẹp" thành một đoạn thẳng.

Từ đây cách đơn giản nhất là duyệt mọi cặp $i \lt j$ và kiểm tra điều kiện trên. Cách này không phải tính căn bậc 2 nên không lo sai số số thực (nếu làm đúng y công thức của đề với sqrt thì dễ gặp sai số khi số lớn).

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;

int main(){
    int n;
    cin >> n;
    vector<pair<long long, long long>> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
    long long res = 0;
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            if(a[i].first == a[j].first || a[i].second == a[j].second){
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    x = [int(v) for v in data[1:2 * n + 1:2]]
    y = [int(v) for v in data[2:2 * n + 2:2]]
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if x[i] == x[j] or y[i] == y[j]:
                res += 1
    print(res)

main()

Chỉ qua được subtask 1

Số cặp phải xét là $\frac{N(N-1)}{2}$. Với $N = 500$ thì chỉ khoảng $1.25 \cdot 10^5$ cặp, chạy tức thì; nhưng với $N = 10^5$ đã là $5 \cdot 10^9$ cặp và $N = 10^6$ là $5 \cdot 10^{11}$ cặp – TLE chắc luôn. Code này chủ yếu để hiểu đề và làm code đối chiếu.

Không gian$O(N)$

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

Cách 2Đếm bằng map – O(N·logN)

Đã biết chỉ cần đếm cặp cùng hoành độ hoặc cùng tung độ thì ta không cần ghép từng cặp nữa. Duyệt các con gà lần lượt, khi đến con gà thứ $i$ ta đếm xem trong các con gà đứng trước nó có bao nhiêu con ghép với nó được:

• mp1[x] = số con gà đã gặp có hoành độ bằng x;
• mp2[y] = số con gà đã gặp có tung độ bằng y;
• mp3[(x, y)] = số con gà đã gặp đứng đúng tại điểm (x, y).

Nhưng hãy lưu ý chỗ này là mỗi cặp chỉ được tính 1 lần thôi nhé. Ví dụ khi xét hoành độ ta có $x_A = x_B$ thì cặp $A, B$ đã được tính là 1 cặp thỏa. Nếu xét tiếp tung độ mà giả sử $y_A$ cũng bằng $y_B$ (tức là A và B đứng trùng chỗ) thì không được cộng thêm 1 vào đáp án nữa, vì cặp này đã đếm trước đó rồi. Những cặp như vậy chính là những cặp bị đếm 2 lần trong mp1 và mp2, nên ta trừ bớt đi số lượng đó bằng mp3 (nguyên lý bù trừ):

Công thức

Khi xét con gà $(x, y)$: res += mp1[x] + mp2[y] - mp3[(x, y)], sau đó mới tăng mp1[x], mp2[y], mp3[(x, y)] lên 1 (để con gà này không tự ghép cặp với chính nó).

Các bạn nhập tọa độ các con gà (mỗi con 2 số, để dễ vẽ thì $|x|, |y| \le 6$) rồi bấm Tiếp để xem từng con gà được thêm vào: điểm vàng là con đang xét, điểm xanh là các con đứng trước ghép cặp được với nó.

Tọa độ (x y 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;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<long long, long long>> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;
    long long res = 0;
    map<long long, long long> mp1, mp2;
    map<pair<long long, long long>, long long> mp3;
    for(int i = 0; i < n; ++i){
        res += mp1[a[i].first] + mp2[a[i].second] - mp3[a[i]];
        mp1[a[i].first]++;
        mp2[a[i].second]++;
        mp3[a[i]]++;
    }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    mp1, mp2, mp3 = {}, {}, {}
    res = 0
    for i in range(n):
        x = int(data[2 * i + 1])
        y = int(data[2 * i + 2])
        p = (x, y)
        res += mp1.get(x, 0) + mp2.get(y, 0) - mp3.get(p, 0)
        mp1[x] = mp1.get(x, 0) + 1
        mp2[y] = mp2.get(y, 0) + 1
        mp3[p] = mp3.get(p, 0) + 1
    print(res)

main()

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

1. Code gốc của mình duyệt i từ $n - 1$ về $0$, ở đây mình cho duyệt xuôi cho dễ theo dõi – chiều nào cũng ra kết quả như nhau vì mỗi cặp vẫn chỉ được đếm đúng 1 lần (lúc gặp con gà đứng sau trong cặp).
2. Phải cộng vào res trước rồi mới tăng 3 map. Làm ngược lại thì con gà sẽ tự ghép cặp với chính nó.
3. res phải là long long: nếu cả $10^6$ con gà cùng hoành độ thì có tới $\frac{10^6 \cdot (10^6 - 1)}{2} \approx 5 \cdot 10^{11}$ cặp, vượt xa int.
4. mp3 dùng khóa là pair (C++) / tuple (Python) để nhận biết các con gà đứng trùng chỗ.

Quên trừ mp3 là sai ở test có điểm trùng

Ví dụ 2 chính là cái bẫy: nếu chỉ lấy mp1[x] + mp2[y] thì cặp 2 con gà cùng đứng ở $(0, 1)$ bị đếm 2 lần và in ra 12 thay vì 11.

Khung chạy tay (để dễ theo dõi, giới hạn $N \le 15$):

C++▶ Chạy tay từng dòng codeCách 2: duyệt từng con gà, cộng số con đứng trước cùng x hoặc cùng y (trừ đi số con trùng chỗ).

Dữ liệu vào (stdin) – sửa thoải mái6 0 0 0 1 0 2 -1 1 0 1 1 1

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

7 int n;

8 cin >> n;

9 vector<pair<long long, long long>> a(n);

10 for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;

11 long long res = 0;

12 map<long long, long long> mp1, mp2;

13 map<pair<long long, long long>, long long> mp3;

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

15 res += mp1[a[i].first] + mp2[a[i].second] - mp3[a[i]];

16 mp1[a[i].first]++;

17 mp2[a[i].second]++;

18 mp3[a[i]]++;

19 }

20 cout << res;

21 return 0;

22}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng tọa độ và 3 map, mỗi map tối đa $N$ khóa – $O(N)$.
• Thời gian: mỗi con gà làm vài thao tác trên map, mỗi thao tác $O(\log N)$ ⇒ $O(N \log N)$.

Không gian$O(N)$

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

Muốn nhanh hơn nữa

Nếu dùng unordered_map (bảng băm) thay cho map thì độ phức tạp trung bình là $O(N)$. Với unordered_map có khóa là pair thì C++ chưa có sẵn hàm băm, các bạn có thể gộp 2 tọa độ thành một số long long, ví dụ (x + 10^9) * (2 * 10^9 + 1) + (y + 10^9), rồi dùng số đó làm khóa.

Cách 3Sắp xếp rồi đếm theo nhóm – O(N·logN), nhanh hơn map

Cách 2 đúng về độ phức tạp, nhưng map của C++ là cây nhị phân, mỗi lần truy cập phải nhảy qua nhiều nút nằm rải rác trong bộ nhớ nên hằng số khá lớn. Với $N = 10^6$ và tọa độ ngẫu nhiên, mình đo thử thì code Cách 2 (C++) chạy mất mấy giây – hơi nguy hiểm với giới hạn 1 giây của subtask 3. Ta có thể đếm cùng một đại lượng mà không cần map:

• Nếu có $k$ con gà cùng hoành độ thì chúng tạo ra $\frac{k(k-1)}{2}$ cặp cùng $x$. Gọi tổng các số này trên mọi nhóm hoành độ là $S_x$; tương tự có $S_y$ cho tung độ.
• Gọi $S_{xy}$ là số cặp con gà đứng trùng chỗ (cùng cả $x$ lẫn $y$) – những cặp này bị đếm ở cả $S_x$ và $S_y$.

Công thức bù trừ

Đáp án $= S_x + S_y - S_{xy}$. Muốn đếm số phần tử trong từng nhóm giá trị bằng nhau thì chỉ cần sắp xếp mảng, các giá trị bằng nhau sẽ đứng liền nhau.

Để sắp xếp được các điểm như một số nguyên, mình gộp $(x, y)$ thành một số long long: $(x + 10^9) \cdot (2 \cdot 10^9 + 1) + (y + 10^9)$. Vì $0 \le y + 10^9 \le 2 \cdot 10^9$ nên hai điểm khác nhau luôn cho hai số khác nhau, và số lớn nhất chỉ khoảng $4 \cdot 10^{18}$ – vẫn vừa long long. Kiểm tra lại với ví dụ 2: hoành độ $\{0, 0, 0, -1, 0, 1\}$ có nhóm 4 số 0 ⇒ $S_x = 6$; tung độ $\{0, 1, 2, 1, 1, 1\}$ có nhóm 4 số 1 ⇒ $S_y = 6$; điểm $(0, 1)$ xuất hiện 2 lần ⇒ $S_{xy} = 1$; đáp án $6 + 6 - 1 = 11$ ✔.

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;

long long countPairs(vector<long long> &v){
    sort(v.begin(), v.end());
    long long res = 0, cnt = 1;
    for(int i = 1; i < (int)v.size(); ++i){
        if(v[i] == v[i - 1]) cnt++;
        else{
            res += cnt * (cnt - 1) / 2;
            cnt = 1;
        }
    }
    res += cnt * (cnt - 1) / 2;
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<long long> xs(n), ys(n), ps(n);
    for(int i = 0; i < n; ++i){
        long long x, y;
        cin >> x >> y;
        xs[i] = x;
        ys[i] = y;
        ps[i] = (x + 1000000000) * 2000000001LL + (y + 1000000000);
    }
    cout << countPairs(xs) + countPairs(ys) - countPairs(ps);
    return 0;
}

import sys

def count_pairs(v):
    v.sort()
    res = 0
    cnt = 1
    for i in range(1, len(v)):
        if v[i] == v[i - 1]:
            cnt += 1
        else:
            res += cnt * (cnt - 1) // 2
            cnt = 1
    res += cnt * (cnt - 1) // 2
    return res

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    xs = list(map(int, data[1:2 * n + 1:2]))
    ys = list(map(int, data[2:2 * n + 2:2]))
    ps = [(x + 1000000000) * 2000000001 + (y + 1000000000) for x, y in zip(xs, ys)]
    print(count_pairs(xs) + count_pairs(ys) - count_pairs(ps))

main()

Không gian$O(N)$

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

Ghi chú của mình: Code C++ và Python của cả 3 cách đã được kiểm tra với 700 bộ test ngẫu nhiên ($N \le 60$, tọa độ nhỏ để có nhiều điểm trùng hoành độ/tung độ/trùng chỗ, xen lẫn tọa độ tới $10^9$), so với code vét cạn tính đúng y công thức của đề bằng số nguyên (so sánh bình phương 2 vế) – khớp hết; 2 test của đề in ra 2 và 11. Với $N = 10^6$ tọa độ ngẫu nhiên, trên máy mình thử: Cách 2 C++ mất khoảng 5–6 giây CPU (với $N = 2 \cdot 10^5$ như Codeforces thì khoảng 0.85 giây), Python khoảng 2 giây; Cách 3 C++ chỉ khoảng 0.4 giây, Python khoảng 2.7 giây. Nên muốn chắc ăn subtask 3 với giới hạn 1 giây thì các bạn dùng Cách 3 bằng C++ 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 😇