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
Trả lời: Bàn tròn IOI 2011 (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Ủ ĐỀ - Trả lời: Bàn tròn IOI 2011
#49530
khuc_tuan (Admin)
khuc_tuan+137
Admin
Bài viết: 1472
graph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
Trả lời: Bàn tròn IOI 2011 9 năm, 6 tháng trước   (+1)
Em có 2 quan điểm hơi khác thầy:

- Về chiến thuật, các em lúc thi không hề biết mình đang đứng ở đâu và cần bao nhiêu điểm để đạt mục tiêu. Có lẽ lúc cuối giờ em Linh đang cố gắng đc subtask điểm cao bài elephants. Khá mạo hiểm nhưng khi thi không thể biết được 12 điểm kia có thực sự đáng để dành thời gian vào không.

- Về thay đổi: thi vòng 2 nên có hệ thống nộp bài giúp các em biết điểm 1 số bài / test, tránh trường hợp "chết oan" mà đi thi IOI hiện nay không có những trường hợp như thế. Còn IDE thì em vẫn nghĩ là không quan trọng
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49546
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: Bàn tròn IOI 2011 9 năm, 6 tháng trước   (+3)
Mình có một ý kiến nhỏ về vấn đề subtask:

Đúng là những cao thủ thì họ cứ hổ báo lao vào và ăn full ngay. Còn chúng ta phải tiến chắc từng bước một, giải từng subtask. Tuy nhiên thì việc giải subtask không phải là quá vô nghĩa. Mình cá là dù có giỏi mấy cũng không dại gì mà không ngó qua một gợi ý rành rành như subtask...

1. IOI 2009 - Region. Đây là một bài rất tiêu biểu về ý nghĩa của subtask. Chỉ bằng một nhận xét tinh tế, thuật toán ăn full hóa ra là sự kết hợp của thuật toán giải các subtask. Giới hạn của subtask là một gợi ý ngầm cho thuật toán. Năm nay, có lẽ nên tham khảo bài RACE.

2. Bắt đầu từ IOI 2010, để ý rằng các subtask ngày càng nhiều, điểm mỗi subtask ngày càng nhỏ lại. Ăn full một bài mang tính chất optimize tinh tế nhiều hơn là thay đổi thuật toán. Minh chứng là bài Hotter-Colder (IOI 2010), năm nay là bài Parrots (không biết solution, nhưng theo ý kiến riêng thì cải tiến hết mức mới ăn được 100, thuật toán căn bản không khác mấy so với subtask N = 32) và bài Elephants (mình đoán là subtask 3 điểm là dành cho việc code thay thế STL của C++ để chạy nhanh hơn).

Dù sao cũng đừng trách em Linh nhiều quá. Thi chung với em ấy nhiều lần, phần nào anh rất thích phong cách thi giật gân của em. Thi Codeforces mở bài khó làm trước, thi topcoder fail bài 250 nhưng AC bài 1000. Submit vào những phút cuối của IOI, không rõ có run tay hay không nhưng đó là một chuyện đáng ngưỡng mộ. Nếu như em không biết mình đang ở đâu, thì đó là một tinh thần chiến đấu đến cùng, luôn luôn đi lên phía trước. Còn nếu như em biết đó là submission sẽ thay đổi thế cuộc, thì phải có một tinh thần thép để tập trung code mà không nghĩ lung tung. Em làm anh hơi đau tim vì subtask cuối cùng bài Parrots không phải dễ ăn, hơn nữa, lại tính điểm theo độ tốt. Nhưng không sao cả, nó làm chiến thắng không thể nào đẹp hơn.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49575
hoangle (Thành viên)
Biết code binary-indexed tree
Bài viết: 47
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: Bàn tròn IOI 2011 9 năm, 6 tháng trước   (+3)
Quên mất là năm nay có luật về subtasks: Nếu dữ liệu cho subtask i cũng có thể lấy làm dữ liệu cho subtask j mà thí sinh bị fail subtask i thì sẽ không được chấm subtask j nữa. Tức là cho dù subtask 1 dễ nhưng trong đó bao gồm 1 test rất đặc biệt làm thí sinh bị fail thì sẽ bị 0 điểm cả bài nếu như ràng buộc dữ liệu của subtask 1 nằm trong những subtasks khác.
Dĩ nhiên sẽ phải nghĩ theo subtasks nhưng làm trong đầu hay làm bằng code, release hay không là điều phải cân nhắc vì có một số subtask tốn khá nhiều effort để code và chẳng liên quan gì lắm nếu mình muốn ăn full. Linh làm bài RACE cũng bỏ qua subtask 12 điểm. Mình không biết mục tiêu cụ thể của Linh ngày 2, nếu là cố gắng chung chung thì cách làm là chính xác, còn nếu quyết tâm đoạt vàng mà đã quay ra code và release từng subtask khi mới hết 1/10 thời gian và 1 bài full (cho dù ko biết rank của mình) là điều không hợp lý lắm.
@Tuấn:
Chuyện thay đổi quy chế nói cho vui thế thôi, từ khi có yêu cầu thay đổi cho đến lúc thay đổi thật còn nhiều chuyện lắm.
Nếu IDE ổn định và giúp người ta bao quát được chương trình thì chọn cái nào cũng được. Nhưng cái IDE rất hay treo và bị lỗi thì dùng rất khó chịu. Nhất là thi VOI2 không có sự lựa chọn khác, hoặc dùng IDE đó, hoặc Notepad , Notepad++ cũng không có luôn.
@pirate: Mình đâu có trách Linh câu nào, dù Linh mất vàng cũng rất đáng khen. Tuy cách làm của Linh nếu như bạn nói thì vào thời điểm hiện tại sẽ khó có HLV nào ủng hộ và phổ biến cho học sinh được. Linh vẫn có điểm yếu nên làm như thế rất đau tim, nếu Gennady thì là chuyện khác
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#49729
ll931110 (Thành viên)
ll931110+27
Nhắm mắt code không bug
Bài viết: 152
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: Bàn tròn IOI 2011 9 năm, 6 tháng trước   (+2)
Rất xin lỗi mọi người vì đến tận hôm nay em mới có đủ thời gian để viết post này. Cảm ơn mọi người đã cổ vũ cho đội tuyển

@pirate:
Thuật toán của em trong bài RACE là như sau.
- Đặt 0 là gốc của cây, tiến hành DFS để xác định quan hệ cha/con trên cây
- Đầu tiên, xét cách làm không tối ưu với độ phức tạp O(NK): gọi F[x][y] là số đường nhỏ nhất cần đi để có 1 đường xuất phát từ 1 con của x và kết thúc tại x, và độ dài đường đi đó đúng bằng y. Việc tính toán và cập nhật trong phần này không quá phức tạp.
- Từ cách làm trên, nhận thấy vấn đề nằm ở việc với mỗi u, cần quản lí 1 tập các đường đi từ con của u đến u (gọi là path[u], và tổng số lượng các phần tử trong các path[u_i] không vượt quá N). Cho nên, để cải tiến, cần sử dụng cấu trúc dữ liệu quản lí path[u] thực hiện được 2 thao tác:
+ Truy vấn tìm 1 đường có độ dài x km và đi qua ít con đường nhất
+ Với 2 nút u, v trong đó u là cha của v, cần "ghép" path[u] và path[v] thành 1 tập

Nếu thực hiện trực tiếp việc dồn từng phần tử của v vào u, trong tình huống xấu nhất sẽ cần dồn O(N^2) phần tử. Với việc luôn dồn từ tập nhỏ hơn sang tập lớn hơn, có thể chứng minh được số phần tử cần di chuyển trong tình huống xấu nhất vào khoảng O(N log N). Ngoài ra, trong bài em sử dụng BST (STL set trong C++) để quản lí các path[u_i], nên độ phức tạp trong thuật toán của em là O(N (log N)^2)

Anh có thể tham khảo kĩ thuật tương tự trong các bài
http://vn.spoj.pl/problems/STRAVEL/
http://main.edu.pl/en/archive/oi/18/rot
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#51465
wanderer (Thành viên)
Đã biết code đệ quy
Bài viết: 9
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: Bàn tròn IOI 2011 9 năm, 5 tháng trước   (+1)
Gửi mọi người đọc 1 bài báo hết sức thú vị về kỳ thi IOI http://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#58282
takiemtam (Thành viên)
takiemtam-
Đã code là AC
Bài viết: 114
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: Bàn tròn IOI 2011 9 năm, 1 tháng trước   (+0)
wanderer viết:
QUOTE:
Gửi mọi người đọc 1 bài báo hết sức thú vị về kỳ thi IOI
http://www.wired.com/magazine/2010/11/mf_algorithmolympics/all/1

ai đó dịch bài viết này cho mọi người thưởng thức đi, vừa đọc vừa google khó hiểu quá
 
Đã lưu IP Đã lưu IP  
 
Thiên hạ đệ nhất kiếm
  Đã 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