Chiến thần thiết kế thuật toán (luyện tập lần 1)

Lần luyện tập \(1\) bao gồm các vấn đề cơ bản và mở rộng áp dụng các kĩ thuật trong quy hoạch động, chia để trị:

  • Tìm kiếm nhị phân - Binary search.
  • Min, max tiền tố, hậu tố - Prefix, suffix min, max.
  • Tổng tiền tố, hậu tố (cộng cuốn chiếu, cộng dồn) - prefix, suffix sum.
  • Tìm kiếm tam phân - Ternary search trong hình học.

Chủ đề mở rộng:

  • Giải thuật leo đồi - Hill climbing search trong hình học.

Các vấn đề đều có thể giải bằng ngôn ngữ C.

Hướng dẫn giải (editorial) cho một số bài sẽ được cập nhật sau khi kì thi kết thúc.

Link luyện tập lần 2

Link luyện tập lần 3

Problems

Problem Points AC Rate Users
Top 3 2p 16.1% 114
Phần tử đầu tiên nhỏ hơn 2p 11.3% 73
Phần tử đằng trước xa nhất 2p 42.2% 98
Tích ưu tiên 2.6p 31.7% 53
Lượng nước 3 34.3% 187
Truy vấn tổng đoạn con liên tiếp 2p 38.8% 250
Phân đoạn tuyệt đối 3p 19.4% 48
Tổng trên hình chữ nhật 3p 32.7% 43
Lật bit trong khoảng 3p 35.8% 50
Đếm cách tách xâu con chia hết cho 9 2p 38.8% 106
Chia đôi đoạn con 3p 9.9% 35
Khảo sát lưu lượng xe 3.2p 33.6% 34
Tổng ưu tiên 3.6p 12.5% 17
Chia nhóm trên vòng tròn 4p 10.9% 11
Điểm Fermat 3.5 40.2% 96
Tìm điểm trên trục Oz 3.4p 39.1% 26
Đường đi của ánh sáng 4p 51.0% 12

Comments


  • 0
    No_Limit  commented on Feb. 7, 2023, 6:55 a.m.

    sao lại có 3 TuAnh trên bxh vậy :)) , buff bẩn quá !


    • 1
      aaaaa  commented on Feb. 7, 2023, 2:36 p.m.

      có 2 TuAnh thôi ạ :<


  • 0
    No_Limit  commented on Feb. 5, 2023, 10:17 a.m.

    Phải là 7 chứ nhỉ


  • 1
    No_Limit  commented on Feb. 5, 2023, 10:15 a.m.

    bài "tách xâu chia hết 9" thiếu th 1,1 ad ơi


  • 3
    creator  commented on Feb. 3, 2023, 1:04 p.m. ← edited

    Kì thi lập trình dành cho K63 vòng chung kết và kì thi chiến thần thiết kế thuật toán sắp tới sẽ có những vấn đề áp dụng các kĩ thuật trong vòng luyện tập này, mình đã kéo dài thời gian và sẽ thêm \(2\) vấn đề cho các bạn luyện tập nhé.


  • 2
    No_Limit  commented on Jan. 30, 2023, 2:01 p.m.

    Dành cả thanh xuân để code bài "Tìm điểm trên trục Oz" :))


  • 0
    No_Limit  commented on Jan. 30, 2023, 1:57 p.m.

    SOS :)


  • 0
    kehuydietcaude  commented on Jan. 20, 2023, 4:03 a.m.

    Khi nào có đủ đề z ad


    • 1
      creator  commented on Jan. 20, 2023, 5:33 a.m. ← edit 2

      Chốt kì thi gồm 16 bài hoặc ít hơn r, các bài còn lại mình đăng một thể vào tối thứ 7 hoặc tối CN.


  • 0
    kehuydietcaude  commented on Jan. 19, 2023, 1:28 p.m.

    t ghét hình học aaaaaaaaaaa


    • 1
      jjiangly  commented on Jan. 19, 2023, 1:30 p.m.

      Nguyên phần sau toàn hình với hình toang dữ :((


  • 0
    jjiangly  commented on Jan. 19, 2023, 1:14 p.m.

    Cho em hỏi bài Khảo sát lưu lượng xe, test đề giải thích xe thứ nhất dừng ở trạm 1 mà sao output lại là 0 1 0 1 3 vậy ạ. Trạm đếm bắt đầu từ 0 hay 1 vậy ạ


    • 0
      creator  commented on Jan. 19, 2023, 1:16 p.m.

      Bắt đầu từ trạm 1 nhé, mình mới sửa thành 1 không để ý phần ví dụ.


      • 0
        jjiangly  commented on Jan. 19, 2023, 1:24 p.m.

        Hình như bài đó input n, m phải không vậy ạ. Em input m, n theo đề thì bị RTE ạ


  • 0
    jjiangly  commented on Jan. 18, 2023, 2:11 p.m.

    Bài Phân đoạn tổng cố định hình như bị sai test đề phải ko v ạ


    • 0
      creator  commented on Jan. 18, 2023, 2:16 p.m.

      Mình chưa code nhẩm kết quả sai bạn thông cảm :v


  • 0
    kehuydietcaude  commented on Jan. 18, 2023, 2:03 p.m.

    sao bài "Phân đoạn tuyệt đối" không nộp được ta?


    • 0
      creator  commented on Jan. 18, 2023, 2:05 p.m.

      Vì đã cập nhật bộ test đâu :v


      • 0
        kehuydietcaude  commented on Jan. 18, 2023, 2:06 p.m.

        adu, thôi để mai làm :v, hy vọng mai lên kịp


  • 0
    creator  commented on Jan. 18, 2023, 1:17 p.m. ← edited

    Bộ test cho các bài còn lại sẽ được cập nhật dần nhé mn.


    • 1
      kehuydietcaude  commented on Jan. 18, 2023, 1:35 p.m.

      ai thi cũng được hả bạn?