Ủa mình thấy bài Ellip max cù nhầy thôi chứ có gì đâu =)) IT lazy update thôi :v Code mình 315 dòng.

Cây IT của mình gồm có: Số hình còn lại trong khoảng, tổng A, tổng B, tổng A * B, min A, max A, min B, max B, vài cái mảng lazy nữa.

Mình không biết quản lí cái >A >B như thế nào cả

Bạn lưu thêm min A, max A, min B, max B ấy :v xong r` cứ xong 1 truy vấn, while min A < 1 xóa, while max A > A xóa, ...

Kinh khủng thế :| nghe cũng tưởng tượng ra 1-2 trăm dòng rồi

Vậy nên mình mới bảo bài này cù nhầy là chính =))

Bài Group bây giờ mình mới biết là lấy last submission chứ không phải best submission, đắng lòng quá :'(

Vậy nên mình mới bảo bài này cù nhầy là chính =))

Bài Group bây giờ mình mới biết là lấy last submission chứ không phải best submission, đắng lòng quá :'(

Ẹc em cũng đến giờ mới để ý :v

Mấy round trước toàn lấy best mà, với cả cũng giới hạn 20 submission rồi sao không lấy max nhỉ.

Ẹc em cũng đến giờ mới để ý :v

Mấy round trước toàn lấy best mà, với cả cũng giới hạn 20 submission rồi sao không lấy max nhỉ.

Lấy last cho bài NP, round trước cũng thế mà. Lấy last để các bạn không chơi trò submit 1 bầy, chỉ thay đổi 1 2 cái hằng số :v

Chiếu cố cho em round này được không anh :|

Kiểu như codeChef Long họ vẫn lấy max, nếu chỉ thay đổi hằng số thì 20 lần submit cũng không nhiều mà anh

Bạn lưu thêm min A, max A, min B, max B ấy :v xong r` cứ xong 1 truy vấn, while min A < 1 xóa, while max A > A xóa, ...

mình cũng làm kiểu IT, nhưng code quá dài, khó debug.

Cách tiếp cận các bài của mình:

Bài VMSQUARE: Có thể chứng minh được rằng các điểm X1 cần tìm chính là các điểm có tọa độ nguyên nằm trong hình vuông gồm 4 đỉnh A; D; B1 (đối xứng với B qua AD) và C1 (đối xứng với C qua AD). Cũng nhận thấy luôn rằng số điểm này đúng bằng số các điểm có tọa độ nguyên nằm trong hình vuông ABCD. Đáp án = S(hình vuông) + 1 - |số điểm nguyên nằm trên các cạnh| / 2 Pick's theorem.

Bài VMTOWN: Nhận xét được rằng với một cây ban đầu. Khi ta nối / xóa một cạnh u-v, chỉ các cạnh trên đường đi ngắn nhất trên cây từ u đến v (tức là đi từ u -> lca(u,v) ->v) bị ảnh hưởng. Các cạnh không thuộc bất cứ đường đi nào thuộc dạng trên sẽ là cầu. Sử dụng HLD ta chuyển về bài toán: cho một đoạn [l, r], tăng nhãn các số thuộc đoạn [u, v] +-1, đếm số các số có nhãn bằng 0. Cách cài đặt cho dạng truy vấn này tương tự bài AREA.

Bài VMELLIP: Ban đầu mình cũng cài Splay Tree và xóa từng ellip nhưng cài lazy sai và không debug được. Mình chuyển qua duyệt trâu nhưng có bỏ qua các ellip đã bị xóa bằng dis-join set và được 70 điểm. Code tham khảo: http://ideone.com/najHAJ Mình sửa từ code splay nên nhìn hơi dài còn thực tế code cũng không quá 50 dòng.

Bài: VMGROUP2:

Chuyển mô hình bài toán: Chia các đỉnh thành K nhóm bằng nhau. Đặt sao cho các cạnh nối trong mỗi nhóm là lớn nhất có thể. Kết quả bài toán ban đầu chính là M - tổng này.

Ban đầu mình tạo sol đặt random đến khi quá 0.95s thì thôi. Sol này được 100.4 điểm. Sau đấy mình chuyển qua cách thử đảo chỗ 2 đỉnh (x, y) thuộc 2 nhóm khác nhau. Để tránh local best mình sử dụng Simulated Annealing. Vì không có nhiều thời gian để test và cải tiến tốc độ nên mình được 109.2 điểm.

Sau khi thi mình tạo local test, lấy benchmark là sol được 100.4 điểm.

Vì time limit cho rất eo hẹp so với N (1s) nên cách của mình không thật sự hiệu quả. Sau khi thi mình có một số cải tiến về tốc độ:

1. Phép đổi chỗ 2 đỉnh có 2 cách: O(2 * n / k; 1) và O(1, deg(x) + deg(y)) trong đó deg(x) là số cạnh chứa x và O(2 * n . k, 1) nghĩa là tính chênh lệch trong O(2 * n / k) và đổi chỗ 2 đỉnh trong O(1). Nếu n * n / k < 2 * m thì mình dùng O(2 * n / k) còn ngược lại dùng O(1, deg(x) + deg(y)). Thực tế nếu dùng SA thì nên chọn cách O(1, deg(x) + deg(y)) vì rất ít khi chênh lệch tạo ra kết quả chấp nhận được. Lời giải được 1.092 của mình trong lúc thi dùng O(deg(x) + deg(y); deg(x) + deg(y))

2. Cải tiến copy mảng. Mình dùng số 64-bit để copy hai mảng nên tốc độ copy nhanh hơn 7 lần về mặt lý thuyết.

Có một cách khác là sinh random các hoán vị rồi đổi chỗ đến khi không tạo chênh lệch tốt nữa thì thôi. Cách này cũng tốt nhưng chỉ được khoảng 1.089 điểm.

Trong benchmark 50 tests, cải tiến về tốc độ ở 1s cho mình sol tốt nhất là 1.0927 và tổng các best là 1.0937

Mình nâng thời gian lên 3s thì best sol là 1.09482 là tổng các best là 1.09512.

Cách của mình khá đơn giản và có tốc độ cải tiến chậm. Không biết lời giải bài này của các bạn khác thế nào?

a có thể chứng minh cho e tại sao số điểm cần tìm lại nhận số điểm trong hình vuông là kq k ạ ?

em tìm ra cái này = cách dùng trâu r xem vài test thì thấy thế chứ em k hiểu tại sao cả :'( .

Cách tiếp cận các bài của mình:

Bài VMSQUARE: Có thể chứng minh được rằng các điểm X1 cần tìm chính là các điểm có tọa độ nguyên nằm trong hình vuông gồm 4 đỉnh A; D; B1 (đối xứng với B qua AD) và C1 (đối xứng với C qua AD). Cũng nhận thấy luôn rằng số điểm này đúng bằng số các điểm có tọa độ nguyên nằm trong hình vuông ABCD. Đáp án = S(hình vuông) + 1 - |số điểm nguyên nằm trên các cạnh| / 2 Pick's theorem.

Bài VMTOWN: Nhận xét được rằng với một cây ban đầu. Khi ta nối / xóa một cạnh u-v, chỉ các cạnh trên đường đi ngắn nhất trên cây từ u đến v (tức là đi từ u -> lca(u,v) ->v) bị ảnh hưởng. Các cạnh không thuộc bất cứ đường đi nào thuộc dạng trên sẽ là cầu. Sử dụng HLD ta chuyển về bài toán: cho một đoạn [l, r], tăng nhãn các số thuộc đoạn [u, v] +-1, đếm số các số có nhãn bằng 0. Cách cài đặt cho dạng truy vấn này tương tự bài AREA.

Bài VMELLIP: Ban đầu mình cũng cài Splay Tree và xóa từng ellip nhưng cài lazy sai và không debug được. Mình chuyển qua duyệt trâu nhưng có bỏ qua các ellip đã bị xóa bằng dis-join set và được 70 điểm. Code tham khảo: http://ideone.com/najHAJ Mình sửa từ code splay nên nhìn hơi dài còn thực tế code cũng không quá 50 dòng.

Bài: VMGROUP2:

Chuyển mô hình bài toán: Chia các đỉnh thành K nhóm bằng nhau. Đặt sao cho các cạnh nối trong mỗi nhóm là lớn nhất có thể. Kết quả bài toán ban đầu chính là M - tổng này.

Ban đầu mình tạo sol đặt random đến khi quá 0.95s thì thôi. Sol này được 100.4 điểm. Sau đấy mình chuyển qua cách thử đảo chỗ 2 đỉnh (x, y) thuộc 2 nhóm khác nhau. Để tránh local best mình sử dụng Simulated Annealing. Vì không có nhiều thời gian để test và cải tiến tốc độ nên mình được 109.2 điểm.

Sau khi thi mình tạo local test, lấy benchmark là sol được 100.4 điểm.

Vì time limit cho rất eo hẹp so với N (1s) nên cách của mình không thật sự hiệu quả. Sau khi thi mình có một số cải tiến về tốc độ:

1. Phép đổi chỗ 2 đỉnh có 2 cách: O(2 * n / k; 1) và O(1, deg(x) + deg(y)) trong đó deg(x) là số cạnh chứa x và O(2 * n . k, 1) nghĩa là tính chênh lệch trong O(2 * n / k) và đổi chỗ 2 đỉnh trong O(1). Nếu n * n / k < 2 * m thì mình dùng O(2 * n / k) còn ngược lại dùng O(1, deg(x) + deg(y)). Thực tế nếu dùng SA thì nên chọn cách O(1, deg(x) + deg(y)) vì rất ít khi chênh lệch tạo ra kết quả chấp nhận được. Lời giải được 1.092 của mình trong lúc thi dùng O(deg(x) + deg(y); deg(x) + deg(y))

2. Cải tiến copy mảng. Mình dùng số 64-bit để copy hai mảng nên tốc độ copy nhanh hơn 7 lần về mặt lý thuyết.

Có một cách khác là sinh random các hoán vị rồi đổi chỗ đến khi không tạo chênh lệch tốt nữa thì thôi. Cách này cũng tốt nhưng chỉ được khoảng 1.089 điểm.

Trong benchmark 50 tests, cải tiến về tốc độ ở 1s cho mình sol tốt nhất là 1.0927 và tổng các best là 1.0937

Mình nâng thời gian lên 3s thì best sol là 1.09482 là tổng các best là 1.09512.

Cách của mình khá đơn giản và có tốc độ cải tiến chậm. Không biết lời giải bài này của các bạn khác thế nào?

Oh bài NP em cũng làm gần giống anh =)) Chỉ khác là em local search chay chứ không simulated annealing. Em có một ý tưởng về một cách swap nữa, mình phải trừ đi số quan hệ cũ và cộng thêm số quan hệ mới, đếm số quan hệ này thì có thể biểu diễn tập hợp đỉnh kề của một đỉnh và tập hợp đỉnh thuộc một nhóm bằng một dãy bit, và lấy and của tập hợp đỉnh kề với tập hợp đỉnh thuộc nhóm sẽ ra được tập hợp những đỉnh nối với đỉnh đang xét thuộc cùng nhóm. Nhóm 20 bit lại làm một để and và đếm cho nhanh, độ phức tạp của phép swap sẽ là O(n / 20), có thể thay thế cách O(n / k) nếu k nhỏ :v Ý tưởng thế thôi chứ em cũng chưa thử, code thêm thì lằng nhằng quá =))

Dù sao bài này với công thức tính điểm lấy đáp số của ban tổ chức chia đáp số của thí sinh thì em nghĩ điểm cũng khó mà cao lên được =)) Vì tỉ lệ này với những lời giải khá tốt chắc xấp xỉ 1 cả, phạm vi đáp số nhỏ nên khó mà lệch nhau quá nhiều :v