Codeforces Round #731 (Div. 3) - A, B & C

 

Lâu lắm mới chơi contest lại và vẫn ngu!

---

A - Shortest Path with Obstacle.

Tóm tắt: Trên mặt phẳng $ Oxy $ cho 3 điểm $A(x_A, y_A), B(x_B, y_B), F(x_F, y_F)$. Tìm độ dài đường đi ngắn nhất từ $A$ đến $B$, biết rằng bạn chỉ có thể đi qua các ô kề cạnh với ô đang đứng và trên đường đi không được đi qua ô $F$.

Cách giải: dùng Khoảng cách Manhattan với tí quan sát:

• Nếu $A, B, F$ cùng nằm trên 1 đường thẳng và $F$ nằm giữa $A, B$ (nghĩa là, ($x_A = x_F = x_B$ và $y_A \leq y_F \leq y_B$) hoặc ($y_A = y_F = y_B$ và $x_A \leq x_F \leq x_B$)) thì độ dài đường đi $l = |x_A - x_B| + |y_A - y_B| + 2$. $+2$ ở trường hợp này là để "né" ô $F$ ra.
• Còn lại, độ dài đường đi $l = |x_A - x_B| + |y_A - y_B|$.

Q: Ở đâu ra công thức này? A: Nhìn hình trong ví dụ là biết. 

Bài này chỉ hơi tricky ở chỗ $F$ có thể nằm giữa $A, B$ hoặc không. Code cẩn thận là ổn.

Code mẫu (C++).

---

B - Alphabetical Strings.

Tóm tắt: Thuật toán sinh một xâu (chỉ gồm các chữ cái Latinh viết thường) được định nghĩa trong đề. Cho một xâu $s$, xác định xem xâu $s$ có thể được sinh từ thuật toán trên hay không?

Cách giải: Algoritham.

1. Tìm chữ cái $s_{\text{max}}$ có ASCII lớn nhất trong $s$. Nếu $s_{\text{max}}$ không nằm ở đầu / cuối xâu thì xâu này không được sinh từ thuật toán trên.
• Ta có điều này vì chữ cái cuối cùng được thêm vào đầu / cuối xâu, theo định nghĩa thuật toán.
2. Xóa $s_{\text{max}}$, sau đó xét:
• Nếu $s_{\text{max}} = s_0$, chữ cái tiếp theo cần xóa là chữ cái liền trước $s_0$ trong bảng alphabet và phải đứng ở đầu / cuối xâu.
• Nếu $s_{\text{max}} = s_{n - 1}$, chữ cái tiếp theo cần xóa là chữ cái liền trước $s_{n - 1}$ trong bảng alphabet và phải đứng ở đầu / cuối xâu.
• Nếu không tìm được chữ cái cần xóa, xâu này không thể sinh từ thuật toán.
3. Lặp lại từ bước 2 đến khi xâu còn duy nhất 1 ký tự.
4. Nếu ký tự cuối cùng là ký tự $'a'$, xâu này được sinh từ thuật toán.

Code mẫu (C++).

---

C - Pair Programming.

Tóm tắt: Cho số nguyên $k$, mảng $A$ gồm $n$ phần tử và $B$ gồm $m$ phần tử. Tìm một mảng  $\text{res}$ gồm $n + m$ phần tử sao cho

• Mảng $\text{res}$ gồm các phần tử từ $A, B$, mỗi phần tử xuất hiện đúng thứ tự của nó trong mảng ban đầu.
• Với mỗi phần tử $\text{res}_i = 0$, tăng $k$ lên 1 đơn vị.
• Với mỗi phần tử $\text{res}_i > 0$, $\text{res}_i \leq k$. 

Cách giải: Nghe qua nếu ẩu (như mình) sẽ chọn Algoritham sort các phần tử của 2 mảng tăng dần rồi in ra. Tuy nhiên, câu in đen bên trên đòi hỏi vị trí của các phần tử phải ổn định. Vậy, không Algoritham.

Ta sẽ giải theo tư tưởng của Merge Sort. Ta sẽ merge các phần tử theo ưu tiên số 0 merge trước, nếu không còn số 0 thì merge các phần tử $\leq k$ và nếu không còn lựa chọn nữa thì kết luận không thể merge.

Code mẫu (C++).

---

Happy coding!