Phân tích

Năm ngoái, chúng tôi đã thử giải nhiều phiên bản khác nhau của bài toán này. Phải mất khá lâu mới hội tụ được về dạng bài cụ thể này; ngay cả sau khi chốt các yêu cầu hiện tại, vào lúc 2 giờ sáng đêm trước cuộc thi, chúng tôi vẫn còn điều chỉnh giới hạn đầu vào để bài toán thú vị hơn một chút. Bài toán kết hợp khéo léo quy hoạch động, tham lam và các khái niệm đồ thị như thành phần song liên thông và cây.

Bước đầu tiên là quyết định xem một cấu hình cụ thể có thể giải được hay không. Nếu đối với hai màu, các viên bi tương ứng của chúng nằm xen kẽ nhau (ví dụ: màu A, màu B, màu A, màu B), điều đó có nghĩa là hai cặp bi này cần được nối bởi các đường cong ở hai phía đối diện của đường nằm ngang \(y=0\). Chúng ta có thể xây dựng một đồ thị trong đó các nút đại diện cho các cặp bi cùng màu và tạo các cạnh giữa các cặp bi nằm xen kẽ nhau. Chúng ta có thể vẽ các đường đi mà không giao nhau khi và chỉ khi đồ thị này là đồ thị hai phía (bipartite).

Tiếp theo, đối với các cấu hình có thể giải được, chúng ta tính chiều cao tối thiểu. Đồ thị các cặp bi có thể có nhiều thành phần liên thông, và đối với mỗi thành phần như vậy, chúng ta có hai cách để vẽ các đường (với cặp bi đầu tiên ở trên đường \(y=0\) hoặc ở dưới nó). Vì vậy, tổng cộng chúng ta sẽ có \(O(2^{\text{số thành phần}})\) cấu hình. Ý tưởng này có thể giải được Small dataset nhưng quá tốn thời gian cho Large dataset.

Để giải quyết Large dataset, chúng ta cần sử dụng quy hoạch động. Trạng thái của chúng ta sẽ được xác định bởi left, right, height_up và height_down. Đối với mỗi trạng thái, chúng ta tính một giá trị boolean cho biết liệu bài toán con sử dụng tập hợp các viên bi có chỉ số từ left đến right có thể được giải quyết trong phạm vi chiều dọc \([-height\_down \dots height\_up]\) hay không. Việc tính toán giá trị này hơi phức tạp; điều chúng ta cần lưu ý là chúng ta có thể thử từng cách trong hai cách vẽ thành phần bắt đầu tại chỉ số left. Sau đó, một quan sát quan trọng là chúng ta có thể vẽ mỗi đường đi với chiều cao tối đa có thể nếu đường đó nằm trên trục X hoặc độ sâu tối đa có thể nếu đường đó nằm dưới trục X, miễn là bản vẽ của chúng ta nằm trong phạm vi chiều dọc \([-height\_down \dots height\_up]\). Sử dụng những ý tưởng này, chúng ta có thể đưa ra một thuật toán \(O(n^5)\).

Chúng ta có thể cải thiện giải pháp này bằng cách sử dụng trạng thái (left, right, height_up) và đối với mỗi trạng thái, tìm height_down nhỏ nhất để bài toán con [left .. right] có thể giải được. Bây giờ chúng ta nhận thấy rằng nên sử dụng quy hoạch động trên các cặp left và right nơi các thành phần liên thông của các viên bi bắt đầu và kết thúc. Điều này sẽ làm cho right được xác định duy nhất bởi left. Do đó, chúng ta đã giảm không gian trạng thái xuống còn \(O(n^2)\) trạng thái. Chúng ta cũng nhận thấy rằng các thành phần liên thông tạo thành một cấu trúc dạng cây, nơi chúng ta cần giải quyết các thành phần trong cùng trước rồi mới đến các thành phần bên ngoài, giống như việc duyệt các lá của cây trước và tiến dần về phía gốc. Bây giờ mỗi thành phần liên thông sẽ chỉ được phân tích một lần ở cấp độ thành phần phía trên, vì vậy thuật toán tổng thể sẽ mất thời gian \(O(n^2)\).

Dưới đây là giải pháp của Tomek Czajka:

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <map>
#include <string>
#include <vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
template<class T> inline int size(const T&c) { return c.size();}
const int INF = 1000000000;

int n; // number of types of marbles
vector<vector<int> > where; // [n][2]
vector<int> marbles; // [2*n]

void readInput() {
  char buf[30];
  map<string,int> dict;
  scanf("%d", &n);
  marbles.clear(); marbles.reserve(2*n);
  where.clear(); where.resize(n);
  for(int i=0;i<2*n;++i) {
    scanf("%s",buf);
    string s = buf;
    map<string,int>::iterator it = dict.find(s);
    int m;
    if(it==dict.end()) {
      m = size(dict);
      dict[s] = m;
    } else {
      m = it->second;
    }
    marbles.push_back(m);
    where[m].push_back(i);
  }
}

struct Event {
  int x,t;
  // t=0 start top, 1 end top
  // t=2 start bot, 3 end bot
};

vector<int> vis;

bool cross(int m1,int m2) {
  return
      where[m1][0] < where[m2][0] &&
      where[m2][0] < where[m1][1] &&
      where[m1][1] < where[m2][1] ||
      where[m2][0] < where[m1][0] &&
      where[m1][0] < where[m2][1] &&
      where[m2][1] < where[m1][1];
}

void dfs(int m,int sign) {
  if(vis[m]==sign) return;
  if(vis[m]==-sign) throw 0;
  vis[m]=sign;
  REP(i,n) if(i!=m && cross(m,i)) dfs(i,-sign);
}

vector<vector<Event> > cacheCalcEvents;

const vector<Event> &calcEvents(int startx) {
  vector<Event> &res = cacheCalcEvents[startx];
  if(!res.empty()) return res;
  vis.assign(n,0);
  dfs(marbles[startx],1);
  REP(x,2*n) {
    int m = marbles[x];
    if(vis[m]==0) continue;
    int nr=0;
    if(where[m][nr] != x) ++nr;
    assert(where[m][nr]==x);
    Event e; e.x=x;
    e.t = (1-vis[m]) + nr;
    res.push_back(e);
  }
  return res;
}

vector<vector<int> > cacheCalcH2;

int calcH2(int a,int b,int h1) {
  if(h1<0) return INF;
  if(a==b) return 0;
  int &res = cacheCalcH2[a][h1];
  if(res!=-1) return res;
  const vector<Event> &events = calcEvents(a);
  res = INF;
  for(int mask = 0; mask<=2; mask+=2) {
    int top=0, bot=0;
    int h2 = 0;
    REP(i,size(events)+1) {
      int alpha = i==0 ? a : events[i-1].x + 1;
      int beta = i==size(events) ? b : events[i].x;
      h2 = max(h2, calcH2(alpha, beta, h1 - top) + bot);
      if(i!=size(events)) {
        switch(events[i].t ^ mask) {
          case 0: ++top; break;
          case 1: --top; break;
          case 2: ++bot; break;
          case 3: --bot; break;
        }
      }
    }
    res = min(res, h2);
  }
  return res;
}

int solve() {
  int res = INF;
  cacheCalcH2.assign(2*n, vector<int>(n+1,-1));
  cacheCalcEvents.clear(); cacheCalcEvents.resize(2*n);
  try {
    REP(h1,n+1) {
      res = min(res, h1 + calcH2(0,2*n,h1));
    }
    return res;
  } catch(int) { return INF; }
}

int main() {
  int ntc; scanf("%d", &ntc);
  REP(tc,ntc) {
    readInput();
    int res = solve();
    if(res==INF) res = -1;
    printf("Case #%d: %d\n", tc+1, res);
  }
}

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