Experience Nov

ptree

*) do phuc tap la O(N^2)
C/m: https://codeforces.com/problemset/problem/815/C
Dpt la O( numChild[i] * numChild[j] ) -> O(N ^ 2)

*) trace
dùng trace ngược up[v][x] nghĩa là dp[ dad[v] ][ x ] dùng bao thằng ở con v

another problem: kingdom spoj

---

 

winrar algo :v

link đề, có m siêu cạnh a, b, t nghĩa là nối a -> b, a + 1 -> b + 1, a + 2 -> b + 2, …
hỏi có bao thành phần liên thông.

Sol:

O(m căn m):

gọi căn n = x,
tách mỗi siêu cạnh ra thành (a, b, x), (a + x, b + x, x), …
khi đó ta có m căn n cạnh, dùng kruskal đưa về tối đa n cạnh.
sau đó bung đám này ra có n căn n cạnh lại dùng kruskal tiếp.

O(n log)

với mỗi (a, b, t), gọi x = log2(t)
đưa (a, b, t) về (a, b, 2 ^ x) và (a + t – 2 ^ x, b + t – 2 ^ x, 2 ^ x)

xét từ tầng log cao nhất về cuối, trên mỗi tầng ta kruskal để đưa về n cạnh, sau đó, với mỗi (a, b, 2 ^ x) di truyền cho tầng dưới (a, b, 2 ^ (x – 1)) và ( a + 2 ^ (x – 1), b + 2 ^ ( x – 1), 2 ^ (x – 1)).

Bản chất:
dùng tính chất của kruskal, ko quan trọng số lượng input, output luôn <= n.

---

chia căn

dấu hiệu:

Q: bài nào làm đc chia căn ?
A: những bài có đọ phức tạp phụ thuộc, varied.

ví dụ: https://vn.spoj.com/problems/VMBW/
nếu làm trâu thì nó thành đpt O ( Q * deg(u) ) trong đó u là đỉnh được hỏi.
ví dụ: cho đồ thị vô hướng G = (V, E), đếm số tam giác.
thì nếu làm trâu nó cũng là O(N*deg(u)*deg(v))

Lợi thế:
Tự hỏi 1 đồ thị vô hướng bình thường thì có tính chất gì?
Ngoài cây cầu ra thì :v nah
chia căn sẽ giúp ta phân tập đỉnh ra làm 2 tập, nhỏ và to:
*) tập nhỏ: số đỉnh kề <= căn(n)  —-> có thể for trâu được
*) tập to    : số đỉnh to tối đa là căn(n)
từ đó cho ta biến một đồ thị bình thường G = (V, E) thành một đồ thị khá bựa.
Bên cạnh đó, ta còn có thể xây được mảng cạnh 2 chiều mà ko cần dùng đến vector, cụ thể:
Với tập cạnh (to – to): xây mảng N ^ 2
Với tập cạnh (to – nhỏ): xây mảng N căn ( N )
Với tập cạnh (nhỏ – nhỏ): for trâu.

---

lzs:

lcs2x thì quen thuộc với các bạn trẻ rồi, nhưng h, nếu hỏi là, số lượng dãy thỏa mãn độ dài dài nhất thì làm thế nào ?

dãy ở đây là xét về giá trị hén :v
và để cho đơn giản thì ta chỉ xét giá trị sau > giá trị trước trong dãy LCS.

Tư tưởng:
Với cách (N ^ 3), ta có thể for i = 1 -> n,  for j = 1 -> m, for k = i – 1 -> 1, và chỉ cập nhật khi a[k] xuất hiện lần đầu trong khoảng từ (k, i]

Lời giải:

Gọi F[i][j] = độ dài dài nhất xét dãy a[1..i] và b[1..j], và kết thúc tại b[j], còn kết thúc ở a thì ko biết.
Gọi Num[i][j] = số lượng dãy unique xét dãy a[1..i] và b[1..j], và kết thúc tại b[j], còn kết thúc ở b thì ko biết.

Nó phức tạp vcc. nên gắng đọc hiểu ha.
Gọi 2 dãy là a[1..n] và b[1..m]
Mình sẽ for i = 1 -> n.
Thêm 1 cái pair best, best.first lưu để dùng cho F, best.second lưu cho Num.
Do ta đang chốt vị trí i của dãy a, nên giả sử b[j] = a[i], thì rõ ràng F[i][j] sẽ luôn lấy cặp (a[i], b[j]), nên Num[i][j] lúc ấy cũng reset về 0 luôn, vì các lần xét ở trước vô nghĩa tại thời điểm này.
Còn giả sử a[i] > b[j], thì b[j] có thể là phần tử đứng trước của b[ j1 ] (j1 > j) mà a[i] = b[j1], nên cập nhật cho best hiện tại với F[i – 1][j]. Nên là tí nữa nếu đến j1, thì cập nhật F[i][j] với best sẽ hợp lí.
Vấn đề còn lại là dãy phải unique. Với tư tưởng ở trên, có thể thấy, nếu b[j] = b[k] (j < k) thì ta sẽ bị trùng, cách xử lý khá đơn giản, lưu lại vị trí của giá trị đó, nếu gặp lại thì mình trừ đi gía trị cũ chơi giá trị mới.

Code mẫu cho một bài tương tự, đọc hiểu concept thôi:
https://pastebin.com/PKtS86p2