Phân tích: Willow

Bài toán có thể được diễn đạt lại như sau: chúng ta được cho một cây gồm \(N\) đỉnh, mỗi đỉnh \(i\) có \(C_i\) đồng xu. Có hai người chơi luân phiên thực hiện lượt chơi. Đầu tiên, mỗi người chọn một đỉnh bắt đầu (có thể trùng nhau), sau đó người chơi 1 thực hiện nước đi đầu tiên. Trong một nước đi, người chơi chọn một đỉnh lân cận mới chưa được sử dụng đường nối từ đỉnh hiện tại, tạo thành một đường đi đơn giản. Đường đi của một người chơi được phép giao nhau tại tối đa một đỉnh (tức là không có cạnh nào chồng chéo) với đường đi của người chơi kia. Trò chơi kết thúc khi không người nào có thể di chuyển. Điểm của người chơi là tổng số xu tại các đỉnh họ đã đi qua trừ đi tổng số xu của đối thủ. Nhiệm vụ là tìm điểm tối đa cho người chơi 1.

Có \(N\) đỉnh bắt đầu cho người chơi 1. Sau đó, người chơi 2 cũng có \(N\) đỉnh bắt đầu. Cả hai sẽ chọn đỉnh bắt đầu để tối đa hóa điểm của mình. Giải pháp cấp cao để tìm điểm tối đa cho người chơi 1 được thể hiện trong mã giả dưới đây:

  p1_max_score = -INFINITE
  for p1_start_vertex in 1 .. N:
    min_score = INFINITE
    for p2_start_vertex in 1 .. N:
      p1_score = minimax(p1_start_vertex, p2_start_vertex)
      min_score = min(min_score, p1_score)
    p1_max_score = max(p1_max_score, min_score)

  print p1_max_score

Người chơi 1 cố gắng chọn đỉnh bắt đầu để tối đa hóa p1_max_score, trong khi người chơi 2 cố gắng chọn đỉnh bắt đầu để giảm thiểu điểm số của người chơi 1. Hàm minimax là thuật toán chính để tối đa hóa điểm cho người chơi đầu tiên, với các đỉnh bắt đầu đã cho.

Dưới đây là hai thuật toán minimax. Thuật toán đầu tiên dựa trên mô phỏng DFS chạy trong \(O(N^2)\), cho tổng độ phức tạp \(O(N^4)\). Thuật toán thứ hai dựa trên quy hoạch động có thể tính toán trước trong \(O(N^2)\) và trả lời trong \(O(1)\), cho tổng độ phức tạp \(O(N^2)\).

Minimax sử dụng mô phỏng \(O(N^2)\)

Với đỉnh bắt đầu của mỗi người chơi, ta có thể thực hiện mô phỏng DFS cho thuật toán minimax. Trạng thái DFS là các đỉnh cuối cùng được chọn bởi mỗi người chơi và người chơi hiện đang thực hiện lượt. Người chơi hiện tại lấy xu tại đỉnh hiện tại và cố gắng chọn một đỉnh lân cận để tối đa hóa tổng số xu. Trước khi di chuyển, cạnh nối được loại bỏ và sau đó được khôi phục khi DFS quay lui. Nếu không thể di chuyển, lượt chơi được chuyển cho người kia.

function rec(i, j, turn)  # See note 1
  if visited[i][j][turn] return 0  # See note 2
  visited[i][j][turn] = true

  ci = C[i]  # See note 3
  C[i] = 0  # Remove the coins at vertex i

  ret = -INF
  for each neighbor ni of i
    remove edge[i][ni]  # See note 4
    ret = max(ret, -rec(j, ni, 1 - turn))
    restore edge[i][ni]

  if ret == -INF
    ret = -rec(j, i, 1 - turn)  # See note 5

  C[i] = ci  # Restore the coins at vertex i

  return ret + ci

Lưu ý:

1. Tham số i là đỉnh cuối cùng do người đang đi lượt hiện tại chọn; j là đỉnh cuối của người kia; turn là ID người đang đi lượt (\(0\) là người chơi 1, \(1\) là người chơi 2).
2. Trạng thái (i,j,turn) chỉ được thăm đúng một lần. Lần thăm tiếp theo vào cùng trạng thái trả về \(0\), biểu thị điều kiện kết thúc.
3. Ta tạm lưu số xu ở đỉnh của người chơi hiện tại, đặt số xu tại i thành \(0\) để các lời gọi DFS sau không dùng lại, rồi khôi phục trước khi trả về.
4. Xóa cạnh nối trước khi đệ quy sang đỉnh kế tiếp bảo đảm cả hai người không thể dùng lại cạnh đó về sau. Cạnh được khôi phục khi quay lui; số xu cũng được xử lý tương tự.
5. Nếu người hiện tại không thể đi, họ phải nhường lượt cho người kia.

Độ phức tạp \(O(N^2)\) cho mỗi cặp đỉnh bắt đầu dẫn đến tổng \(O(N^4)\), chỉ phù hợp với Small dataset (\(N=80\)).

Minimax với Quy hoạch động \(O(1)\)

Ý tưởng của thời gian trả lời \(O(1)\) là tái sử dụng kết quả khi xét các đỉnh bắt đầu khác nhau. Trạng thái DFS ở phần trước không độc lập với trạng thái khác vì phải theo dõi những đồng xu đã lấy và những cạnh không còn dùng được; mỗi trạng thái có một tập xu và cạnh khả dụng riêng. Nếu thiết kế được trạng thái không cần quan tâm xu hay cạnh nào còn lại, mỗi trạng thái sẽ độc lập, có thể ghi nhớ kết quả và tái sử dụng; khi đó mỗi trạng thái được tính trong \(O(1)\).

Quan sát quan trọng: Sau khi một người chơi di chuyển, cạnh nối bị xóa. Nếu đỉnh mới không thể đi tới đỉnh cuối của người chơi kia, hai đỉnh nằm trong hai cây riêng biệt. Khi đó, mỗi người chỉ cần chọn đường đi tốt nhất còn lại trong cây của mình. Chúng ta chỉ cần thực hiện minimax khi hai người chơi vẫn ở trong cùng một cây.

Trạng thái mới được mô tả bởi cạnh cuối cùng mà mỗi người chơi đã đi qua (\(O(N^2)\) cặp cạnh). Người chơi hiện tại có hai lựa chọn:

1. Đi về phía đỉnh cuối của người chơi kia: Vì đồ thị đầu vào là cây, có đúng một đường đi nối hai đỉnh cuối. Người hiện tại chọn đỉnh kế trên đường ấy để tiến gần đối phương. Sau nước đi, ta chuyển tới trạng thái mới trong đó người kia đi lượt. Trạng thái mới độc lập với trạng thái cũ: người hiện tại không thể quay về đỉnh trước, còn đối phương không thể tới các đỉnh nằm phía sau người hiện tại, nên không cần nhớ xu hay cạnh nào đã bị lấy. Đỉnh hướng tới đối phương được tìm trong \(O(1)\) sau tiền xử lý. Tiền xử lý này là một quy hoạch động với trạng thái gồm cạnh cuối của người hiện tại và đỉnh cuối của đối phương; chuyển trạng thái tiến gần đối phương thực hiện trong \(O(1)\) vì trung bình mỗi đỉnh có một cạnh đi ra. Chi tiết nằm trong cách tính next_node_to của mã mẫu.

Trong hình, người chơi 1 đang đi, ở đỉnh i1, cạnh cuối nối với p1; người chơi 2 ở i2, cạnh cuối nối với p2. Người chơi 1 chọn n1, đỉnh dẫn tới i2. Sau đó đệ quy sang trạng thái độc lập: người chơi 2 ở i2 giữ cạnh cuối cũ, còn người chơi 1 ở n1 với cạnh cuối nối về i1.

1. Đi theo đỉnh tốt nhất không hướng về phía đối phương: Danh sách đỉnh tốt nhất có thể được tiền xử lý để chọn trong \(O(1)\). Nước đi này làm đỉnh mới của người hiện tại tách khỏi đỉnh cuối của đối phương; tổng xu tối đa của họ từ đó được xử lý độc lập trong \(O(1)\). Đối phương cũng có thể độc lập chọn đường tốt nhất tránh các cạnh người hiện tại đã dùng.

Như trước, người chơi 1 ở i1, cạnh cuối nối p1; người chơi 2 ở i2, cạnh cuối nối p2. Người chơi 1 chọn n1, đỉnh dẫn tới đường tốt nhất nhưng đã tách khỏi i2. Lúc này hai phía độc lập. Người chơi 2 có thể đi theo hướng tới i1, rồi ở bất kỳ lúc nào rẽ sang hướng khác để lấy đường tốt nhất. Trường hợp đặc biệt là khi tới i1, người chơi 2 không thể rẽ về p1 hay n1 vì hai cạnh đó đã được dùng; chỉ có thể rẽ sang f2. Vì khi rẽ chỉ cần đường tốt nhất chưa bị cấm, và lựa chọn tốt thứ ba chỉ xuất hiện trong trường hợp đặc biệt ấy, lưu ba cạnh đi ra tốt nhất cho mỗi đỉnh là đủ. Ta tiền xử lý bằng DP tổng xu lớn nhất khi rẽ tại một điểm giữa i2 và i1, kể cả hai đầu, trong \(O(N^2)\); xem hàm branch_off_between và chú thích trong mã mẫu. Nhờ đó, số xu tối đa của người chơi 2 trong trường hợp này được trả lời trong \(O(1)\).

Với \(O(N^2)\) trạng thái và mỗi trạng thái tính trong \(O(1)\), tổng độ phức tạp là \(O(N^2)\).

Cài đặt tham khảo (C++11)

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 4001
#define MAXE (MAXN * 3)

vector<int> con[MAXN];
int T, N, C[MAXN], id;
int edge_id[MAXN][MAXN];
int next_node_to[MAXN][MAXN];
int best_coins[MAXE];
int best_nodes[MAXE][3];
int memo_rec[MAXE][MAXE];
int memo_branch_off[MAXE][MAXE];

// Pre-calculate the next_node_to, best_coins, best_nodes.
void precalc(int i, int pi, int from, int first_node) {
  next_node_to[from][i] = first_node;
  int &best = best_coins[edge_id[i][pi]];
  best = 0;
  vector<pair<int, int> > arr;
  for (int ni : con[i]) if (ni != pi) {
    precalc(ni, i, from, first_node);
    int coins = best_coins[edge_id[ni][i]];
    arr.push_back(make_pair(coins, ni));
    best = max(best, coins);
  }
  sort(arr.rbegin(), arr.rend());
  for (int j = 0; j < arr.size() && j < 3; j++)
    best_nodes[edge_id[i][pi]][j] = arr[j].second;
  best += C[i];
}

// Returns the best next vertex when coming from
// edge (pi -> i), excluding vertex v1 and v2.
int next_best_except(int i, int pi, int v1, int v2 = -1) {
  int ei = edge_id[i][pi];
  int j = 0, *arr = best_nodes[ei];
  if (arr[j] == v1 || arr[j] == v2) j++;
  if (arr[j] == v1 || arr[j] == v2) j++;
  return arr[j];
}

// Maximum coins for sub-tree i with parent pi.
int max_coins(int i, int pi) {
  return (i < 0) ? 0 : best_coins[edge_id[i][pi]];
}

// Maximum coins for branching off at any vertex in [i, j].
int branch_off_between(int i, int pi, int j, int pj) {
  int ei = edge_id[i][pi];
  int ej = edge_id[j][pj];
  int &ret = memo_branch_off[ei][ej];
  if (ret != -1) return ret;

  if (i == j) {
    int ni = next_best_except(i, pi, pj);
    int nj = next_best_except(i, pi, pj, ni);
    // The other player takes the third best vertex nj since
    // the best two are already taken by the current player.
    return ret = max_coins(nj, j);
  }

  int nj = next_node_to[j][i];
  int njb = next_best_except(j, pj, nj);
  int branch_off_now = max_coins(njb, j);
  int branch_off_later = ((nj == i) ? 0 : C[nj])

    + branch_off_between(i, pi, nj, j);

  return ret = max(branch_off_now, branch_off_later);
}

// Minimax for the current player with last edge (pi -> i)
// and the other player with last edge (pj -> j).
int rec(int i, int pi, int j, int pj) {
  int ei = edge_id[i][pi];
  int ej = edge_id[j][pj];
  int &ret = memo_rec[ei][ej];
  if (ret != -1) return ret;

  if (i == j) {
    // The current player pick the next best path.
    int ni = next_best_except(i, pi, pj);
    // The other player pick the next next best path.
    int nj = next_best_except(i, pi, pj, ni);
    return ret = max_coins(ni, i) - max_coins(nj, j);
  }

  // The first option for the current player:
  // The current player pick the vertex ni
  // that leads to other player last vertex.
  int ni = next_node_to[i][j];
  int option1 = ((ni == j) ? 0 : C[ni]) - rec(j, pj, ni, i);

  // The second option for the current player:
  // The current player go to the best path other than ni.
  ni = next_best_except(i, pi, ni);
  int p1coins = max_coins(ni, i);
  // The other player branch off at any point
  // between vertex i and j (inclusive).
  int p2coins = branch_off_between(i, pi, j, pj);
  int option2 = p1coins - p2coins;

  // Pick the best outcome for the current player.
  return ret = max(option1, option2);
}

int main() {
  scanf("%d", &T);
  for (int TC = 1; TC <= T; TC++) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
      scanf("%d", &C[i]);
      con[i].clear();
    }
    id = 0;
    memset(edge_id, -1, sizeof(edge_id));
    for (int i = 0, j; i < N - 1; i++) {
      scanf("%d", &j); j--;
      con[i].push_back(j);
      con[j].push_back(i);
      edge_id[i][j] = id++;
      edge_id[j][i] = id++;
    }
    for (int i = 0; i < N; i++) {
      edge_id[i][N] = id++;
    }

    // These memoizations are reset per test case.
    memset(best_coins, -1, sizeof(best_coins));
    memset(best_nodes, -1, sizeof(best_nodes));
    memset(next_node_to, -1, sizeof(next_node_to));
    memset(memo_rec, -1, sizeof(memo_rec));
    memset(memo_branch_off, -1, sizeof(memo_branch_off));

    // Pre-calculation.
    for (int i = 0; i < N; i++) {
      precalc(i, N, i, N);
      for (int j : con[i]) precalc(j, i, i, j);
    }

    int max_diff = -1000000000;
    for (int i = 0; i < N; i++) {
      int min_diff = 1000000000;
      for (int j = 0; j < N; j++) {
        int cost = C[i] - (i == j ? 0 : C[j]);
        min_diff = min(min_diff, cost + rec(i, N, j, N));
      }
      max_diff = max(max_diff, min_diff);
    }
    printf("Case #%d: %d\n", TC, max_diff);
  }
}

Dựa trên phân tích chính thức của Google Code Jam.