Tối ưu thuật toán cho bài toán O(n^2) thành O(n)

#1

Đề bài toán: Cho N tọa độ điểm trên mặt phẳng Oxy. Hãy lập trình tính tổng bình phương khoảng cách giữa tất cả các cặp điểm.
Input

  • Dòng đầu tiên chứa số nguyên dương N là số điểm trên mặt phẳng thỏa 1 ≤N≤10^5
  • N dòng tiếp theo, mỗi dòng chứa hai số nguyên X, Y là tọa độ của mỗi điểm thỏa −10^4≤X, Y≤10^4
    Có thể có các tọa độ trùng nhau.

Output
In ra số cần tính.

Bài code của em:

#include<iostream>
using namespace std;
int main(){
long long n;
int arr[100000][2];
cin>>n;
for(long i=0;i<n;i++){
    for(int j=0; j<2;j++){
        cin>>arr[i][j];
        }
    }
long long tongkc=0;

for(long t=0; t<(n-1) ; t++){
            long long kc1;
        for(long j=t+1; j<n ;j++){
kc1=(arr[j][0]-arr[t][0])*(arr[j][0]-arr[t][0])+(arr[j][1]-arr[t][1])*(arr[j][1]-arr[t][1]);
         tongkc+=kc1;
            }
        }
cout<<tongkc;
return 0;
}

Khi nộp bài vào hệ thống thì đúng với 9/10 testcase. Case thứ 10 bị out time limit (time limit 1000ms). Trong khi em chạy case đấy hết 3960 ms. Em có tìm trên mạng nhưng vẫn k biết cách tối ưu. Mong mọi người có thể gợi ý cho em cách tối ưu hoặc tài liệu để nghiên cứu bài này ạ. Em xin cảm ơn mọi người nhiều ạ.

#2

Dùng đại số nào :smiley:

S = \frac{1}{2}\sum_{1 \leq i,j<n}(x_i-x_j)^2 + (y_i-y_j)^2

Xét riêng tung và hoành độ, ta gom các hạng tử đồng dạng :slight_smile:

9 Likes
#3

dạ em mới năm 1 nên cũng chưa hiểu cách ấy lắm . Em có tìm ra 1 bài viết TA sử dụng thuật toán như anh nói.


với là em đang lo là nếu tách riêng x và y thì có ảnh hưởng đến input k ạ vì hệ thống bắt nhập từng hàng là x y của 1 điểm. Mong anh hồi đáp ạ, em cảm ơn anh nhiều.

#4

Bạn có chắc là có cách tối ưu về O(n) không ? Với bài này tối ưu 3960ms về 1000ms thì ko cần tối ưu về O(n) mới làm được và cá nhân mình thấy là không thể. Như bác bên trên đã nói, hãy gom những phần tử chung lại nhằm giảm thiểu số bước thực hiện với độ phức tạp O(n^2) (Tách tổng giữa các bình phương x^2, y^2 và tích 2xixj, 2yiyj). Tách riêng 2 mảng x, y TH này không sao bạn nhé thậm chí còn an toàn về lỗi tràn bộ nhớ và clean hơn

4 Likes
#5

dạ tại em đọc bài này


Người ta chuyển được mà nó lằng nhằng với khó hiểu quá nên em không tiếp thu được.
Cách của anh em thấy cũng giống bài này phải không ạ. Em dốt quá nên đọc mãi k hiểu ạ @@, em chưa học tới vector ạ.
Em cảm ơn anh nhiều lắm ạ

2 Likes
#6

Em cảm ơn các anh rất nhiều ạ, để em cố gắng làm theo hướng các anh đã gợi ý xem thử ạ.

#7

Cảm ơn bạn đã shared link giúp mình học hỏi thêm, bạn cố gắng đọc hiểu hoặc dựa vào từ khóa tìm thêm nguồn xem sao

2 Likes
#8

dạ em cảm ơn anh nhiều lắm ạ, để em cố gắng load hết đống này. Chúc anh ngày mới vui vẻ ạ.

1 Like
#9

Tập trung vào thuật toán đã, rồi bạn tham khảo code sau.

Đúng vậy, trình bày khác thôi.

Mỗi bình phương hoành/tung độ sẽ xuất hiện n lần, vì ta tính khoảng cách 1 điểm với n điểm còn lại. Tương tự phần 2x_ix_j có thể đặt thành nhân tử chung.

3 Likes
#10

chuyển n trong O(n^2) từ 10^5 xuống còn 2x10^4 là được :V :V :V

1 ≤N≤10^5
10^4≤X, Y≤10^4

cũng là O(n^2) nhưng 4e8 < 1e10, 1 giây dư sức.

3 Likes
#11

em vẫn chưa hiểu ý anh lắm ạ, anh có thể giải thích kĩ hơn về cách làm này được không ạ. Em cảm ơn anh ạ

#12

dạ em cảm ơn sự giúp đỡ của anh nhiều lắm ạ, em đang cố gắng hiểu thuật toán này ạ. Chúc anh ngày vui vẻ ạ

#13

Kiến thức này là lớp 8 rồi bạn. Đừng sợ!
Nếu bạn cảm thấy mấy công thức trên nhìn quá khó hiểu thì bạn có thể tự giải bài toán bằng cách giảm từ n điểm xuống còn 3 điểm. Lần lượt có: A(x_1, y_1) ;B(x_2, y_2); C(x_3, y_3)
Tổng Bình phương khoảng cách:

|AB|^2 + |AC|^2 + |BC|^2
= [(x_1-x_2)^2+ (y_1-y_2)^2] + [(x_1-x_3)^2 + (y_1-y_3)^2] + [(x_2-x_3)^2 + (y_2-y_3)^2]
Gom các hạng tử x và y về một bên
= [ (x_1-x_2)^2+ (x_1-x_3)^2 + (x_2-x_3)^2 ]+ [(y_1-y_2)^2 + (y_1-y_3)^2 + (y_2-y_3)^2 ]

Tới đây thì bạn thực hiện toán cấp 2 thôi
= 2(x_1^2 +x_2^2 + x_3^2) - 2(x_1x_2 +x_1x_3 +x_2x_3 ) + 2(y_1^2 +y_2^2 + y_3^2) - 2(y_1y_2 +y_1y_3 +y_2y_3 )

Nhìn ra quy luật 3 số rồi tự động chuyển qua n số.
Nhìn không ra nữa thì viết 4 điểm ra. So sánh với 3 điểm coi khác nhau sao.

3 Likes
#14

ví dụ N=10, -2 <= x, y <= 2
chia làm 2 mảng X và Y:

X = [1, -2, 2, 2,  2, -1, 0, -2, 1, 0]
Y = [2,  0, 2, 2, -1,  0, 1, -2, 2, 1]

gom mảng X, Y lại từ 10 số còn 5 số:

     -2  -1   0   1   2
X' = [2,  1,  2,  2,  3]
Y' = [1,  1,  2,  2,  4]

tính tổng bình phương hiệu các số trong X’, tốn ~5^2 thay vì 10^2 :V

4 Likes
#15

Thớt mà ko tìm cách ánh xạ lại lấy tần suất cho nhanh thì cũng vậy :smiley:

Mà lấy tần suất còn khó hiểu hơn là khai triển công thức kia.

4 Likes
#16

công thức là toán rồi, xài cách này mới là lập trình :smiling_face_with_three_hearts:

à công thức toán cũng nhân x_i x_j cũng là O(n^2), vẫn phải gom phần tử lại thôi :V

4 Likes
#17

Nhưng mà gom theo tần suất nó lại khác với đặt nhân tử chung :smiley:

Mà thớt muốn O(n) kìa.

5 Likes
#18

Bài này có thể giải trong O(n) được mà:

A = 2 * \sum_{1<i<j<n}(x_i * x_j) = (\sum x_i)^2 - \sum x_i^2 \\ \sum_{1<i<j<n}(x_i-x_j)^2 = \sum(x_i^2) * (n-1) - A
5 Likes
#19

^ tính A là từ công thức nào vậy nhi?

1 Like
#20

Bài này thật sự quá sức đối với em rồi các anh/chị ạ. Em đọc code mãi vẫn k hiểu công thức và cũng k hiểu tại sao chuyển được hết ạ.

#include<iostream>
using namespace std;
int main()
{
int T;
long a[100000],b[100000];
long ar[100000],br[100000];
long arr[100000],brr[100000];
cin>>T;
for (int i=1; i<=T ; i++){
cin>>a[i]>>b[i];}
for (int i=1; i<=T ; i++){
ar[i]=ar[i-1]+a[i];
br[i]=br[i-1]+b[i];
arr[i]=arr[i-1]+a[i]*a[i];
brr[i]=brr[i-1]+b[i]*b[i];
}
long long hdx =0;
long long hdy=0;

for (int i=1; i<=T ; i++){
     hdx+=(i-1)*a[i]*a[i]+arr[i-1]-2*a[i]*ar[i-1];
     hdy+=(i-1)*b[i]*b[i]+brr[i-1]-2*b[i]*br[i-1];}
     long long tong=hdx+hdy;
     cout<<tong;
return 0;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?