Tutorial
A. Tia Laser
Category: output-only, math
Hint: Đang giải một bài toán vô nghĩa: tìm số vùng mà một đường thẳng có thể cắt qua khi chia mặt phẳng thành 4 góc phần tư.
Solution: Giả sử tấm chăn vô hạn (L = W = ∞) như mặt phẳng tọa độ.
- Bất kỳ đường thẳng nào không đi qua gốc tọa độ sẽ chỉ cắt tối đa 3 góc phần tư, thực tế chỉ 2 góc đối nhau.
- Nếu đường đó là trục X hoặc trục Y, nó cắt cả 4 góc phần tư.
Vì vậy, đáp án không phụ thuộc L, W, và luôn là 2.
Complexity: O(1)
B. Dịch chuyển không gian
Category: geometry, math
Hint: Xét xem ta có thể đến điểm nào thông qua nhiều lần phản xạ quanh các điểm khác.
Solution: Giả sử vị trí ban đầu là (x₁, y₁), phản xạ qua điểm (x, y). Sau phản xạ, tọa độ mới là (x₁ + 2(x − x₁), y₁ + 2(y − y₁)). Cả hai tọa độ mới cách vị trí ban đầu một khoảng chẵn. Do đó, ta chỉ có thể đến các điểm có cùng tính chẵn lẻ (parity) với điểm xuất phát. Khi hai điểm có cùng parity, ta có thể đi từ điểm này đến điểm kia qua các lần phản xạ.
Complexity: O(1) mỗi test.
C. Sai một li, đi một dặm
Category: greedy, dp, monotonic stack
Hint: Tính tổng độ dài “dãy con tham lam” của mọi dãy con trong mảng.
Solution: Gọi fᵢ là tổng độ dài dãy con tham lam bắt đầu từ phần tử aᵢ. Với mỗi phần tử, ta tìm phần tử đầu tiên bên phải lớn hơn nó bằng ngăn xếp đơn điệu, gọi là rᵢ.
- Các dãy con từ a[i] đến a[rᵢ−1] có độ dài 1.
- Các dãy con kéo dài qua a[rᵢ] sẽ có độ dài tăng thêm 1.
Suy ra công thức truy hồi: fᵢ = n − i + 1 + frᵢ. Kết quả là tổng tất cả fᵢ.
Complexity: O(n)
D. Bánh quy
Category: combinatorics, counting
Hint: Xét từng phần tử riêng lẻ và tính mức đóng góp (contribution) của nó vào kết quả.
Solution: Giả sử các phần tử trong mảng là phân biệt. Mỗi phần tử aᵢ có thể trở thành giá trị cuối cùng của 'cookie nutrition' khi:
- aⱼ < aᵢ: chọn hàm max, hoặc
- aⱼ > aᵢ: chọn hàm min.
Vì có (i−2) phần tử trước có thể tự do chọn, nên đóng góp của aᵢ là aᵢ ×2(i−2).
Tổng kết quả là a₁ + Σ aᵢ × 2(i−2) mod (10⁹+7).
Complexity: O(n)
E. Khoảng cách đối xứng
Category: dynamic programming, string
Hint: Tìm số phép chèn/xóa/thay thế ít nhất để biến chuỗi thành palindrome.
Solution: Xét chuỗi S[l..r]:
- Nếu Sₗ = Sᵣ → dp[l][r] = dp[l+1][r−1]
- Nếu khác → dp[l][r] = min(dp[l+1][r], dp[l][r−1], dp[l+1][r−1]) + 1
Ý tưởng là thử từng thao tác (chèn ở đầu/cuối, thay ký tự) để đạt palindrome gần nhất. Tính từ các đoạn nhỏ đến lớn để tránh tính lặp.
Complexity: O(n²)
F. Cây Đỏ-Đen
Category: geometry, interval, prefix sum
Hint: Sau quá trình tô màu, ta thu được các tam giác không giao nhau — chỉ cần biết đáy của mỗi tam giác là có thể tính tổng kết quả.
Solution: Quan sát trạng thái cuối cùng là tập hợp các tam giác không giao nhau, mỗi tam giác có đáy m với số lá = m × (m+1) / 2.
Ghi lại khoảng mở rộng của từng điểm đến tầng n, sau đó hợp các khoảng này và tính riêng từng đoạn. Các đoạn không giao nhau được cộng dồn bằng hiệu + tiền tố (difference + prefix sum) để nhanh chóng hợp lại.
Complexity: O(n)