cái bài VMSHAPE e còn chưa dám đọc đề :3

Cho mình hỏi bài VM15SWAP làm thế nào nhỉ ? Với lại bài VMSUM2 nữa, bài này mình chỉ làm được thuật N^2.

Đây là bài dạng NP mà bạn, không có thuật toán tốt, mình nghĩ bạn nên đọc đề vì đề những bài NP rất thú vị, và cũng dễ kiếm vài điểm nữa :3 

Mấy anh cho em hỏi bài vm15swap dùng thuật j vậy em chỉ vét hết thôi :v

Đợi các bạn vào bàn luận :3 mình nói ra mất hay :3 

Bài VM15SWAP: coi mỗi hàng / cột là một đỉnh. để ý thấy việc swapRow(i, j) thực chất là đổi danh sách kề của i và j cho nhau trong đồ thị, tương tự swapCol(i, j) thực chất là đổi 2 đỉnh (M + i) và (M + j). Do đó, bài toán đưa về tìm clique cực đại trên đồ thị 2 phía. Ta có clique cực đại = tập độc lập cực đại trên đồ thị bù = M + N - (tập phủ đỉnh cực tiểu trên đồ thị bù) = M + N - (cặp ghép cực đại trên đồ thị bù) (theo Định lý Koenig). Túm lại đây là bài toán tìm cặp ghép cực đại.

có cách khác k bạn :))))

Mình nghĩ là không :D cách này rất tự nhiên mà.

Dù sao thì mình cũng truy vết tập độc lập sai nên chắc chả được điểm :))))

Cách truy vết (sau khi ăn chơi phè phỡn nghĩ ra nhưng không kịp code, hi vọng là sai cho đỡ tiếc):

- Chọn các đỉnh không nằm trong bộ ghép.

- Xóa các đỉnh kề với các đỉnh được chọn.

- Chạy lại cặp ghép với các đỉnh chưa được chọn, cũng chưa bị xóa.

- Lặp lại quá trình trên đến khi không chọn được đỉnh nào nằm ngoài bộ ghép.

- Chọn toàn bộ một phía nào đó của bộ ghép cuối cùng.

Btw, nếu em upsolve trên trang VM15 ngay bây giờ thì có đc chấm (ko tính vào kì thi) không ạ?

ý tưởng VMSUM2 , mình chưa code:

S(i) = S(i-1) + R(i)

R(i) =  R(i-1) + T(i) - T(i-1)

T(i): sum(1/p*q) thoả mãn: p+q=i hoăc q=i

Tính trước T(i) trong O(n^2). 

Tính t(i) trong N^2 vậy DPT chung là N^2 thì cũng chạy đâu có được bạn :3

Giờ bạn không submit được nữa rồi :D

Cách truy vết của wiki:

Coi tập hàng là L, tập cột là R nhé.

Trước tiên ta lấy U là tập các đỉnh trong L mà không có cặp ghép. Từ mỗi đỉnh của U ta dựng các "alternating path" (các đường nối bởi các cạnh so le có / không trong cặp ghép). Sau đó, clique sẽ là các đỉnh có trong L và có trong ít nhất 1 path + các đỉnh có trong R mà không ở trong path nào

Trong thời gian ngắn nhất chúng mình sẽ up những bài này lên VOJ cho các bạn submit :3

Mình thấy có người làm n log n bài SUM2 mà không ac, vậy thì sol AC là O(n) sao?

Chấm xong rồi nhaaaaaaaaaaaa

Bài VMSHAPE tính điểm thang giảm theo log giống như round 5 năm ngoái hả bạn?

Hóng thuật chuẩn bài VMSUM2 @.@ Ngồi nghĩ cả chiều không ra :(

Một vài ý tưởng thuật toán của mình :)

VM15SWAP: Thuật toán của mình cũng giống của bạn mofk_, mà thực tế mình cũng nghĩ đây là cách duy nhất. Đề còn cho thêm cái điều kiện đáp số > max(m, n) có vẻ như để support thuật toán này nữa =)) Bởi vì nếu không có điều kiện đó có khả năng biclique chọn được lấy toàn hàng hoặc toàn cột. Mình bổ sung cách truy vết là tìm min cut nhé, đỉnh nào không bị cắt thì đỉnh đó thuộc biclique.

VMSUM2: Bài này mình ngồi khảo sát cả chiều và ra được tính chất vô cùng ảo diệu: tổng tất cả các 1 / pq với p q nguyên tố cùng nhau, p < q <= m và p + q > m, cái tổng này bằng 1 / 2 =)) Ai giúp mình nhé mình chẳng biết chứng minh thế nào đâu :v Từ tính chất này, biến đổi một hồi bài toán chuyển thành tính tổng tất cả các 1 / pq với p q nguyên tố cùng nhau, p < q <= m (bỏ điều kiện p + q). Lấy kết quả tính được cộng với (n - 2) / 2 sẽ ra đáp số. Để tính cái tổng đó thì dùng bao hàm loại trừ: (1/1 + 1/2 + 1/3 + ... + 1/n)^2 - (1/2 + 1/4 + 1/6 + ...)^2 - (1/3 + 1/6 + 1/9 + ...)^2 + (1/ 6 + 1/12 + 1/18 + ...) ^2 +- ...

VMSHAPE: Đầu tiên mình tách cái hình ra khỏi nền trước bằng cách loại tất cả các điểm có màu tối hơn màu trung bình và DFS để tìm thành phần liên thông lớn nhất còn lại, đó chính là cái hình. Sau đó, mình tìm trọng tâm của hình là điểm trung bình của tất cả các điểm thuộc hình, tính diện tích hình là bằng tổng số điểm thuộc hình, gọi là S, và tìm điểm xa trọng tâm nhất thuộc hình, gọi khoảng cách điểm này đến trọng tâm là R. Mình khảo sát tỉ lệ S / R^2, nếu là hình tròn thì xấp xỉ 3,14, hình vuông thì xấp xỉ 2, hình tam giác thì < 1,3. Vì cái hình sẽ không chính xác nên tỉ lệ thật sự của thuật toán này nhỏ hơn lí thuyết nhiều, chẳng hạn hình tròn mình toàn ra trên dưới 2 chứ chẳng bao giờ được 3,14 :v Do đó cần điều chỉnh các khoảng tỉ lệ cho hợp với thực tế thuật toán.

1. Tính f(n) là tổng 1/(p.q) mà (p, q) = 1, p + q = n.

2. Tính h(n) là tổng 1/(n.k) mà (n, k) = 1.

3. Khi đó R(n) = R(n - 1) - f(n - 1) + h(n).

Code: http://ideone.com/0Ej4wj.