Hôm nay bài khá lằng nhằng, mình sẽ cố gắng chữa thật nhiều bước.

Tóm tắt đề bài

Heap on Trees, NAIPC 2017, bài D

Cho một cây \(N\) đỉnh, mỗi nút có một số \(A_i\). Tìm tập con các nút lớn nhất thỏa mãn nếu \(i\) là tổ tiên của \(j\) và \(i\), \(j\) đều được chọn thì \(A_i > A_j\).

Giới hạn

\(1 \le N \le 10^5\), \(1 \le A_i \le 10^9\)

Pieces of Parentheses, NAIPC 2017, bài A

Cho \(N\) dãy ngoặc (không nhất thiết đúng), chọn ra một tập con các dãy ngoặc sao cho có thể ghép lại thành dãy ngoặc đúng dài nhất.

Giới hạn

\(1 \le N \le 300\), \(1 \le |S_i| \le 300\)

Problem Buyer, CCPC 2016-2017 Finals, bài E

Trên trục tọa độ cho \(N\) điểm \(C_i\) và \(M\) đoạn thẳng \([A_i, B_i]\). Tìm \(K\) nhỏ nhất sao cho với mọi tập con độ lớn \(K\) của tập đoạn thẳng ta luôn tìm được cặp ghép hoàn hảo của tập điểm với đoạn thỏa mãn:

• Mỗi điểm ghép với đúng 1 đoạn thẳng
• Mỗi đoạn thẳng ghép với tối đa 1 điểm
• Nếu \(C_i\) ghép với \([A_j, B_j]\) thì \(A_j \le C_i \le B_j\).

Giới hạn

\(1 \le N, M \le 10^5\), \(1 \le A_i \le B_i \le 10^9\), \(1 \le C_i \le 10^9\).

Lời giải

Heap on Trees

Xác định phương hướng

Ta bắt đầu với một hàm quy hoạch động “trâu” chưa cần thiết thỏa mãn giới hạn. Gọi \(F[v][j]\) là số đỉnh lớn nhất ta có thể chọn ở cây con gốc \(v\) với giới hạn các số là \(j\). Dễ dàng nhận thấy để tính \(F[v][j]\), ta lần lượt tính tổng \(F[u][j]\) với \(u\) là con của \(v\). Ngoài ra nếu \(A[v] \le j\) ta có một cách chọn là \(A[v]\) cùng với tổng các \(F[u][A[v] - 1]\). \[F[v][j] = \max(\sum\limits_{u \in child[v]} {F[u][j]}, (A[v] \le j) \times (1 + \sum\limits_ {u \in child[v]}{F[u][A[v] - 1]}))\] Đáp số chính là \(F[root][inf]\).

Sau khi nén số, ta có hàm quy hoạch động \(O(n^2)\). Ta sẽ tập trung vào cải tiến hàm quy hoạch động này.

Số giá trị khác nhau

Xét một lá \(v\). Hiển nhiên \(F[v][j]\) chỉ có 2 giá trị khác nhau với mọi \(j\): 0 khi \(A[v] < j\) và 1 nếu ngược lại.

Khi cộng 2 hàm có 2 miền giá trị, ta sẽ được một hàm có 3 miền giá trị. Tổng quát hơn, khi cộng 2 hàm có \(x\) và \(y\) miền giá trị, ta được một hàm có \(x + y - 1\) miền giá trị.

Nếu ta coi \(F\) mỗi lá là một hàm có 2 miền giá trị, thì một cây con gốc \(v\) sẽ có \(F\) là một hàm có \(size[v] + 1\) miền giá trị, với \(size[v]\) là kích cỡ của cây con gốc \(v\).

Ngoài ra, xét các vị trí thay đổi giá trị của các hàm. Ta nhận thấy khi cộng 2 hàm có \(x\) và \(y\) miền giá trị, ta nhận được một hàm có \(x + y - 1\) miền giá trị, trong đó các mốc chính là các mốc thay đổi giá trị của 1 trong 2 hàm số hạng. Như vậy, trong hàm \(F[v]\), các điểm mốc chính là các giá trị \(A[u]\) với \(u\) là nút trong cây con gốc \(v\).

Như vậy, từ một đỉnh \(v\), ta có thể dựng hàm \(F[u]\) với \(u = parent[v]\) bằng cách “gộp” giá trị hàm \(F[v]\) vào \(F[u]\).

Gộp hàm

Giả sử ta có \(F[v]\) với \(k\) mốc giá trị \(X_1, X_2, …, X_k\), ta phải gộp vào hàm \(F[u]\) (\(u\) là cha của \(v\)). Theo đúng công thức quy hoạch động, giá trị của \(F[v][X_i]\) sẽ được cộng vào các \(F[u][p]\) thỏa mãn \(X_i \le p < X_{i + 1}\), hay \(X_i \le p \le N\) nếu \(i = k\).

Tất nhiên, hàm \(F[u]\) cũng sẽ có các mốc \(Y_1, Y_2, …, Y_l\) (\(X \subseteq Y\)). Nếu coi \(F[u]\) như một IT, ta có thể update bằng cách:

int left = lower_bound(Y.begin(), Y.end(), X[i]) - Y.begin();
int right = lower_bound(Y.begin(), Y.end(), X[i + 1]) - 1 - Y.begin();
F[u].add(left, right, F[v][X[i]]); // Thêm F[v][X[i]] vào đoạn [left..right]

Sau đó ta cần cập nhật trường hợp chọn \(u\). Tất nhiên khi chọn \(u\), tổng đáp số của cây con gốc \(u\) sẽ là \(ans = (\max\limits_{i = 1}^{i < A[u]}{F[u][i]}) + 1\). Ta cần gán f[u][i] = max(f[u][i], ans) với mọi \(i \ge A[u]\). Tuy nhiên, do \(F[u]\) là hàm tăng, thực chất ta chỉ cần cộng 1 vào các vị trí từ \(A[u]\) đến trước vị trí \(x\) có \(F[u][x] = ans\).

int ans = F[u].get(A[u] - 1); // hàm tăng
int right = F[u].lower_bound(ans) - 1;
F[u].add(A[u], right, 1);

Các bước gộp hàm đã hoàn chỉnh. Tuy nhiên, độ phức tạp vẫn chưa thay đổi. Ta cần một bước tiếp theo: thuật toán gộp set (hay gộp IT).

Thuật toán tập lớn - bé

Xét bài toán: Cho \(N\) tập hợp, lúc đầu mỗi tập hợp có 1 phần tử. Để chuyển các phần tử từ tập hợp \(A\) sang tập hợp \(B\), ta mất chi phí \(|A|\). Xử lí các truy vấn ghép tập hợp.

Cách giải bài toán rất đơn giản: với mỗi truy vấn ta chỉ cần chuyển tất cả phần tử từ tập nhỏ hơn vào tập lớn hơn, và tổng chi phí sẽ là \(O(N\log{N})\). Tại sao?

Gọi \(s(p)\) là độ lớn của tập hợp chứa phần tử \(p\). Mỗi lần ta chuyển phần tử \(p\) từ tập \(X\) sang tập \(Y\) (\(|X| \le |Y|\)), \(s(p)\) tăng ít nhất gấp đôi. Tuy vậy, \(s(p)\) không thể vượt quá \(N\) do chỉ có tổng cộng \(N\) phần tử. Vì thế \(p\) không thể bị chuyển quá \(\log{N}\) lần. Mỗi phần tử không bị chuyển quá \(\log{N}\) lần, nên tổng chi phí vận chuyển không thể quá \(N\log{N}\).

Áp dụng vào bài toán ban đầu

Để ý khi ta gộp \(F[v]\) vào \(F[u]\), chi phí là \(size[v] \times \log{N}\) và \(size[u]\) tăng thêm \(size[v]\), giống với việc gộp set. Vì vậy ta có thể cải tiến thuật toán như sau. Giả sử ta đã tính xong mọi \(F[v]\) với \(v\) là con của \(u\):

• Gán \(F[u] = F[v_1]\) (đây là phép gán con trỏ \(O(1)\)).
• Với mỗi \(v\) tiếp theo:
  • Nếu \(size[u] < size[v_i]\), tráo \(F[u]\) và \(F[v_i]\) (phép tráo con trỏ \(O(1)\)).
  • Cập nhật \(F[v_i]\) vào \(F[u]\).
• Cập nhật đáp số khi chọn \(u\) như trên.

Ta sẽ có thuật toán \(O(N\log^2{N})\). Tuy vậy, do vẫn sử dụng IT nên bộ nhớ của ta vẫn có thể lên đến \(O(N^2)\).

IT bộ nhớ động

Việc biết trước kích thước tối đa và vị trí các phần tử của IT cho phép ta dựng lên cây IT chỉ với \(\min(2N, \log{N} * size)\) nút. Việc dựng nên IT này khá đơn giản, ta chỉ cần thay vì sử dụng \(2i\) và \(2i + 1\) là con của \(i\), ta lưu 2 con trỏ chỉ đến 2 nút trái và phải, và chỉ cấp phát bộ nhớ nếu cập nhật đến.

struct node {
  int val, sum; // dữ liệu của IT
  node *l, *r; // 2 con của IT*
  node() { l = r = NULL; val = sum = 0; }
};

#define mid ((l + r) >> 1)
void update(node &*v, int l, int r, int i, int j, int val) {
  if (l > j || r < i) return; // không dùng
  if (v == NULL) v = new node(); // chưa có v, cấp phát
  if (i <= l && r <= j) {
    v->val += val; v->sum += val;
    return;
  }
  // gọi đến bản gốc của con trỏ, chỉnh sửa trực tiếp
  update(v->l, l, mid, i, j, val);
  update(v->r, mid + 1, r, i, j, val);
  v->val = 0;
  if (v->l != NULL) v->val = max(v->l->val + v->sum, v->val);
  if (v->r != NULL) v->val = max(v->r->val + v->sum, v->val);
}

int get(node *v, int l, int r, int pos) {
  if (v == NULL) return 0; // chưa cấp phát, chứng tỏ không có giá trị gì
  if (l > pos || r < pos) return 0;
  if (l == r) return v->val;
  return max(get(v->l, l, mid, pos), get(v->r, mid + 1, r, pos)) + v->sum;
}
#undef mid

Do luôn chỉ có tổng cộng \(N\) mốc trên tất cả IT nên tổng bộ nhớ không quá \(O(N\log{N})\).

Ngoài ra để đảm bảo điều này ta cũng cần thực hiện xóa nút để giải phóng bộ nhớ. Ta có thể thực hiện điều này sau khi chuyển xong.

void clear(node &*v) {
  if (v == NULL) return;
  clear(v->l); clear(v->r);
  delete v;
}

Pieces of Parentheses

Thứ tự quy hoạch động

Thông thường để giải các bài ngoặc ta sẽ sử dụng quy hoạch động. Tuy nhiên, theo đề bài thì ta phải chọn một tập con có thứ tự, tức ta không có một thứ tự gốc để dựng hàm quy hoạch động.

Ý tưởng của ta sẽ là đi tìm một thứ tự để chạy phép qhđ.

Biểu diễn dãy ngoặc

Điều kiện một dãy ngoặc đúng là

• Số mở ngoặc bằng số đóng ngoặc
• Tại mọi thời điểm, số mở ngoặc không ít hơn số đóng ngoặc. Nói cách khác, nếu thay ( thành 1 và ) thành -1 thì tổng dồn luôn không âm.

Như vậy, thực chất với mỗi dãy ngoặc con, ta chỉ cần lưu lại 3 thông số: độ dài, vị trí có tổng dồn nhỏ nhất và tổng dồn cuối. Ta gọi 3 giá trị này là \(S_i\), \(A_i\) và \(B_i\).

Để tạo ra dãy ngoặc đúng từ các dãy ngoặc con thì:

• \(\sum\limits_{i = 1}^{k}B[i] = 0\)
• Với mọi \(i\), \((\sum\limits_{j = 1}^{j < i} B[j]) + A[i] \ge 0\)
• Tổng \(S_i\) là lớn nhất có thể.

Phân loại dãy ngoặc

Để đơn giản hóa việc sắp xếp thứ tự, ta có thể nghĩ đến việc phân loại các dãy ngoặc. Trong bài này ta sẽ phân thành 3 loại:

• \(A[i] \ge 0\). Hiển nhiên \(B[i] \ge 0\). Với các loại dãy ngoặc này đặt ở vị trí nào cũng thỏa mãn, vì vậy ta luôn đặt chúng ở đầu để tối đa hóa tổng \(B[j]\). Thứ tự từng thành phần là không quan trọng.
• \(A[i] < 0\) và \(B[i] \ge 0\). Hiển nhiên \(A[i]\) càng nhỏ càng nên đặt phía sau, bởi càng đứng sau thì tổng \(B[j]\) càng lớn, càng dễ thỏa mãn \(A[i]\). Ta đặt các dãy ngoặc loại này sau loại trên, sắp xếp các phần tử theo thứ tự \(A[i]\) giảm dần.
• \(A[i] < 0\) và \(B[i] < 0\). Đây là loại phức tạp nhất, ta sẽ cần một nhận xét để sắp xếp loại ngoặc này. Hiện giờ ta chỉ biết ta sẽ xếp chúng sau cùng.

\(A[i] < 0\) và \(B[i] < 0\)

Giả sử ta có một dãy ngoặc đúng chứa \(i\) và \(i + 1\) là 2 phần tử loại 3 liên tiếp trong dãy. Điều kiện sau là thỏa mãn:

• \(S + A[i] \ge 0\), với \(S\) là tổng các \(B[j]\) đứng trước.
• \(S + B[i] + A[i + 1] \ge 0\).

Từ đây ta có thể suy ra \(S + A[i + 1] \ge 0\) do \(B[i] < 0\).

Nếu \(B[i + 1] + A[i] \ge B[i] + A[i + 1]\), ta hoàn toàn có thể đổi chỗ \(i\) và \(i + 1\) bởi khi đó \(S + B[i + 1] + A[i] \ge S + B[i] + A[i + 1] \ge 0\), cả 2 điều kiện đều thỏa mãn.

Từ đó ta chứng minh được đáp án luôn tồn tại sao cho với mọi cặp \(i, j\) loại 3 ta đều có \(B[j] + A[i] \le B[i] + A[j]\), hay nói cách khác, \(A[i] - B[i] \le A[j] - B[j]\).

Như vậy, ta có thể sắp xếp các dãy ngoặc loại 3 theo thứ tự \(A[i] - B[i]\) tăng dần mà vẫn đảm bảo tìm được đáp án tối ưu.

Công thức qhđ

Khi đã có thứ tự, ta dựng công thức qhđ đơn giản: gọi \(f[i][j]\) là dãy ngoặc dài nhất ghép được từ các đoạn từ 1 đến \(i\) mà có bậc là \(j\). Ta chuyển trạng thái như sau:

• Không thêm đoạn \(i + 1\), chuyển đến \(f[i + 1][j]\).
• Thêm đoạn \(i + 1\), điều kiện là \(j + A[i + 1] \ge 0\), chuyển trạng thái đến \(f[i + 1][j + B[i + 1]]\), tăng thêm \(S[i + 1]\) đơn vị.

Ban đầu \(f[0][0] = 0\), đáp số là \(f[N][0]\).

Độ phức tạp là \(O(N^2 * |S|)\), thỏa mãn bài toán.

Problem Buyer

Thuật toán tham lam

Trước tiên ta cần phải biết thuật toán tham lam để tìm cặp ghép. Thuật toán như sau:

• Sắp xếp \(C_i\) tăng dần.
• Giữ một priority_queue<int, vector<int>, greater<int> >
• Duyệt từ 1 đến \(N\), khi đến \(i\) ta thêm hết các đoạn có \(L_x \le C_i\) vào queue.
• Tim phần tử trong queue có \(R_x\) nhỏ nhất mà \(\ge C_i\). Nếu có, ghép và xóa khỏi queue. Nếu không, không tồn tại cặp ghép đầy đủ.

Tạo ra tập sai

Thay vì đi tìm \(K\) nhỏ nhất sao cho mọi tập đều ghép được, ta sẽ đi tìm \(K’\) lớn nhất mà tồn tại 1 tập không ghép được. Đáp số sẽ là \(K’ + 1\).

Vị trí fail

Dựa theo thuật toán tham lam, ta nhận thấy chỉ cần ở 1 bước mà queue rỗng thì thuật toán sẽ fail. Như vậy, khi xác định được vị trí fail ta có thể dựng dãy bằng cách lấy tất cả các phần tử trừ các phần tử đứng trong queue hiện tại khi mô phỏng thuật toán.

Dễ dàng chứng minh đấy là cách tối ưu nhất để làm một bước \(i\) xác định nào đó fail. Như vậy, thuật toán của ta chỉ là mô phỏng lại thuật tham lam, mỗi bước ta xác định số phần tử phải xóa đi để bước đó fail (chính là số phần tử trong queue lúc đó), và tìm vị trí cần xóa ít phần tử nhất.

Đáp số sẽ là \(N - x\) với \(x\) là số phần tử bị xóa nhỏ nhất. Độ phức tạp là \(O(N \log{N})\).