Rất mong những bạn điểm cao bài VMCUT chia sẻ cách làm. Những bài tốt nhất của các bạn còn chạy tốt hơn cả BTC :D

Bài VMDAOBIT, subtask 1 (40 điểm): Greedy. Thấy ô \(3*3\) nào có nhiều số \(1\) nhất thì đảo, độ phức tạp \(O(n^{3})\). Lưu ý các trường hợp \(m,n<3\) (có cái này chắc được khoảng 10 điểm)
P/S: Chỉ làm được thế thôi :(

bài vmdaobit O(n2) :duyệt lần lượt từng hàng và từng ô trên 1 hàng. Giả sử mình đã đảo đúng tất cả các ô trước ô i,j. Đến ô i,j nếu a[i,j] vẫn =1 thì đảo ô 3*3 có góc trái trên là i,j . Nhận xét thấy vì mình đã duyệt qua tất cả những ô có khả năng thay đổi ô i,j nên cách duy nhất để chuyển ô i,j về 0 là đảo ô 3*3 ở chính nó :)

Mình hiểu thế này có đúng không?
Ban đầu ta có thế này
1 1 0 1 1
1 1 0 1 1
1 0 1 0 1
0 1 1 1 0
0 1 1 1 0
Duyệt đến a[1,1]=1
Đảo ô 3*3 ở (1,1) ta được
0 0 1 1 1
0 0 1 1 1
0 1 0 0 1
0 1 1 1 0
0 1 1 1 0
Duyệt tiếp đến a[1,3]=1
Đảo ô (1,3) ta được
0 0 0 0 0
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
Duyệt tiếp đến a[3,2]=1
Đảo ô 3*3 ở (3,2) ta được một bảng 5*5 toàn số 0 và in dãy thao tác
Nếu duyệt đến ô cuối cùng vẫn còn số 1 thì in ra -1

Các bạn cho mình hỏi bài VMSALARY làm như thế nào ạ ?

Ban đầu, bạn chuyển biểu diễn cây sang biểu diễn mảng bằng cách dfs. Với mỗi cây con gốc u thì luôn tương ứng với một đoạn nào đó trong mảng mà ta sinh ra. Khi đó, vẫn đề chính của bài toán là cho một đoạn cho trước, đếm số phần tử < k. Đây là bài KQUERY.

Bài VMSALARY:

Gọi: 

• ch[x] = số con của cây con gốc x tính cả x.
• res[x] = số nút con có lương nhỏ hơn nút x.

Sort tiền lương từ nhỏ đến lớn. Duyệt từ nút có tiền lương nhỏ đến lớn:

•  Xét tại đỉnh t có giá trị k: res[t] = res[t] - ch[t] + 1. (vì số lượng con của cây t sau này sẽ update lên t ).
• ch[x] = ch[x] - 1 (với x nằm trên đường đi từ 1 đến cha[t]).
• res[x] = res[x] + 1 (với x nằm trên đường đi từ 1 đến cha[t]).

Cuối cùng kết quả là: sum [ res[x] * (res[x] - 1) / 2 ]

Việc cập nhật mảng ch[ ] và res[ ] nếu thông thường rất chậm O(N). Nhưng nếu áp dụng cấu trúc dữ liệu Heavy Light Decomposion thì việc cập nhật chỉ mất O(logN * logN).

* Có thể chỉ cần cập nhật mảng ch[ ] còn mảng res[ ] chỉ cần đánh dấu và dùng dfs để tính sau, còn cập nhật cả 2 mảng có thể chậm hơn xíu.

Tài liệu tham khảo:

Tiếng anh: http://wcipeg.com/wiki/Heavy-light_decomposition

• http://blog.anudeep2011.com/heavy-light-decomposition/

Tiếng việt(vnoi): http://vnoi.info/forum/5/5012/

Đơn giản thế mà không nghĩ ra nhở, cảm ơn nha.

Bài VMSALARY , Dùng DFS , mỗi lần duyệt đến 1 đỉnh thì push đỉnh đó vào stack , ta lưu lại thời điểm duyệt đến và duyệt xong của đỉnh u là s[u]  và f[u] , giờ trên stack tập các con của đỉnh u là 1 đoạn từ s[u] - > f[u] liên tiếp . Ta áp dụng như bài Kquery để làm. Bài KQUERY các bạn có thể xem ở ĐÂY

Bài VMCUT mình thử rất nhiều phương án khác nhau từ random đến greedy nhưng kết quả đều kém. Trong khi có rất nhiều bài > 90 điểm, phương pháp là gì vậy các bạn nhỉ ?

Trong bài VMSALARY mình sử dụng IT và mình xin được chia sẽ các bạn một cách cài đặt ngắn gọn và hiệu quả như sau:

int T[MAX * 2];

void update(int i) {
	for (i += n; i > 0; i >>= 1) {
		T[i]++;
	}
}

int get(int l, int r) {
	int cnt = 0;
	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
		if (l & 1) cnt += T[l++];
		if (r & 1) cnt += T[--r];
	}
	return cnt;
}

Với cách cài đặt này, chúng ta chỉ cần chứa tối đa số đỉnh là 2 * n (thay vì 4 * n), và hơn nữa là không dùng đệ quy nên sẽ nhanh hơn cách cài đặt thông thường. Các bạn đọc thêm tại đây.

VMCUT mình chỉ đơn giản là lần lượt lấy 1 đỉnh kề với H hiện tại mà nếu kết nạp sẽ tăng D(H) nhiều nhất

cách làm rất đơn giản và mình rất sốc khi mình sub đc > 100 @@

"Việc cập nhật mảng ch[ ] và res[ ] nếu thông thường rất chậm O(N). Nhưng nếu áp dụng cấu trúc dữ liệu Heavy Light Decomposion thì việc cập nhật chỉ mất O(NlogN)."

Việc cập nhật chỉ mất O(logN) thôi chứ bạn?

cám ơn bạn, mình đã edit :D

chuẩn rồi :3

chỉ lưu ý là không duyệt tất cả bảng nha ;)) 

thế bài này chỉ cần O(n^2) là AC ạ

O(n^2*9) =)))

Mà bằng tuổi nhau xưng ạ nghe kinh =))

mình tg anh  :)))))

vậy chỉ cần chạy 2 vòng for gặp =1 thì dảo bit mảng 3*3

nếu =0 hết thì in ra kq ko thì in ra -1

còn n hoặc m <3 thì cx in ra -1 :))))

đúng ko :))) nhưng t làm sao chỉ đc 40 nhỉ

Bài VMPIZZA để ăn sub 1 thì dùng thuật toán Quy hoạch động O(N^2).

Gọi F(i) là năng lượng tối đa có thể nhận được khi ăn Pizza từ 1 đến i.

Đầu tiên, sắp các pizza tăng dần theo t.

Có i cách để lấy Pizza thứ i. Với j từ 0 đến i-1, nếu lấy Pizza i cùng lượt với Pizza từ j+1 đến i thì tổng năng lượng là F[j]+sum(a[k]-(t[i]-t[k])*b[k]) (với k = j+1...i).

Kết quả cuối cùng là F(n)

Còn sub 2 thì em bó tay. Có thánh nào biết làm sub 2 không @@