Tối ưu thuật toán cho bài khoảng cách tập điểm

[BORT_Ddoox (Đỗ Quốc Ân)]

Nhờ các cao nhân tối ưa thuật toán cho bài này ạ:

Còn đây là thuật toán của em:

Thuận toán cùi mía của em tuy đúng nhưng khi nạp bài thì bị vượt quá timelimit, nhờ các bác chỉ giáo, cải thiện hơn ạ.

Link cho bác nào test ạ T_T : http://oj.hueuni.edu.vn/practice/problem/692/submission

[SITUVN.gcd]

@BORT_Ddoox

link cho bác nào test T_T :
http://oj.hueuni.edu.vn/practice/problem/692/submission

Bạn nên đưa lên các trang công cộng, trang bạn đưa chỉ dành cho sinh viên trường của bạn có tài khoản.
Codepad, Ideone, OnlineGdb, Replit,…

[kisuluoibieng (Tên Gì Cũng Được)]

Comment đánh dấu lại, sáng sẽ gợi ý cho bạn giải với O(n)

[BORT_Ddoox (Đỗ Quốc Ân)]

Cái này tạo đại 1 cái tài khoản cũng đc á ._.

[rogp10]

Hằng đẳng thức đáng nhớ thôi mà

Xét tổng

S_i = \sum^{i}_{j=1} (x_i-x_j)^2\\ = \sum^{i}_{j=1}(x_i^2 + x_j^2-2x_ix_j)

Do i không phải biến chạy nên kéo ra thành

S_i = i\cdot x_i^2 + \sum x^2_j - 2x_i\sum x_j\\

\sum x^2_j và \sum x_j chỉ cần cộng dồn ở mỗi bước lặp i.

[kisuluoibieng (Tên Gì Cũng Được)]

Tổng bình phương tất cả các cạnh (là đoạn thẳng nối 2 điểm)

ở đây gọi là điểm 1…n

Xét tất cả đoạn thẳng xuất phát từ điểm 1 gồm: 1-2, 1-3, …, 1-n

Tổng bình phương các cạnh có xuất phát điểm là đỉnh 1:

0 + (x_2-x_1)^2+ (x_3-x_1)^2 + .. + (x_n-x_1)^2\\ +\\ 0 + (y_2-y_1)^2 + (y_3-y_1)^2 + .. + (y_n-y_1)^2\\ = X + Y

Xét cụm X ở cụm trên trước

X = x_1^2 - 2*x_1*x_1 + x_1^2 + x_2^2 - 2*x_1*x_2 + x_1^2 + x_3^2 - 2*x_1*x_3 + x_1^2 + .. + x_n^2 - 2*x_1*x_n + x_1^2\\ = (x_1^2 + x_2^2 + x_3^2 + ... + x_n^2) - 2*x_1*(x_1 + x_2 + x_3 + .. x_n) + n*x_1^2

Tổng x và tổng bình phương của x có thể duyệt mảng và tính trước 1 lần duy nhất với O(n). Như vậy khi tính X chỉ tốn O(1)

Tương tự với Y ở cụm dưới

…

Lần lượt xét tất cả các điểm còn lại làm điểm xuất phát (cứ cho nó trùng luôn 1-2 2-1 luôn). Sau khi cộng xong thì chia 2 vì đã giải thích như trong ngoặc.

Tiếc là editor này hình như không có text color nên nếu khó hiểu thì xem text có màu này cho đễ

[rogp10]

Dòng trên là dấu trừ sao dòng dưới thành dấu cộng rồi

Gom các X lại một lần thành tổng \frac{1}{2} (n\sum x_i^2 - 2(\sum x_i)^2 + n\sum x_i)

[tntxtnt]

bỏ vô $\color{red}…$ là nó có thêm màu đỏ á
\color{red}x_1^2 - 2x_1x_2 + x_2^2\color{black}+\color{green}x_1^2 - 2x_1x_3 + x_3^2\color{black}

$\color{red}x_1^2 - 2x_1x_2 + x_2^2\color{black}+\color{green}x_1^2 - 2x_1x_3 + x_3^2\color{black}$

[kisuluoibieng (Tên Gì Cũng Được)]

tool editor không có nên có vẻ phức tạp, mình lại hơi lười

[rogp10]

GUI làm gì cho nhì nhằng à mà đây:
https://www.guru99.com/best-latex-editors-window-mac.html

MathTeX Editor Professional