2 năm, 2 tháng trước

Ban tổ chức chưa muốn công bố lời giải của các bài ngay vì muốn khuyến khích các bạn trao đổi và học tập lẫn nhau. Đó là cách rất nhanh và hiệu quả để các bạn biết cách làm các bài. Các bạn không làm được bài đừng ngần ngại hỏi, và các bạn làm được bài cũng chớ quên chia sẻ nhé :) 

Mời các bạn thảo luận về lời giải của các bài tập trong vòng vừa rồi :)

2 năm, 2 tháng trước

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

2 năm, 2 tháng trước

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 :(

2 năm, 2 tháng trước
Trả lời bvd
  Hiện bài gốc

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ó :)

2 năm, 2 tháng trước
Trả lời s34vv1nd
  Hiện bài gốc
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
2 năm, 2 tháng trước

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

2 năm, 2 tháng trước
Trả lời nguyenthethong
  Hiện bài gốc

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.

2 năm, 2 tháng trước

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

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

 

2 năm, 2 tháng trước
Trả lời s34vv1nd
  Hiện bài gốc

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

2 năm, 2 tháng trước

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

2 năm, 2 tháng trước

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ỉ ?

2 năm, 2 tháng trước
Trả lời youaremysky99
  Hiện bài gốc

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.

2 năm, 2 tháng trước
Trả lời RR
  Hiện bài gốc

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 @@

2 năm, 2 tháng trước
Trả lời sonlh07
  Hiện bài gốc

"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?

2 năm, 2 tháng trước
Trả lời iamquang95
  Hiện bài gốc

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

2 năm, 2 tháng trước
Trả lời bvd
  Hiện bài gốc

chuẩn rồi :3

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

2 năm, 2 tháng trước
Trả lời s34vv1nd
  Hiện bài gốc

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

2 năm, 2 tháng trước
Trả lời namjr
  Hiện bài gốc

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

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

2 năm, 2 tháng trước
Trả lời s34vv1nd
  Hiện bài gốc

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ỉ

2 năm, 2 tháng trước

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 @@