Bài K thực chất là 1 bài cổ điển trong Machine Learning, bạn nào muốn biết có thể search với keyword "Association Rule Mining" hoặc "Frequent Itemset Mining".

Vì là bài cổ điển, và bài K này không có bất kỳ giới hạn nào đặc biệt (EDIT: chỗ này thực ra mình đọc thiếu đề đoạn số product <= 10,000 :))))), nên chắc chắn không có cách giải nào với độ phức tạp tính theo O là đủ nhỏ. Vì vậy chỉ có các thuật tương đối tốt với dữ liệu ngẫu nhiên có thể qua bài này. Trong ML thì thuật toán thông dụng nhất cho bài này là Apriori:

• Đầu tiên với mỗi số, đếm số lượng lần xuất hiện của các product. Sau bước này mình loại tất cả các product có số lần xuất hiện < T. Gọi các product còn lại là product tốt.
• Tiếp theo là duyệt trên các product tốt: với mỗi customer. Dùng 1 map< pair<int,int>, int > để đếm số lần xuất hiện của từng cặp.

Cách này đủ để AC bài K, ko cần tối ưu thêm chỗ nào cả.

Đây là thuật giải bài K của mình, team MEGABYTE.
Coi mỗi cặp đồ vật - người mua là 1 điểm có tọa độ (x, y), sort lại các điểm tăng dần theo x.
Giả sử cố định được 2 cặp tọa độ x1, x2, cần xem có bao nhiêu tọa độ y chung, tạm gọi là K, nếu K >= T thì có kq++.
Cái này mình sử dụng sweepline như sau
 

int i = 1;
int n = số điểm; p[n+1].x = inf;
int dem = 0;
while (i <= n) {
	int j = i;
	while (j <= n && p[i].x == p[j].x) dd[p[j++].y] = 1;
	for(int k = j; k <= n+1; k++) 
		if (p[k].x == p[k-1].x) {
			if (dd[p[k].y]) {
				dd[p[k].y] = 0; backup.push_back(p[k].y); dem++;
			}
		} else {
			if (dem >= T) res++;
			for(int jj = 0; jj < sz(backup); jj++) dd[backup[jj]] = 1;
			backup.clear(); dem = 0;
			if (dd[p[k].y]) {
				dd[p[k].y] = 0; backup.push_back(p[k].y); dem++;
			}
		}
	for(int k = i; k < j; k++) dd[p[k].y] = 0;
	i = j;
}

Độ phức tạp O(N + (số tọa độ x phân biệt)²)

 

Bài D thấy nhiều bạn hỏi nên mình cũng xin chia sẻ cách làm của team MEGABYTE (mà bài này hình như có mỗi một cách :v)

Đây là thuật toán tham lam, các bước làm của nó như sau:

1/ Giả sử mình cần cắt xâu s[i..N] (ban đầu i = 1). Tìm j lớn nhất sao cho tất cả các ký tự từ i+1 đến j đều lớn hơn s[i]. Dễ thấy ta không thể cắt tại vị trí nào < j vì xâu sau đó sẽ có thứ tự từ điển lớn hơn xâu vừa cắt.

2/ Tìm k lớn nhất sao cho s[i..i+k-1] = s[j+1..j+k] (tiền tố chung dài nhất). k có thể bằng 0.

3/ Xét s[j+k+1], bản chất là ký tự đầu tiên khác nhau của 2 xâu con s[i..N] và s[j+1..N]. Có 2 trường hợp sau:

    + s[j+k+1] < s[i+k], khi đó ta bắt buộc phải cắt tại j, vì nếu cắt tại vị trí > j thì xâu được cắt không phải là xâu minion. Ta cũng thể cắt tại vị trí < j như đã nói ở bước 1.

    + s[j+k+1] > s[i+k], khi đó ta không thể cắt tại vị trí < j+k+1 vì hoặc xâu sau có thứ tự từ điển lớn hơn xâu vừa cắt hoặc xâu vừa cắt không phải là xâu minion. Vậy ta phải cắt tại vị trí >= j+k+1. Ta sẽ quay trở lại bước 1, tiếp tục tìm ký tự đầu tiên <= s[i], tìm tiền tố chung dài nhất (bước 2), và xét ký tự khác nhau (bước 3).

Cứ lặp như vậy cho đến khi cắt hết xâu. Đpt là O(N log N) vì bọn mình dùng hash và chặt nhị phân để tìm tiền tố chung dài nhất (mất O(log N)). Có thể cải tiến xuống O(N) bằng những cách tìm tiền tố chung dài nhất O(1), nhưng có lẽ không cần thiết trong bài này =))

bạn chip giỏi quá :( mình thật vinh dự khi được làm teammate của bạn 

Hình như bạn nhầm độ phức tạp thì phải :))

Độ phức tạp tối đa là O(N²) nếu không tính mấy cái phụ linh tinh, có thể thấy 2 vòng i j có tổng là O(N), vòng for k cũng là O(N) nên tối đa là O(N²) :-?

Cho em hỏi là bài B làm như thế nào ạ? :D