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.