Comments

• 
  

  -13

  

  xero2409  commented on April 28, 2023, 5:03 a.m. ← edit 5 →

  Thuật chuẩn:

  xài chặt nhị phân

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  -5

  

  PM  commented on July 23, 2023, 2:39 a.m.

  ? đòi đú:))

  This comment is hidden due to too much negative feedback. Show it anyway.

• 
  

  30

  

  marvinthang  commented on March 19, 2022, 2:38 p.m. ← edited →

  Thuật chuẩn:

  ~Binary Search~

  Check bằng quy hoạch động

  ~F_i~: có tồn tại trạng thái 1 người ở nhà thứ i không, nếu có tìm j lớn nhất thỏa mãn khoảng cách từ ~X_{i + 1}, .. X_j~ đến ~X_i \leq D~ thì ~ F_{i + 1}, .., F_j = true~.

  ĐPT: ~O(N^2 * \log_2 N~)

  Cải tiến:

  Sử dụng ~Sparse Table~ kết hợp ~Binary Search~ để tìm j, j thỏa mãn khi khoảng cách từ ~max(X_{i + 1}, .., X_j)~ và ~min(X_{i + 1}, .., X_j)~ đến ~X_i \leq D~.

  ĐPT ~O(N * log_2^2 N~)

  Code mẫu: Ideone