Bình luận

• 
  

  0

  

  username001  đã bình luận lúc 13, Tháng 5, 2026, 4:23

  Bài toán này thực chất được lấy từ kỳ thi ICPC East Central North America Regional Contest 2016 (Bài D – Lost in Translation).

  Tuy nhiên, bản dịch tiếng Việt trên Free Contest mắc phải hai lỗi dịch thuật nghiêm trọng, làm thay đổi hoàn toàn bản chất của bài toán:

  1. Lỗi dịch thuật thứ nhất (nghiêm trọng nhất):
     Đề tiếng Việt ghi rằng một dịch giả “có thể dịch từ ngôn ngữ l1 sang ngôn ngữ l2” — cách diễn đạt này khiến người đọc hiểu rằng đồ thị là có hướng.

     Trong khi đó, đề gốc tiếng Anh viết rõ:

     “the cost to translate between them (in either direction)”

     Điều này có nghĩa là việc dịch thuật được thực hiện theo cả hai chiều giữa l1 và l2. Vì vậy, mô hình đúng của bài toán bắt buộc phải là đồ thị vô hướng.

  2. Lỗi dịch thuật thứ hai:
     Đề tiếng Việt ghi:

     “số thứ tiếng trung gian của bản dịch cần nhiều thứ tiếng trung gian nhất phải thấp nhất có thể”

     Cách diễn đạt này khiến người đọc dễ hiểu nhầm rằng cần tối thiểu hóa độ sâu lớn nhất của cây.

     Tuy nhiên, đề gốc tiếng Anh viết:

     “minimize each target language's distance from English”

     Nghĩa đúng là: với mỗi ngôn ngữ đích, cần tối thiểu hóa khoảng cách từ tiếng Anh đến ngôn ngữ đó. Nói cách khác, ta cần xây dựng một BFS shortest-path tree từ English.

  May mắn là dù bản dịch sai, test mẫu vẫn đủ để suy ra đúng ý tưởng BFS.

  Do đồ thị thực chất là vô hướng, các test ẩn hoàn toàn có thể chứa dữ liệu theo dạng:

  ```text French English 1

  thay vì:

  English French 1

  Nếu cài đặt đồ thị có hướng như theo bản dịch tiếng Việt, chương trình sẽ hiểu rằng không tồn tại đường đi từ English đến French, dẫn đến kết quả sai hoặc in ra Impossible.