VM15 round 2 đã kết thúc suôn sẻ, và trong thời gian ngắn nhất chúng mình sẽ đưa ra kết quả chấm bộ test chính thức.

Topic này mình lập ra để các bạn cùng nhau vào trao đổi trước khi solution của ban tổ chức được đưa ra. Bàn luận là một cách tốt để có thể nâng cao trình độ bản thân và sửa những sai lầm của mình trong round này, rút kinh nghiệm cho các round khác.

Nhất là bài VMSHAPE là một bài rất thú vị để các bạn trao đổi thuật toán :D

Cảm ơn các bạn đã tham gia kỳ thi VM15.

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.

Trả lời romqn1999
  Hiện bài gốc

Đâ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

Trả lời tungtp
  Hiện bài gốc

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

Trả lời anhhungcolao
  Hiện bài gốc

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.

Trả lời mofk_
  Hiện bài gốc

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

Trả lời batman12vn
  Hiện bài gốc

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

Trả lời anhhungcolao
  Hiện bài gốc

ý 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). 

Trả lời res
  Hiện bài gốc

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

Trả lời mofk_
  Hiện bài gốc

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

Trả lời mofk_
  Hiện bài gốc

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

 

Trả lời mofk_
  Hiện bài gốc

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

Trả lời iamquang95
  Hiện bài gốc

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 @[email protected] 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.

Trả lời sorry_natsukagami
  Hiện bài gốc

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.