The Lyons là team đến từ đảo quốc sư tử của NTU, theo như flashmt thì có một thành viên đã từng thi IOI.

Một chút thông tin về đề bài:
- 3 bài cuối (H, I, J) là 3 bài dễ, code khá đơn giản.
- Bài D: cho N điểm (N <= 10^5). Có Q truy vấn (Q <= 10^4), mỗi truy vấn là đếm số điểm nằm trong hình tròn (0,0), bán kính R. Thuật toán: chặt nhị phân cơ bản.
- Bài B: Cho N điểm phân biệt trên hình tròn (N <= 20,000). Đếm số tam giác nhọn. Bài này thuật toán cũng khá cơ bản. Đội mình và Nguyên (và chắc là cả các đội khác nộp sai khác) sai do không cẩn thận trong việc xử lý số thực.

Các bài còn lại khá khó. Trong thời gian cuối đội mình có nghĩ và làm thử A, E, G và C.
- Bài E: Đại khái là cho các truy vấn chèn, xóa ký tự khỏi một dãy số. Yêu cầu in ra một số ký tự ở xâu thuộc version k. Phải xử lý online.
Bài này đại khái là dùng CTDL để mô phỏng các thao tác, sau tầm 100 version thì lưu lại 1 version. Đội mình code thuật toán này chạy đủ nhanh, nhưng tiếc là ko debug kịp
- Bài A: Cho một bảng gồm 0/1 kích thước M*N (M, N <= 40). Cho phép thực hiện các thao tác đảo bit 1 ô trên bảng (0 --> 1 và ngược lại). Tìm độ dài dãy biến đổi ngắn nhất để bảng thỏa mãn: Số số 1 trên càng hàng bằng nhau, số số 1 trên các cột bằng nhau. Đội Spear of Triam có code luồng mincost nhưng không qua được time limit.
- Bài G: Mình không đọc đề bài này mà chỉ nghe người khác tóm tắt, có sai sót gì mong các bạn thông cảm
Có N màu (N <= 100), và một đồ thị H đỉnh (H <= 1000). Mỗi màu có trọng số C(i) và mỗi cạnh (u,v) của đồ thị có trọng số W(u,x) với x là màu của đỉnh v. Cho Q truy vấn (Q <= 1000). Mỗi truy vấn cho một đường đi gồm không quá 1000 đỉnh. Với mỗi đường đi, cần tô màu các đỉnh trên đường đi, sao cho tổng trọng số là nhỏ nhất. Tổng trọng số bằng tổng W(u,x) + tổng C(i) trên đường đi.
- Bài C: Cho N điểm (N <= 10,000). Cho Q truy vấn (Q <= 100). Mỗi truy vấn có dạng: Thêm K điểm có cùng tọa độ vào tập điểm gốc (các truy vấn không liên quan đến nhau). Tìm một đường thẳng có tổng khoảng cách đến các điểm là nhỏ nhất.
Bài C là một bài khá cổ điển trong Machine learning, về sau bọn mình có tìm được lời giải ở: http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

Đội Lyon cả 3 là người Indo, có 1 bạn IMO và 2 bạn IOI
Theo như kết quả thì có vẻ là đội FPT (Spear of triam) và DiscreteMath sẽ được vào world final

19h tối mai (18-11) sẽ có semilive của site Hatyai vừa thi trên UVA.

Bài F:
Cho tập S gồm N <= 100 số nguyên dương <= 500. Tìm tổng LCM của tất cả tập con khác rỗng của S mod 10007.

Oops, lẽ ra không nên post đề trước khi có semilive

semilive ở đâu?

UVA, thông báo trên trang chủ có hyperlink mà.

Bài A: Sau khi xây được flow graph cho luồng mincost, bạn sẽ nhận ra được các giá trị cost rất đặc biệt. Nếu mincost flow chỉ có k loại cost => đưa về k maxflow được => mình nghĩ là đưa được về cặp ghép trong đồ thị 2 phía. Nhưng dù sao cũng có đội passed bài này bằng mincost flow.

Bài E:
Nếu bỏ operation “version” đi thì bài này dùng splay tree chuẩn. Đối với operation “version”, ý tưởng chính là làm sao quản lý được version bằng cách đánh nhãn thời gian. Có 3 cách tiếp cận:

1. (Cách được mô tả trong solution sketch) Thay thế pointers trong splay tree bằng một list pointers để quản lý timestamp. List pointers này là dãy đơn điệu tăng => binary search mỗi lần query. Số lượng pointers quản lý timestamp là hữu hạn, amortized cost của query O((logN)^2).

2. Dùng skiplist thay vì splay tree để quản lý thông tin version, mình nghĩ cách này code dễ hơn dùng splay tree.

3. Caching -- Lưu x versions trong 1 history cache. Tức là các version được chia thành nhiều đoạn độ dài K, các thao tác cần cập nhật dữ liệu chỉ xoay quanh thông tin được lưu trong cache => Không cần thêm CTDL nào khác. Đội duy nhất Aced khi thi onsite đã dùng cách này, và tình cờ K mà các bạn đó chọn đã qua được test ở Hatyai (case chậm nhất mất khoảng 6s), nhưng lại TLE với time limit của UVA. Vì thông thường limit của onsite ~4 lần standard solution, còn UVA chỉ chênh lệch khoảng 1-2s.

p/s: Thứ bảy này (24/11/2012, 9:00 – 14:00) mình và coach của HKUST có tổ chức 1 buổi joint practice cho các team của 2 trường (just for fun ^^)
http://acm.hdu.edu.cn/vcontest/vtl/vtl/userlogin/vtlid/4420

Nếu team nào muốn join the fun thì các bạn để lại thông tin (tên team) trong thread này (sorry, đang spam thread của admin). Trong trường hợp nhiều hơn 5 teams, mình sẽ mở contest public, còn không thì các team đăng ký sẽ nhận được password truy cập trong tin nhắn riêng

lâu lắm mới thấy Free Pascal

Bạn đã trở lại, và lợi hại gấp nhiều lần

Chị cho team em join this fun với nhé:
Team: Spear of Triam

Nhân thể bài A, trong contest, team em làm luồng mincost, có 2 loại chi phí là +1 với -1 nhưng bị TLE. Sau đó bọn em tìm cách chuyển về luồng thường (vì thấy chi phí khá đặc biệt) nhưng không chuyển được (bị WA). Chị có thể chia sẻ paper nào đó về K-maxflow được không ạ? Em search google không thấy.

Ngoài ra bọn em cũng đã thử chuyển về cặp ghép trọng số nhỏ nhất giống như bài http://vn.spoj.pl/problems/ASSIGN4/ . Nhưng bài ASSIGN4 này khác một chút, vì khả năng thông qua của các cung giữa 2 đỉnh X-Y trong bài ASSIGN4 là vô cùng, còn trong bài A là 1.

Chị ơi cho đội em đăng kí tham gia cùng nữa với nhé.
Đội em là đội Mog của Đại học FPT.