Bình luận

• 
  

  0

  

  tri_88  đã bình luận lúc 26, Tháng 12, 2023, 3:08

  Code C++ (Task C) AC tại đây

• 
  

  1

  

  khiemkrkt  đã bình luận lúc 13, Tháng 12, 2023, 14:51

  Editorial - Task C:

  Trâu bò:

  Với mỗi truy vấn, ta đơn thuần chạy từng cặp và tính tổng của chúng

  Độ phức tạp: ~O(Q*N^2)~

  Tối ưu 1:

  Với mỗi ~j~ ta cần tính tổng:

  ~A_l*A_j + A_{l+1}*A_j + A_{l+2}*A_j + ... + A_{j-1}*A_j~

  ~=A_j*(A_l+A_{l+1}+...+A{j-1})~

  Xây dựng mảng cộng dồn (prefixsum) để tính nhanh ~(A_l+A_{l+1}+...+A{j-1})~

  Độ phức tạp tiền xử lý: ~O(N)~

  Độ phức tạp khi truy vấn: ~O(N)~

  Code mẫu: https://ideone.com/FBoCGY

  Một số bạn cài đặt như sau bị TLE, bạn có thể tham khảo video sau để tìm lí do:

  https://www.youtube.com/watch?v=mmAf5lgZuTI

  Tối ưu 2:

  Khởi tạo ~px_i~ là tổng các các cặp ~A_l*A_r~ với ~1 \le l \le r \le i~

  Nếu lấy ~px_r - px_{l-1}~ ta sẽ được tổng các cặp ~A_i*A_j~ với ~1 \le i \le j~ và ~l \le r \le n~

  Thì cần trừ đi phần dư là tổng các cặp ~A_i*A_j~ với ~1 \le i < l~ và ~l \le r \le n~, có thể rút gọn lại: ~(A_1+A_2+...+A_{l-1}) * (A_l+A_{l+1}+...+A_r)~, ta có thể dễ dàng tính nhanh phần này bằng prefixsum

  Độ phức tạp tiền xử lý: ~O(N)~

  Độ phức tạp khi truy vấn: ~O(1)~

  Code mẫu: https://ideone.com/RUpH1X

  Cách tối ưu từ trâu bò trên được mình nghĩ ra trong lúc làm bài, có gì khó hiểu thì các bạn góp ý nhé. 🧠

• 
  

  -6

  

  _SUGAR__DADDY_  đã bình luận lúc 26, Tháng 11, 2023, 16:11

  xin downvote

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  5

  

  Khanhll123  đã bình luận lúc 26, Tháng 11, 2023, 16:03

  chưa có rate lun =)))

• 
  

  0

  

  tqtien200540  đã bình luận lúc 26, Tháng 11, 2023, 10:22

  Thank you very much <3