Hướng dẫn cho A-Skew-ed Reasoning
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Dưới đây là phân tích chi tiết về cách tìm chuỗi đầu vào (input sequence) cực tiểu và cực đại về mặt từ điển (lexicographical) để tạo ra một cấu trúc Skew Heap cho trước.
1. Ý tưởng cốt lõi (Core Idea)
Để tìm chuỗi đầu vào, chúng ta sẽ thực hiện duyệt cây một cách đệ quy bắt đầu từ nút gốc.
Giả sử ta đang ở nút gốc (giá trị là 1) và cần xác định vị trí của nút này trong chuỗi đầu vào:
- Dựa trên cơ chế chèn của Skew Heap: Mọi phần tử xuất hiện sau nút gốc 1 sẽ xen kẽ (alternate) giữa việc đi vào cây con bên trái và cây con bên phải.
- Phần tử đứng trước gốc: Mọi phần tử đứng trước nút gốc 1 trong chuỗi phải nằm hoàn toàn ở cây con bên trái hoặc hoàn toàn ở cây con bên phải (tùy thuộc vào tính chẵn lẻ của vị trí nút gốc).
2. Các bước thực hiện
Bước 1: Tính toán vị trí khả thi
Dựa trên kích thước (size) của cây con bên trái và cây con bên phải, ta có thể tính toán được các vị trí có thể đặt nút gốc. Thông thường sẽ có từ 0 đến 2 vị trí khả thi:
- Nếu có 2 vị trí, chúng luôn là hai vị trí đầu tiên của chuỗi.
- Tối ưu từ điển:
- Chọn vị trí thứ nhất để xây dựng chuỗi nhỏ nhất (lexicographically minimal).
- Chọn vị trí thứ hai để xây dựng chuỗi lớn nhất (lexicographically maximal).
Bước 2: Đệ quy và Hợp nhất (Merge)
Tại mỗi nút, ta đệ quy xuống hai cây con để xây dựng các chuỗi cực tiểu/cực đại tương ứng. Sau đó, tiến hành hợp nhất chúng dựa trên các quan sát về tính xen kẽ đã nêu ở trên.
3. Tối ưu độ phức tạp (Complexity)
Với số lượng nút lên tới \(N = 2 \cdot 10^5\), một thuật toán duyệt thông thường dễ dẫn đến \(\mathcal{O(N^2)}\). Để đạt được tốc độ cần thiết, chúng ta áp dụng kỹ thuật:
- Interleaving (Đan xen): Việc kết hợp chuỗi từ cây con trái và phải thực chất là đan xen chuỗi ngắn hơn vào một hậu tố (suffix) có độ dài tương đương của chuỗi dài hơn.
-
Độ phức tạp: Do mỗi phần tử chỉ thuộc về chuỗi ngắn hơn trong một phép hợp nhất tối đa \(\log(N)\) lần (tương tự tư tưởng Small-to-Large merging), tổng thời gian thực thi đạt:
\[\mathcal{O}(N \log N)\]
4. Kết luận
Đây là một cách tiếp cận cực kỳ hiệu quả về mặt bộ nhớ và thời gian. Thực tế, lời giải tối ưu cho bài toán này (Judge solution) chỉ tốn khoảng 1197 bytes mã nguồn nhưng xử lý mượt mà với dữ liệu lớn.
Code mẫu
#include <bits/stdc++.h>
using namespace std;
struct Task {
int u;
bool isMin;
long long base, step;
long long start, len;
};
long long ceil_div_ll(long long a, long long b){
if(a >= 0) return (a + b - 1) / b;
else return - ((-a) / b);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin >> n)) return 0;
vector<int> L(n+1), R(n+1);
for(int i = 1; i <= n; i++){
cin >> L[i] >> R[i];
}
vector<int> sz(n+1, 0);
for(int i = n; i >= 1; i--){
sz[i] = 1 + (L[i] ? sz[L[i]] : 0) + (R[i] ? sz[R[i]] : 0);
}
vector<char> minA(n+1), maxA(n+1);
bool ok = true;
for(int u = 1; u <= n; ++u){
int nl = L[u] ? sz[L[u]] : 0;
int nr = R[u] ? sz[R[u]] : 0;
if(nl == 0 && nr > 0){
ok = false;
break;
}
bool opt1 = (nl >= 1 && nl <= nr + 1);
bool opt2 = (nl >= nr);
if(!opt1 && !opt2){
ok = false;
break;
}
if(opt1 && opt2){
if(nl == nr + 1){
minA[u] = 1; maxA[u] = 0;
}
else if(nl == nr){
minA[u] = 0; maxA[u] = 1;
}
else{
minA[u] = 0; maxA[u] = 1;
}
}
else if(opt1){
minA[u] = maxA[u] = 1;
}
else{
minA[u] = maxA[u] = 0;
}
}
if(!ok){
cout << "impossible\n";
return 0;
}
auto fill_mode = [&](bool isMin){
vector<int> res(n, 0);
vector<Task> st;
st.reserve(2*n + 10);
st.push_back({1, isMin, 0, 1, 0, (long long)sz[1]});
while(!st.empty()){
Task t = st.back();
st.pop_back();
int u = t.u;
if(u == 0 || t.len <= 0) continue;
long long base = t.base, step = t.step;
long long start = t.start, len = t.len;
long long end = start + len;
int l = L[u], r = R[u];
if(l == 0 && r == 0){
res[base] = u;
continue;
}
bool ALeft = isMin ? minA[u] : maxA[u];
int A = ALeft ? l : r;
int B = ALeft ? r : l;
int nA = A ? sz[A] : 0;
int nB = B ? sz[B] : 0;
long long k = ALeft ? (long long)(nB - nA + 1)
: (long long)(nB - nA);
long long bL = max(0LL, start);
long long bR = min(end, k);
if(B && bL < bR){
st.push_back({
B, isMin,
base + step * (bL - start),
step,
bL,
bR - bL
});
}
if(start <= k && k < end){
res[base + step * (k - start)] = u;
}
long long lowA = max(0LL, ceil_div_ll(start - (k+1), 2));
long long highA = min((long long)nA, ceil_div_ll(end - (k+1), 2));
if(A && lowA < highA){
st.push_back({
A, isMin,
base + step * ((k+1 - start) + 2*lowA),
step * 2,
lowA,
highA - lowA
});
}
long long remB = max(0LL, (long long)nB - k);
long long lowB = max(0LL, ceil_div_ll(start - (k+2), 2));
long long highB = min(remB, ceil_div_ll(end - (k+2), 2));
if(B && lowB < highB){
st.push_back({
B, isMin,
base + step * ((k+2 - start) + 2*lowB),
step * 2,
k + lowB,
highB - lowB
});
}
}
return res;
};
vector<int> resMin = fill_mode(true);
vector<int> resMax = fill_mode(false);
for(int i = 0; i < n; i++){
if(i) cout << ' ';
cout << resMin[i];
}
cout << "\n";
for(int i = 0; i < n; i++){
if(i) cout << ' ';
cout << resMax[i];
}
cout << "\n";
return 0;
}
Bình luận (4)