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.

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.

Nếu vậy thì tính f(n) là mất xấp xỉ O(n căn n) nhỉ @.@ Có cách nào tối ưu xuống O(n) không nhỉ @.@

nlogn mà bạn.

Chấm xong rồi nhaaaaaaaaaaaa

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.

Xin phép chứng minh cái vụ 1/2 nhé =)) mình đã hỏi được 1 red coder của codeforces 

Giả sử ta coi F(n) = 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

Mình có F(2) = 1/(1 * 2) = 1/2 nhé

Ta giả sử F(n) = 1/2, ta sẽ chứng minh F(n+1) = 1/2

Để ý F(n+1) = F(n) + 1/(n+1) * G(n+1) - K(n+1)

với G(n+1) = tổng các phân số 1/p sao cho gcd(n+1, p) = 1

và K(n+1) = tổng các 1/pq sao cho gcd(p, q) = 1; p < q <=n và p + q = n + 1

Do gcd(p, q) = 1 nên gcd(n + 1, p) = gcd(n+1, q) = gcd(p, q) = 1. (tính chất đồng dư thôi)

Như vậy nếu tồn tại  - 1/pq trong K(n+1) thì:

-1/pq = 1/(p+q) * (1/p + 1/q) = 1/(n+1) * (1/p + 1/q) tồn tại trong G(n+1)

Vì thế nên F(n) = F(n+1) = 1/2

Cho mình hỏi : max(M,N) ở bài swap nghĩa là sao ?

Do bài viết này nhiều lứa tuổi đọc nên em / mình / anh sẽ thống nhất xưng là mình.

Về thuật giải, mình chỉ nói sơ qua thuật VMSHAPE do các bài khác bạn "chipchip3412" đã trình bày rôi.

Thuật toán có 2 phần:

1. Chuyển màu về 0/1.

2. Xác định hình(gần đúng) mà các số bit 1 biểu diễn.

1) Trong tất cả các code, mình luôn tìm màu X sao cho chia thành 2 loại <= X và > X sao cho thỏa mãn điểu kiện nào đó. Trong khi thi mình lấy tổng trung bình min nhưng sau khi thi + gen test + check thì mình thấy để đơn giản là trung bình cộng lại tốt hơn hẳn cách phức tạp trên.

2) Ban đầu cách làm của mình cũng giống hệt "chipchip3412" là so tỉ lệ diện tích và lời giải này cũng được 42.5 điểm. Sau đó mình thấy độ nhiểu ảnh hưởng quá nhiều nên mình duyệt 20 bán kính lớn nhất,tạo các đường viền vuông và tròn. Đường viền nào có tỉ lệ diện tích phủ cao nhất thì mình in ra. Nếu độ phủ <= 0.8 (lấy ước lượng) thì coi là hình tam giác. Lời giải này giúp mình ăn thêm 1 test trong lúc thi lên 45 điểm.

Sau khi thi mình đổi cách đặt màu thì lên 60 điểm (sửa có 1 dòng code - :sosad:).

Một số ý tưởng khác, đã cài nhưng không hiệu quả:

+ Quay các góc 1-90 độ cho hình vuông, vì hình vuông ở góc 45 độ trông rất giống hình tròn do tính chất của các tọa độ nguyên.

+ Vẽ đường viền, giữ các đường viền có chênh lệch 1/0 lớn nhất.

Tuy nhiên cả 2 sol này đều không hiệu quả vì độ nhiễu ảnh hưởng quá lớn tới hình mình tạo ra.

Cách tiếp cận của mình chỉ là xử lý các bit 0/1 và tọa độ nguyên nên độ chính xác không cao. Không biết có ai thạo về phần hình ảnh và nhận diện (recognition) có thể chia sẻ cách xử lý những bài dạng như thế này?

Mình có một số ý kiến về kỳ thi như sau

Bài VMSUM2, chỉ cần tìm đúng từ khóa sẽ ra Project Euler, ai từng làm ở đây sẽ biết cái vào xem thread và sẽ ra rất nhiều công thức, chọn một số công thức đủ tốt là có thể ăn bài này mà không mất công sức suy nghĩ. Mình thấy bài này ra là khá bất công khi người search được thì ăn dễ dàng, còn không thì phải tự lực cánh sinh thì cũng khá vất vả.

Bài VMSHAPE: Đây là một bài NP. Theo như mình thấy các bài NP thường sẽ được cho qua ít nhất 1 ngày đêm ( các kì VM trước thường để bài NP là 1,5 ngày ). Nhưng theo cách thi mới thì thời gian dành riêng cho bài NP thật sự là quá ít. Bài này mình định tạo generator + 100 local tests để đánh giá độ tốt của từng cách làm nhưng việc này mình chỉ có thể thực hiện được sau khi thi xong vì không đủ thời gian. Mong các admins có thể kéo dài thời gian nộp bài NP hơn so với các bài khác.

ad ơi sao bài VMRESTO của em chấm ở VM15 tới h vẫn được AC

Vậy mà khi nộp lên spoj thì lại báo 0đ là tại sao z ak 

Trên VM15 chấm test ví dụ thôi mà a @@