Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
The 2012 ACM-ICPC Asia Hatyai Regional Contest (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - The 2012 ACM-ICPC Asia Hatyai Regional Contest
#67816
hphong591992 (Admin)
hphong+103
Admin
Bài viết: 1296
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
 
Dont be shy when + 4 me !!
  Đã khóa chức năng gửi bài.
#67837
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+2)
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
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67838
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+1)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67839
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
Oops, lẽ ra không nên post đề trước khi có semilive
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67844
pirate (Admin)
khanhptnk+108
Admin
Bài viết: 868
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
semilive ở đâu?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67845
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
UVA, thông báo trên trang chủ có hyperlink mà.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68013
freepascal145 (Thành viên)
Đã biết code đệ quy
Bài viết: 8
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+7)
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 IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68020
khuebeo (Admin)
beo_chay_so+62
Admin
Bài viết: 294
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
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
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68021
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68032
Arvernorix (Thành viên)
arvernorix
Đã biết code đệ quy
Bài viết: 14
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: The 2012 ACM-ICPC Asia Hatyai Regional Contest 8 năm, 2 tháng trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS