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.

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/

February Challenge 2016

Kỳ thi February Challenge 2016 của CodeChef sẽ được diễn ra trong 10 ngày, bắt đầu từ 16h30 chiều ngày mai 5/2/2016. Đặc biệt, tất cả các bài đã được VNOI Team dịch sang Tiếng Việt. Tham gia kỳ thi, các bạn sẽ được thử sức với nhiều bài toán khác nhau, ngoài ra còn có cơ hội nhận các giải thưởng lớn như $300 hay $400. Chúc mọi người ăn Tết vui vẻ và kiếm "lì xì" từ kỳ thi :D

January Lunchtime 2016

Vào 12h30 trưa nay ngày 31/01/2016, kỳ thi January Lunchtime 2016 sẽ được diễn ra.
Kỳ thi sẽ kéo dài trong 3 tiếng và đã được VNOI Team dịch sang Tiếng Việt.
Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Dành cho những bạn chưa biết: Cách xem đề Tiếng Việt

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.

VOI 2016

Vào 2 ngày mùng 6 và mùng 7 tháng 1 năm 2016, kỳ thi Học sinh giỏi cấp Quốc gia môn Tin học VOI2016 sẽ được diễn ra. Thay mặt các admins VNOI mình xin chúc các bạn thật bình tĩnh và cố gắng hết sức mình để có thể đạt kết quả cao nhất trong kỳ thi này. 

Một vài lưu ý nho nhỏ cho các bạn trước khi tham gia kỳ thi mà mình đúc kết được trong các cuộc thi của mình

  • Cố gắng vét điểm bằng mọi cách, brute force, greedy các kiểu.
  • Kiểm tra tên file, tên file output input cẩn thận.
  • Khi in bài đừng ký luôn mà hãy đọc cẩn thận lại 1 lần rồi ký. Đừng tiếc vài phút đọc lại.
  • Mang theo nước vào phòng thi nếu phòng thi không có nước. 3 tiếng thi vòng 1 có thể không quá nhiều, nhưng khi mất bình tĩnh hay uống 1 hụm nước để giảm căng thẳng và làm bài tiếp.

Các bạn thi xong thì post đề vào đây cho các bạn khác không thi tham khảo nhé :D 

                                                                                                                                       Admins VNOI

January Long Challenge 2016

Kỳ thi đầu năm 2016 của CodeChef là January Long Challenge 2016 sẽ được tổ chức trong 10 ngày, bắt đầu từ 16h30 hôm nay ngày 01/01/2016 đến hết 16h30 ngày 11/01/2016. Mọi người cùng tham gia nhé :)
Đề thi đã được dịch sang Tiếng Việt.

VO2016 - statistic

Xin chào các bạn, vậy là kỳ thi VO16 đã kết thúc 2 ngày thi, điểm thi và bảng xếp hạng đã có tại đây

Xin chúc mừng natsukagami đã vô địch kỳ thi này với chênh lệch ~1 điểm với bạn duyboy135 ở rank 2.

Sau đây là 1 chút thống kê về kỳ thi (mình mới tập vẽ nên vẽ xấu, thông cảm nha :<)

Ngày 1 có 4 bạn được max 20 điểm: duyboy135, duymanhit, tru3goon3r, su123

Đường điểm các thí sinh ngày 1

Ngày 2 có bạn ladpro98 là người duy nhất được max 20 điểm.

Đường điểm các thí sinh ngày 2

Tuy nhiên với phong độ duy trì ổn định nhất, bạn natsukagami đã bứt phá lên rank 1 của kỳ thi VO16

Đường điểm của tổng 2 ngày

Phân bố điểm, mình lấy mốc dựa theo điểm của kỳ thi học sinh giỏi năm 2015

  • < 10: không có giải
  • 10-17: Giải khuyến khích
  • 17-23: Giải Ba
  • 23-30: Giải Nhì
  • > 30: Giải Nhất

Mấy hình xấu xấu trên cũng không thể hiện được nhiều lắm nhưng chỉ là thống kê nho nhỏ về kỳ thi :">

Hi vọng kỳ thi VO16 giúp bạn củng cố kiến thức, mang lại thêm những giải thuật hay độc đáo, cũng như một bước đệm tốt để các bạn có thể định hình được phong độ của mình đang ở đâu để đặt mục tiêu phấn đấu cho kỳ thi thật sắp tới.

Thay mặt Admins VNOI, mình xin được chúc các bạn đạt kết quả cao trong kỳ thi VO16 duy trì phong độ, trau dồi thêm kiến thức để đạt kết quả cao nhất trong kỳ thi VOI16 sắp tới. Còn những bạn chưa đạt được mục tiêu của mình ở kỳ thi VO16, chúc các bạn cố gắng hết sức và đạt được đúng phong độ tại kỳ thi thật.

                                                                                                                                       VNOI Admins