Educational Codeforces Round 98 (Rated for Div. 2) - A & C

Deadline ngập đầu xong tự rước thêm deadline vào thân, xong tự dưng buổi tối lại ngồi gõ code contest.

Vẫn như mọi khi, code nhiều nhưng vẫn thiếu não.

A. Robot Program.

Tóm tắt: Bạn phải điều khiển robot đi từ tọa độ (0, 0) đến tọa độ đích (x, y) trên một lưới ô vuông bằng 5 loại lệnh di chuyển (xem đề), sao cho 2 lệnh liên tiếp không được giống nhau và số lệnh điều khiển đưa ra là ít nhất. 

Hướng giải: Toán + Algoritham.

(Khái niệm Khoảng cách được nhắc đến là Khoảng cách Manhattan).

Để thực hiện ít lệnh nhất thì robot phải hạn chế thực hiện lệnh đứng yên tại chỗ, nói cách khác là robot phải di chuyển zig-zag nhiều nhất có thể. Ta quan sát được các trường hợp sau:

• Nếu |x - y| ≤ 1, robot sẽ di chuyển zig-zag đến đích trong x + y lệnh.
• Còn lại, robot sẽ di chuyển zig-zag trong 2 × min(x, y) lệnh, sau đó đi thẳng đến đích trong 2 × |x - y| - 1 lệnh. Vậy, trong trường hợp này robot sẽ di chuyển đến đích trong tổng cộng 2 × min(x, y) + 2 × |x - y| - 1 lệnh.

Độ phức tạp: O(1).

Code mẫu (C++).

---

C. Two Brackets.

Tóm tắt: Cho một xâu s chỉ gồm các dấu '(', ')', '[', ']'. Một dãy ngoặc thường (regular bracket sequence - RBS) được định nghĩa là dãy có một trong các thuộc tính sau:

• dãy rỗng (không có phần tử nào).
• '(' + RBS + ')'.
• '[' + RBS + ']'.
• RBS + RBS (nối 2 RBS lại).

Trong một thao tác, bạn có thể chọn một dãy con không rỗng của s (không nhất thiết phải liên tục) là RBS, sau đó xóa dãy con đó khỏi s. Tìm số thao tác tối đa bạn có thể thực hiện trên xâu s cho trước.

Hướng giải: Algoritham.

Để thực hiện nhiều thao tác xóa nhất thì mỗi lần ta chỉ xóa một cặp ngoặc hợp lệ (i.e một dấu mở ngoặc và đóng ngoặc của mỗi loại). Đến đây ta đưa về bài toán đếm số cặp ngoặc hợp lệ và đáp án là tổng số cặp ngoặc hợp lệ mỗi loại trong dãy ngoặc ban đầu.

Tổng thể, độ phức tạp là O(n).

Code mẫu (C++).

---

Happy coding!