8

LCOJ Regular Contest #1

wronganswer posted on Nov. 26, 2023, 7:05 a.m.

Xin chào các bạn, blog này thông báo rằng LCOJ sẽ tiếp tục tổ chức LCOJ Regular Contest #1.

LCOJ Regular Contest #1 sẽ diễn ra vào 20h00 ngày 26/11/2023 với thời lượng kéo dài 2 giờ 30 phút (vì một số lý do liên quan trong khâu duyệt bài nên kỳ thi sẽ kéo dài thêm 30 phút đến 23h00 ngày 26/11/2023).

Tổ chức kỳ thi
Thông tin kỳ thi
  • Sử dụng format ICPC.
  • Kỳ thi gồm 6 task làm trong thời gian 2 giờ 30 phút.

UPD: Sau khi contest kết thúc các bạn hoàn toán có thể đóng góp editorial cho các bài tập trong contest bằng cách comment editorial của các bạn xuống dưới bài post này với tiêu đề "Editorial - Task ...". Nếu editorial của các bạn nhận được sự ủng hộ của mọi người, lời giải của các bạn sẽ được cân nhắc để được đưa làm lời giải chính thức cùng với lời giải đến từ LCOJ ! Rất mong được cùng các bạn đóng góp lời giải cho LCOJ!

Comments

Please read the guidelines before commenting.


  • -1
    tri_88  commented on Dec. 26, 2023, 3:08 a.m.

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


  • 0
    khiemkrkt  commented on Dec. 13, 2023, 2:51 p.m.

    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é. 🧠


  • 4
    Khanhll123  commented on Nov. 26, 2023, 4:03 p.m.

    chưa có rate lun =)))


  • -1
    tqtien200540  commented on Nov. 26, 2023, 10:22 a.m.

    Thank you very much <3