Thuật toán tối ưu cho bài toán đếm

[Huynh_Minh_Tuan (JustTee_Phương Ly)]

Bài này em giải với T(n^3), chắc chắn là quá thời gian . Mong các anh/ chị giúp em để có 1 thuật toán tối ưu … Em cảm ơn

[noname00 (HK boy)]

log(n^3) là 3log(n) rồi còn gì nữa TLE thế [spoiler]*éo[/spoiler] nào được

Lấy bất kì 2 thanh gỗ từ 2 bộ đầu tiên, rồi kiểm tra xem thanh gỗ còn lại có số đo bao nhiêu. Kiểm tra xem trong bộ thứ 3 có thanh gỗ nào có chiều dài như vậy không.

Độ phức tạp O(n^2 log n).

[Phong_Ky_Vo (Tao Không Ngu.)]

Hi JustTee_Phương Ly.
Bạn có thể xắp xếp một loại sau đó dùng tìm kiếm nhị phân để giản thời gian tim thanh gỗ thứ 3.

[rogp10]

Thực ra chỉ cần theta(n^2) thôi sắp xếp cả 3 mảng xong rồi giữ a, chọn b, dịch cửa sổ trong c. Tương tự cho hai lượt còn lại.