SIU AUTUMN TOUR WEEK 2 #1

Tutorial

A. Lồng đèn

Category: Implementation

Hint:
Chỉ cần đếm số lượng ký tự '1' trong chuỗi 0/1 đã cho.

Solution:
Đọc chuỗi đầu vào, duyệt toàn bộ và đếm số lượng ký tự '1'.
In ra kết quả đếm được.

Complexity:
O(n) — với n là độ dài chuỗi.

B. Dãy con cân bằng

Category: Constructive algorithm

Hint:

1. Chú ý rằng n = 2 là trường hợp duy nhất không có nghiệm.

2. Có thể phân tích theo tính chẵn/lẻ của n.

3. Nhiều người nhầm rằng với n chẵn thì vô nghiệm — nhưng điều đó sai.

Solution:
Đây là bài toán cấu trúc (construction).

• Nếu n là số lẻ, có thể tạo hoán vị như sau:
  n, n−1, …, ⌈n/2⌉ + 1, 1, 2, …, ⌊n/2⌋

• Nếu n là số chẵn, chỉ cần hoán đổi vị trí của n và n−1 trong dãy trên.
  Cách này đảm bảo độ dài dãy con tăng và giảm dài nhất là bằng nhau.

Complexity:
O(n) — chỉ cần xây dựng một dãy duy nhất.

C. Vượt lũ

Category: Dynamic Programming / Graph Search

Hint:
Tìm đường đi với độ sâu nước tối thiểu mà pháp sư có thể vượt qua từ ô đầu đến ô cuối.

Solution:
Có hai cách giải:

1. Dynamic Programming:

   • Với mỗi ô, tính độ sâu nước nhỏ nhất mà pháp sư có thể tới được từ ô đầu.

   • Duyệt từng hàng hai lần (trái→phải, phải→trái) để xét di chuyển hai chiều.

   • Độ phức tạp O(n·m).

2. Binary Search + BFS/DFS:

   • Dùng tìm kiếm nhị phân trên giá trị độ sâu nước x.

   • Với mỗi x, chỉ giữ lại các ô có độ sâu ≥ x và kiểm tra có đường đi hợp lệ không bằng BFS.

   • Độ phức tạp O(n·m·log D), với D là độ sâu nước lớn nhất.

Complexity:
O(n·m) hoặc O(n·m·log D).

D. Trốn ở đâu?

Category: Graph / BFS

Hint:
Bắt đầu BFS đa nguồn từ tất cả các lá (leaf) trong cây để tìm khoảng cách tới nút gần nhất.

Solution:

• Đưa tất cả lá vào hàng đợi ban đầu.

• Thực hiện BFS để tính khoảng cách từ mỗi nút đến lá gần nhất.

• Sau khi hoàn thành, chọn vị trí đầu tiên có giá trị khoảng cách lớn nhất.

Complexity:
O(n) — do duyệt mỗi cạnh một lần.

E. Dây đàn và nốt nhạc

Category: Dynamic Programming / Bijection

Hint:

1. Hãy tìm một bài toán tương đương (bijection) dễ hơn.

2. Quan sát mảng hiệu của a khi thực hiện thao tác.

3. Dùng quy hoạch động để kiểm tra khả năng chuyển đổi từ a sang b.

Solution:

• Đặt da[i] = a[i+1] − a[i], db[i] = b[i+1] − b[i], di = db[i] − da[i].

• Có 6 kiểu thao tác khác nhau, mỗi kiểu thay đổi mảng hiệu da theo quy tắc riêng.

• Mục tiêu: kiểm tra xem có thể biến da thành db bằng các thao tác hợp lệ hay không.

• Nếu có phần tử di < 0 ⇒ không thể.

• Dùng DP để kiểm tra xem với mỗi suffix [i, n−1], có thể chuyển đổi được không, với điều kiện mỗi vị trí được thao tác tối đa 2 lần.

• Xét cẩn thận trường hợp biên khi da[i] = 1 mà không thể tăng thêm.

Complexity:
O(n) — quy hoạch động tuyến tính theo chiều dài dãy.

F. Elden Ring

Category: Simulation / Number Theory

Hint:
Hai vòng có kích thước n và m cùng bắt đầu đếm từ 1; khi đếm tới số chia hết cho m thì hai vòng đổi vị trí. Cần tìm trạng thái cuối sau khi đếm đến k.

Solution:

• Nếu chỉ có một vòng, trạng thái lặp lại sau lcm(n, m) bước.

• Với hai vòng đổi chỗ, chu kỳ quay lại ban đầu là 2 × lcm(n, m).

• Chỉ cần xét k mod (2 × lcm(n, m)).

• Khi n, m ≤ 10⁶ có thể mô phỏng trực tiếp; với k rất lớn, chỉ cần tính vị trí trong chu kỳ.

Complexity:
O(k) hoặc O(lcm(n, m)) — tùy cách mô phỏng và rút gọn.

Lưu ý : Code đầy đủ được chia sẻ ngay trong contest codeforce.