Phân tích: City Tour

Đây được coi là bài toán dễ nhất trong vòng chung kết đối với các thí sinh có kinh nghiệm.

Chúng ta có thể hiểu sâu hơn về bài toán bằng cách nhận thấy đồ thị này tương tự như một cấu trúc cây. Những đồ thị này thực chất được gọi là partial 2-trees. Chúng ta thực sự có thể xây dựng một cái cây nếu làm theo cách đồ thị được tạo ra. Chúng ta xây dựng một đồ thị khác liên kết mỗi nút với mỗi chu trình độ dài 3 mới được thêm vào; chu trình này chia sẻ một cạnh với một chu trình cũ, vì vậy chúng ta thêm một cạnh giữa hai nút tương ứng trong đồ thị thứ hai này. Bằng cách này, chúng ta đã xây dựng được cấu trúc tree decomposition của các đồ thị này. Giống như trên cây, nhiều bài toán khó giải trên đồ thị tổng quát lại có thuật toán đa thức trên loại đồ thị này.

Hãy giải bài toán liên quan là tìm đường đi dài nhất trên cây. Chúng ta có thể sử dụng quy hoạch động và tìm kiếm theo chiều sâu (DFS). Chúng ta chọn một nút làm gốc. Mọi đường đi trong cây đều có đúng một nút gần gốc nhất và nút này chia đường đi thành hai đường đi hướng xuống. Bây giờ, đối với mỗi nút trong cây, chúng ta tính đường đi hướng xuống dài nhất bắt đầu từ nó. Để tìm đường đi lớn nhất trong cây, chúng ta xem xét tại mỗi nút và hai đường đi dài nhất bắt đầu từ các con của nó. Điều này giải quyết bài toán trong thời gian tuyến tính.

Giải pháp cho bài toán gốc của chúng ta cũng khá tương tự. Đối với mỗi cạnh \((x, y)\), chúng ta tính chu trình chứa nó và tất cả các nút khác trong chu trình đều có chỉ số lớn hơn. Hãy gọi đây là một "chu trình hướng xuống" (downward cycle) vì nó đi ngược hướng với vị trí của ba nút ban đầu. Để tìm số lượng đó, chúng ta phải xem xét tất cả các nút có chỉ số cao hơn đã được kết nối với cạnh này và thử sử dụng chúng làm các điểm trung gian trong chu trình. Vì vậy, đối với một điểm trung gian \(z\) nhất định, chúng ta có thể xây dựng một chu trình bằng cách xem xét đường đi hướng xuống dài nhất chứa cạnh \((x, z)\) và đường đi hướng xuống dài nhất chứa cạnh \((z, y)\), sử dụng tất cả các cạnh, thêm cạnh \((x, y)\) và loại bỏ các cạnh \((x, z)\) và \((z, y)\).

Chúng ta cũng tính toán đường đi hướng xuống dài nhất chứa hai nút này nhưng không chứa cạnh này, đây là sự kết hợp của đường đi đi qua các nút này và đường đi lớn thứ hai mà từ đó chúng ta loại bỏ cạnh \((x, y)\).

Dưới đây là đoạn mã thực hiện giải pháp này:

int best_so_far = 0;

int best(int x, int y, int N, int[][] a) {
    int max_len = 2;
    int second_max_len = -1;
    for (int i = Math.max(x, y) + 1; i < N; i++) {
      if (a[x][i] * a[y][i] > 0) {
        int len =  best(x, i, N, a) + best(y, i, N, a) - 1;
        if (len > max_len) {
          second_max_len = max_len;
          max_len = len;
        } else if (len > second_max_len) {
          second_max_len = len;
        }
      }
    }
    best_so_far = Math.max(max_len, best_so_far);
    best_so_far = Math.max(max_len + second_max_len - 2,
                           best_so_far);
    return max_len;
}

Một giải pháp thú vị khác dựa trên ý tưởng co (contracting) mỗi nút có bậc hai. Chúng ta thay thế nó bằng một cạnh có trọng số bằng tổng trọng số của hai cạnh đi vào. Đó là một ý tưởng khá hay và chúng tôi sẽ để bạn tự tìm hiểu chi tiết.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2010 - World Finals - City Tour, thuộc kho Google Coding Competitions (Apache-2.0).