Hướng dẫn NTUCoder Round #11

admin - 20/07/2015

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)

CÁC PHẢN HỒI

Back to Top