Hướng dẫn giải bài trên VNOI

Mình đã thêm "Hướng dẫn giải bài" trên VNOI. Các bạn có thể xem code mẫu của khoảng 500 bài trên VNOI: xem Danh sách bài tập.

VNOI là nơi rất nhiều huyền thoại của làng Competitive Programming Việt Nam bắt đầu luyện tập. Giờ bạn đã có thể xem code của những huyền thoại sau:

1. Khúc Tuấn (khuc_tuan): 

  • Đỏ target Topcoder duy nhất của VN (max rating > 3000, chỉ khoảng 100 người trên thế giới từng đạt được),
  • #2 Facebook Hackercup 2011;
  • Người VN duy nhất vào chung kết Google Code Jam;
  • #17 ACM ICPC World final 2011.

2. Lăng Trung Hiếu (hieult):

  • Chỉ mới bắt đầu học Tin từ lúc vào ĐH, nhưng anh đã nhanh chóng gánh team FPT lọt vào top 50 ACM ICPC World final 2013, cố vấn cho team RRwatameda đạt #15 ACM ICPC World final 2016.
  • Anh Hiếu cũng có một thời gian dạy đội tuyển quốc tế IOI và ra đề cho ACM ICPC Việt Nam.

3. Kiên Khánh Hạnh (kc97ble, happyboy99x, skyvn97):

  • Bộ 3 nổi tiếng của khoá 97 Tổng hợp - khoá mạnh nhất trong lịch sử chuyên Tin Tổng hợp
  • Kiên kc97ble nổi tiếng với trang code mẫu kc97ble và Free Contest.
  • Hạnh vàng IOI 2015 nhưng đã chuyển sang nghề bán trà sữa dạo.
  • Khánh tuy code đẹp tuyệt diệu, nhưng ít nói hơn, đã qua Nhật chơi với các bạn Nhật.

4. RR & Nguyên Nguyễn (flashmt):

  • Team RRwatameda, #15 ACM ICPC World final 2016 (cao nhất trong lịch sử các team VN từ trước đến nay);
  • Trong đó flashmt code nhanh tay to bài nào đã code là AC. Bật mí: hơn 90% code của team RRwatameda đều do flashmt code.

5. Vương Linh (ll931110):

  • Cực sv MIT, Vàng IOI 2011 - sau 8 năm chờ đợi 1 HCV (từ 2003 - 2011), VN mới xuất hiện 1 Vương Linh.

6. Lê Anh Đức (ladpro98):

  • APIO 2016, code trâu bò nhất khoá 98.
  • #2 VOJ

 

1 bạn nữ giấu tên cho biết: Em đã đọc code mẫu của Khúc Tuấn trên VNOI và yêu anh ý luôn  ko biết giờ này anh đang ở đâu..
1 bạn nam giấu tên khác cho biết: Giá em là con gái thì đã có thể yêu anh Lăng Trung Hiếu rồi - code của anh quá trí tuệ đỉnh cao chắc chắn là đẹp trai phong độ.

 Ảnh minh hoạ:

Giờ các bạn đã có thể đọc đề trên VNOI, với những tính năng vượt trội như sau:

  1. Phân loại bài tập
  2. Tìm kiếm theo kỳ thi (hiện có HSG QG, sau này sẽ có thêm VM, VO, Free Contest...)
  3. Hầu hết các đề bài format đẹp hơn trên VOJ (xem hình minh hoạ đc chụp từ admin tool của mình), chẳng hạn bài ALAKE: VNOI: http://vnoi.info/problems/show/ALAKE/
  4. Một số bài bị mất hình đã được sửa trên VNOI (tuy nhiên VOJ sẽ không được sửa). Ví dụ bài http://vnoi.info/problems/show/SIGNAL/ vs http://vnoi.info/problems/show/NTKING/
  5. Một số bài đề sai, thiếu, ... đã được sửa trên VNOI: Ví dụ bài TREENUM được thêm giới hạn: http://vnoi.info/problems/show/TREENUM/

Còn chần chừ gì nữa, ngay từ hôm nay các bạn hãy đọc đề trực tiếp trên VNOI để ủng hộ bọn mình: http://vnoi.info/problems/list

2016 ACM-ICPC Phuket World Finals !!

Xin chào các bạn. Hôm nay là Chủ nhật ngày 15/5, ngày đầu tiên của vòng chung kết thế giới ACM-ICPC. World Finals năm nay được tổ chức ở Phú Kẹt (Thái Lan), từ hôm nay các đội tuyển đã bắt đầu hạ cánh xuống Phú Kẹt. Ngày thi chính thức sẽ được diễn ra vào Thứ năm ngày 19/5, cuộc thi kéo dài 5 tiếng, gồm ít nhất 10 bài.

Các đội tuyển tham dự là những đội xuất sắc nhất, vượt qua vô số đội mạnh khác (ví dụ như đội của mình) tại các cuộc thi Regional trước đó. Năm nay Việt Nam có đến hai đội tham dự World Finals, đó là:

  1. Đội BYTE đến từ Đại học UET, gồm 3 thành viên:
    + Đỗ Ngọc Khánh
    + Nguyễn Tiến Trung Kiên
    + Phạm Văn Hạnh
  2. Đội HCMUS - Shine đến từ Đại học HCMUS, gồm 3 thành viên:
    + Lê Yên Thanh
    + Phạm Việt Khôi
    + Trương Minh Bảo
  3. Ngoài ra còn một đội người Việt đến từ đại học NUS ở Singapore. Đó là đội RRwatameda, gồm 3 thành viên:
    + Nguyễn Thành Trung
    + Nguyễn Tấn Sỹ Nguyên
    + Nguyễn Hùng Tâm

Mong các bạn hãy cổ vũ nhiệt tình cho các đội tuyển Việt Nam dành kết quả cao nhất ở World Finals lần này.

Ngoài ra, để hưởng ứng phong trào đỏ đen cùng với mùa Euro đang đến gần, ban tổ chức VNOI cũng xin tổ chức một Gameshow cá độ nho nhỏ. Các thành viên VNOI đều có thể tham gia, thể lệ của chương trình là đặt cược cho đội Việt Nam trong số 3 đội trên dành thứ hạng cao nhất. Các bạn có thể đặt cược một số tiền bất kỳ, và sẽ thắng lớn nếu như may mắn đoán đúng, làm giàu quả thật không khó. Sau đây là tỷ lệ cược của nhà cái:

  • Đội BYTE: Đặt 3 ăn 0.
  • Đội HCMUS - Shine: Đặt 69 ăn 0.
  • Đội RRwatameda: Đặt 109 + 7 ăn 0.

Thủ tục đặt tiền sẽ được cho biết sau. Xin cảm ơn :))

Kỳ thi duyên hải năm 2016

Đề bài của kỳ thi học sinh giỏi các trường THPT chuyên Khu vực Duyên Hải và Đồng bằng Bắc bộ lần thứ 9, năm học 2015-2016 gồm 2 khối 10 và khối 11 đã được đưa lên mạng.

Các bạn có thể download đề bài tại đây : Link download đề bài

Các bạn cùng đọc qua và thảo luận tại topic này nhé :D

Update 1: Link download bộ test kỳ thi

                                                                                                                        VNOI Admins

Codeforces Round #346 (Div 2)

Vào 23:05 tối nay 30/03/2016 Codeforces Round #346 (Div 2) sẽ diễn ra.

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Chúc Tết 2016

Nhân dịp tết âm lịch 2016 Bính Thân, mình xin thay mặt các admins diễn đàn VNOI cảm ơn các bạn đã ủng hộ diễn đàn trong suốt một năm vừa qua.

Năm 2015 cùng với nhiều sự kiện đáng nhớ như sự trở lại của diễn đàn VNOI cũng như các kỳ thi lớn bé mà các bạn cùng đồng hành đã trở nên vô cùng ý nghĩa.

Chúc các bạn và gia đình năm mới tràn ngập hạnh phúc và sức khỏe dồi dào. Chúc các bạn đạt nhiều thành công trong năm mới và đồng hành, chia sẻ niềm vui đó cùng diễn đàn VNOI.

                                                                                                                  VNOI Admins.

Những vấn đề cơ bản về mạng neuron

Xin chào các bạn, trong bài viết này mình sẽ giới thiệu với các bạn về mạng neuron (neural network), một mô hình học máy (machine learning) đang rất thịnh hành hiện này. Các bạn có thể download tài liệu ở link phía dưới. Mong muốn của bọn mình là muốn viết một tài liệu chuẩn về chủ đề này bằng tiếng Việt để làm khởi đầu cho những bạn muốn tìm hiểu. Vì thế, mình rất mong nhận được góp ý và sửa lỗi để tài liệu ngày càng hoàn thiện hơn.

http://khanhxnguyen.com/nhung-van-de-co-ban-ve-mang-neuron/

Live stream ACM training

Bạn quá rảnh rỗi? Bạn không có việc gì làm? Bạn không biết phải làm gì để giết thời gian?

Chần chừ gì nữa, hãy bật Youtube lên và xem RR code :v

Hôm nay nhân dịp còn khoảng 4 tháng nữa là ACM ICPC World final, mình sẽ train hầu như tất cả các ngày (trừ khi đi chơi), bắt đầu từ tầm 8-9h tối giờ VN đến khoảng 1-2h sáng.

Các bạn nếu rảnh rỗi có thể vào chim lợn hoặc cười vào mặt mình mỗi lúc bị WA / TLE ở link

Một vài câu thắc mắc thường thấy:

  • Mình ko quay mặt / không nói (do xấu). Tuy nhiên nếu sau này bỗng nhiên thấy muốn hù các bạn có thể mình sẽ bạt webcam
  • Nếu ko phải train team thỉnh thoảng sẽ chat trên Youtube
  • Mình sẽ có note lại những cái mình đang làm ở góc dưới màn hình, để bạn nào vào sau biết mình đang làm trò gì :v
  • Mình làm cho vui thôi nên các bạn đừng trông chờ gì nhiều. Mình nghĩ khi xem stream bạn có thể thi đua nghĩ bài + code vs mình, xem ai code nhanh hơn :3 Nếu bạn code nhanh hơn thì chúc mừng bạn bằng 1 tràng pháo tay :))

RR

UPD: Training 1 (đã có thể tua đc :v)

Training 2: 19/01 sẽ là 1 buổi training của team mình với mình + Hùng Tâm

Bài viết mới của mình, hy vọng giúp đỡ được các bạn mới học lập trình. Cao thủ xin miễn đọc :D

http://khanhxnguyen.com/toi-da-hoc-tin-hoc-nhu-nao-bat-dau-tu-dau/

 

Lời giải các bài VOI 2016

Kỳ thi VOI 2016 đã kết thúc và chắc chắn là để lại nhiều kỉ niệm đau buồn trong lòng tất cả mọi người. Tuy vậy, gác quá khứ qua 1 bên, dù sao các bạn cũng gắn bó với môn Tin khá lâu rồi, tuy thọt lần này nhưng hi vọng các bạn vẫn đam mê môn Tin học, và đam mê giải bài. Hôm nay ta thọt nhưng ngày mai ta đứng lên sẽ mạnh mẽ và khủng khiếp hơn.

Nói tóm lại mình xin đi tiên phong tổng kết các thảo luận các bài VOI 2016:

Bài 1:

Nhận xét:

  • Có thể sort lại dãy
  • Có thể chọn tất cả các số bằng nhau.

Như vậy đầu tiên chúng ta có thuật N*2^10 hồn nhiên như sau:

  1. Sort lại, gộp các số bằng nhau lại thành 1.
  2. Đặt F(i, mask) = độ dài dãy lớn nhất nếu ta chọn các số từ A1 --> Ai, mask là dãy bit độ dài 10. Trong 10 số Ai, A(i-1), A(i-2)... thì ta chỉ chọn các số có trong mask. Gọi tập các số đc chọn trong 10 số đó là S(mask). Từ F(i, mask) ta tính đc F(i+1, mask'). Để kiểm tra thỏa mãn tính chất đề bài thì ở trạng thái (i+1, mask') cần xét xem có 2 số nào trong S(mask') mà có hiệu là 1, 8 hoặc 9 hay không.

Bài 2:

(Theo bạn bvd);

Nhận xét:

  • Cách vận chuyển tiết kiệm xăng nhất là vận chuyển toàn bộ lượng xăng có thể ở bể chứa trước đến bể chứa sau

Từ đó thu đc thuật toán với độ phức tạp L/D

Bài 3:

-_-

Bài 4:

Chia hình thoi thành 4 tam giác vuông.
F1(i, j) = độ dài cạnh lớn nhất của tam giác vuông có đỉnh góc vuông là (i, j) và 2 cạnh của nó hướng lên trên và sang trái.
Như vậy:

  • F1(i, j) = 0 nếu ô (i, j) và (i-1, j) hoặc (i, j-1) có cọc.
  • Ngược lại F1(i, j) = 1 + max(F1(i-1, j), F1(i,j-1))

Tương tự tính 4 tam giác 4 hướng: F1, F2, F3, F4.

Sau đó ở (i, j) thì hình thoi lớn nhất có tâm ở (i, j) là min(F1(i,j), F2(i,j), F3(i,j), F4(i,j))

Bài 5:

Với mỗi biểu thức sinh tất cả các giá trị có thể có ra. Sau đó làm cặp ghép.

Để ko phải xử lý số lớn thì cứ tính tràn số 64 bit. Nếu sợ sai thì tính thêm giá trị MOD 10^9 + 7.

Bài 6:

(Lời giải bởi Kiên IOI 2015)

Bài này có 2 bước:

  1. Với mỗi cây, cần tính xem là nếu nó đổ sang trái (hoặc sang phải), thì đổ đến tối đa là bao nhiêu. Đặt 2 cái này là Fright(i) và Fleft(i).
  2. Sau khi có Fleft(i) và Fright(i), xét 2*N đoạn: [Fleft(i), i] và [i, Fright(i)]. Bài toán đưa về chọn ra ít đoạn nhất sao cho phủ đc tất cả 1..N và ko có 2 đoạn nào có điểm chung (để tránh chọn cả 2 cái left và right của i).

Bước 1:

  • Với mỗi i, Fright(i) = max(Fright(i+1).. Fright(i+Hi)). 
  • Như vậy có thể tính đc bằng BIT hoặc IT --> O(N*logN)
  • Ngoài ra có thể tính O(N) dùng stack như sau:
    • Ở i ta duy trì 1 stack chứa tất cả các giá trị có thể dùng để cập nhật cho Fright(i).
    • Rõ ràng, nếu i < j và Fright(i) > Fright(j) thì j vô dụng, nên ta có thể vứt ra khỏi stack.
    • Như vậy, trong stack, nếu có i < j thì Fright(i) < Fright(j)
    • Ở i, đầu tiên loại những j ở đỉnh của stack, vừa loại vừa cập nhật Fright(i). Quá trình này dừng lại khi có Fright(i) < đỉnh stack < Fright(đỉnh stack). Cuối cùng ta thêm i vào stack, thì vẫn đảm bảo tính chất nêu trên.
    • Mỗi đỉnh vào stack và ra khỏi stack 1 lần, nên đpt là O(N).

Bước 2 thì các đoạn rời nhau, nên ta có thể QHD trong O(N) khá đơn giản.