1) Bài A - Số La Mã
Cách thực hiện: xét các ký tự s[i] trong chuỗi input, nếu s[i] >= s[i+1] thì cộng s[i] vào kết quả, nếu ngược lại thì trừ s[i] khỏi kết quả. Độ phức tạp O(|s|).
2) Bài B - Chữ số
Số lượng số thuộc n đoạn đầu tiên được tính theo công thức: S = 1+2+...+n = n(n+1)/2. Vậy ta cần tìm n lớn nhất sao cho S < K, sau đó tính (K-S)%10 là có kết quả.
Để tính n, đầu tiên giả sử n = sqrt(2K), nếu n2 + n < 2K thì OK. Nếu không lấy n = sqrt(2K)-1.
Độ phức tạp O(1)
3) Bài C - Windows Phone Live Tile
Gọi x là số miếng 1x1, y là số miếng 2x2, z là số miếng 2x4. Như vậy ta cần tìm nghiệm nguyên của hệ:
x + y + z = m
x + 4y + 8z = n*6
z ≤ n/2
và x ≥ 6 nếu n lẻ.
Nếu có nghiệm nguyên, nghĩa là có cách sắp LiveTile. Ta thực hiện sắp theo kiểu tham lam như sau: Một lần sắp 2 dòng. Ưu tiên sắp miếng 2x4 trước, dĩ nhiên là chỉ sắp được 1 miếng. Sau đó tiếp theo là miếng 2x2, nếu hết miếng 2x2 thì mới đến miếng 1x1 để sắp cho 2 dòng đó. Sau đó lại chuyển sang 2 dòng tiếp theo. Trường hợp đặc biệt là khi n lẻ, dòng cuối cùng được sắp bằng 6 miếng 1x1.
Độ phức tạp: O(m2) để vét giải hệ trên, O(n) để đưa ra cách sắp ô.
4) Bài D - Robot tìm đường
Nhận xét rằng, một ô [i,j] chỉ có thể được đi qua tối đa 4 lần theo 4 hướng khác nhau: từ ô [i, j-1] sang phải, từ ô [i, j+1] sang trái, từ ô [i-1, j] xuống, từ ô [i+1, j] lên. Nếu đi qua 5 lần thì có 2 lần là cùng hướng nghĩa là robot đi vòng vòng quay lại đường cũ. Như vậy xem như ta có một đồ thị n x m x 4 đỉnh.
Dùng DFS hay BFS để duyệt cho tới khi đến ô đích. Trong quá trình duyệt chỉ đi từ đỉnh này sang đỉnh kia nếu ô tương ứng là đi thẳng hay rẽ trái. Độ phức tạp O(4mn).
5) Bài E - Palindrome
Bài toán quy về tính l[i] là số lượng xâu đối xứng kết thúc tại i và r[i] là số lượng xâu đối xứng bắt đầu tại i.
Để tính l[i], r[i], ta sử dụng thuật toán Manacher để tính bán kính đối xứng tại mỗi vị trí i.
Giả sử vị trí i có bán kính đối xứng len:
- Trường hợp i là tâm (độ dài xâu đối xứng lẻ): tăng mảng r từ i - len + 1 tới i lên 1, tăng mảng l từ i tới i + len - 1 lên 1.
- Trường hợp i - 1 và i là tâm (độ dài xâu đối xứng chẵn): tăng mảng r từ i - len tới i - 1 lên 1, tăng mảng l từ i tới i + len - 1 lên 1.
Kết quả bài toán là tổng l[i] * r[i] với mọi i từ 1 tới n.
Độ phức tạp: O(n)
(còn tiếp)