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

Các chủ đề thiết kế trong vòng luyện tập \(3\):

  • (Thuần) Quy hoạch động - Dynamic programming (DP).
  • Hai con trỏ - Two pointers.
  • Chia để trị, giảm để trị - Divide and conquer, Decrease and conquer (DAC).

Kĩ thuật mở rộng (với quy hoạch động):

  • Quy hoạch động với nhân ma trận - DP with matrix multiplication.
  • Quy hoạch động trên cây - DP on tree.

Chủ đề mở rộng

  • Cây phân đoạn - Segment tree.

Link lần luyện tập 1

Link lần luyện tập 2

Problems

Problem Points AC Rate Users
Rút gọn đơn thức 1.5p 50.7% 86
Number removal puzzle 2p 18.9% 43
Almost Fibonacci 3p 14.0% 68
Relatively prime tower 3p 13.2% 20
Table of numbers 3p 24.4% 23
Đếm các tập con 3p 18.7% 42
Cây ATM trả tiền 3p 47.5% 100
Biến đổi xâu 3 34.9% 81
Chuỗi số 2 35.7% 36
nqson OCD 3 31.2% 28
Dãy con bitonic dài nhất 3 27.4% 95
Phân đoạn các giá trị riêng biệt 3.2 28.7% 19
Xâu FIBONACCI (đơn giản) 2.5 30.1% 148
Tháp Hà Nội 2.5 42.7% 152
Đường kính cây 3.2 33.3% 16
Thử thách 3.5 42.6% 24
Cây phân đoạn (Segment Tree) 4p 13.8% 20

Comments


  • 1
    kehuydietcaude  commented on April 11, 2023, 4:47 p.m.

    câu C, Constraints không có n = 0, nhưng input lại có =))


  • 2
    creator  commented on April 9, 2023, 2:03 p.m. ← edit 3

    Bộ đề đã được cập nhật đầy đủ, mn code dần luyện tập cho vòng chung kết chiến thần nhé.

    Thuật toán Floyd (thuần QHĐ), dãy con đơn điệu tăng dài nhất, thuật toán Manacher các bạn có thể tìm hiểu thêm.