June Cook Off 2016

Vào 11h tối Hôm Nay ngày 26/06/2016 sẽ diễn ra kỳ thi June Cook Off 2016. Kỳ thi sẽ diễn ra trong hai tiếng rưỡi. Thời gian làm bài sẽ là hai tiếng rưỡi kể từ lúc bắt đầu. Các bạn sẽ đọc các vấn đề mà kỳ thi đưa ra và giải trong thơi gian thi. Trong lúc làm bài nghiêm cấm chép code. Thông tin thêm về kỳ thi bạn có thể click vào đây hay tấm poster ở dưới.

Chúc các bạn tham gia kỳ thi vui vẻ.

Cách xem đề Tiếng Việt

Khi bạn vào một bài, sẽ hiện ra như hình ở dưới đây. Bạn chỉ cần click vào chữ "Vietnamese" trong khung đỏ là xong.

ReadProblemInVN.png

Đăng ký

Để tham gia kỳ thi bạn chỉ cần một tài khoản codechef. Bạn có thể đăng ký ở đây.

Tham gia

Các bạn sẽ vào trang web của kỳ thi trong trong thơi gian kỳ thi diễn ra để đọc bài và nộp bài.

Cây Palindrome

Mình không phải là người phát minh ra cấu trúc dữ liệu này. Mình chỉ đọc blog của Mikhail Rubinchik và giới thiệu lại với mọi người thôi :)

Bài viết này sẽ mô tả cây Palindrome, một loại cấu trúc dữ liệu tuyệt vời được dùng để giải một số bài toán liên quan đến Palindrome. Loại cấu trúc dữ liệu này khá là mới, thậm chí bây giờ Google "cây Palindrome" bạn cũng không có thông tin gì về nó đâu. Theo như mình biết, tên cây Palindrome nó cũng không phải là tên chính thức của cấu trúc dữ liệu này (vì nó thậm chí cũng không phải là cây).

Update #1: Tên chính thức của cấu trúc dữ liệu này là Eertree, các bạn có thể tìm hiểu thêm về nó tại đây.

Trong bài viết này mình vẫn dùng tên cây Palindrome vì tên đó nghe hay hơn.

Cấu trúc của cây Palindrome

Như mọi loại cây khác, cây Palindrome cũng có nút.

Ngoài nút ra cây còn có các cung để nối các nút. Cung nối giữa hai nút u và v được gán một chữ cái - ví dụ chữ X - nghĩa là ta có được palindrome chứa ở nút v bằng cách thêm chữ X vào hai bên của palindrome chứa ở nút u.

Trong ví dụ trên, ta có được xâu palindrome aba bằng cách thêm chữ a vào hai bên chữ b

Cuối cùng, ta có thêm các liên kết hậu tố. Nút u có liên kết hậu tố đến nút w, nếu palindrome chứa ở nút w là hậu tố không tầm thường lớn nhất của palindrome chứa ở nút u. (hậu tố là một xâu con chứa các chữ cái cuối cùng của xâu, hậu tố không tầm thường (proper suffix) là hậu tố của một xâu và ngắn hơn xâu đó). Từ bây giờ ta sẽ gọi palindrome lớn nhất mà là hậu tố không tầm thường của một xâu là palindrome hậu tố lớn nhất của một xâu.

Trong ví dụ trên, vì a là palindrome hậu tố lớn nhất của aba nên có một liên kết hậu tố từ nút chứa xâu aba đến nút chứa xâu a.

Đặt tên cấu trúc dữ liệu này là cây Palindrome có vẻ không hợp lí lắm, vì nó có tận 2 gốc. Một sẽ chứa xâu palindrome giả độ dài -1. Gốc này giúp ta cài đặt cây dễ dàng hơn, vì khi ta thêm hai chữ cái bất kì vào hai bên xâu độ dài -1 thì ta sẽ được xâu độ dài 1 và nó luôn là palindrome. Gốc thứ hai chứa một xâu rỗng (xâu có độ dài 0), và xâu này cũng là palindrome. Ta cho thêm một liên kết hậu tố từ hai gốc nối đến gốc chứa palindrome độ dài -1.

Lưu ý rằng ta không chứa xâu palindrome vào nút khi cài đặt thực tế, nếu làm vậy ta sẽ tiêu tốn quá nhiều bộ nhớ. Nút thực tế sẽ chứa độ dài xâu palindrome, chữ cái được gán vào các cung, và các liên kết hậu tố.

Xây dựng cây Palindrome

Ở đây mình sẽ hướng dẫn tạo cây Palindrome chứa tất cả các palindrome con của một xâu s. Ta thấy: Một xâu độ dài n sẽ không có quá n xâu palindrome con, vì vậy cây Palindrome sẽ không có quá n + 2 nút (do phải thêm 2 gốc nữa).

Ta sẽ xử lí từng chữ cái một trong xâu. Giả sử ta đã xử lí được tiền tố p của xâu, và giờ ta phải xét đến chữ cái x tiếp theo.

Ta lưu lại t là palindrome hậu tố lớn nhất của tiền tố p.

Vì t đã được xử lí, nên nó được chứa trong một nút nào đó của cây Palindrome. Nút này sẽ có liên kết hậu tố đến một nút nào đó, nút nào đó lại có một liên kết hậu tố đến một nút khác và cứ tiếp tục như vậy.

Bây giờ ta hãy tìm hậu tố palindrome của tiền tố mới p+x. Hậu tố đó sẽ có dạng xAx, với A là một xâu nào đó, có thể rỗng hoặc có độ dài -1. Vì xAx là palindrome, nên A cũng là palindrome, và nó là một hậu tố của p, vì vậy ta có thể tìm A từ t bằng các liên kết hậu tố.

Xâu xAx sẽ là xâu palindrome con duy nhất của xâu p + x mà không xuất hiện ở xâu p. Thật vậy, ta thấy tất cả xâu palindrome con mới mà ta chưa thấy trong xâu p phải kết thúc bằng chữ x, và do đó trở thành hâu tố của xâu p + x. Vì xAx là hậu tố palindrome lớn nhất của p + x, tất cả các hậu tố palindrome nhỏ hơn nó có thể được tìm thấy trong một số tiền tố của xAx (vì đối với bất kì hậu tố của palindrome có một tiền tố tương tự tương ứng), và vì thế ta đã thấy chúng trong p.

Vì vậy, để xử lí chữ cái x thêm vào, ta phải đi theo các liên kết hậu tố của t cho đến khi ta tìm thấy A thích hợp (xâu A thích hợp có thể có độ dài -1 nếu ta phải đi đến gốc). Sau đó ta kiểm tra xem có cung nào được gán chữ x mà tương ứng với nút chứa xâu A, nếu không, thêm một cung được gán chữ x nối từ nút chứa xâu A đến nút mới chứa xâu xAx.

Bây giờ ta xét đến các liên kết hậu tố nối từ nút xAx. Nếu nút này đã có từ trước, nút này đã có các liên kết hậu tố và ta không phải làm gì cả. Nếu không, ta cần phải tìm palindrome hậu tố lớn nhất của xAx, có dạng xBx, mà B là một xâu có thể rỗng. Bằng lập luận tương tự như trên, B là palindrome hậu tố của p và có thể đến được từ t bằng các liên kết hậu tố.

Vậy ta đã có được thuật toán xây dựng cây Palindrome. Xử lí từng chữ cái một, lưu trữ palindrome hậu tố lớn nhất t của tiền tố đã xử lí (khởi tạo t là xâu rỗng). Khi xử lí thêm chữ x, ta phải đi qua các liên kết hậu tố xuất phát từ t, cho đến khi ta tìm được palindrome A thích hợp. Xâu xAx sẽ trở thành sẽ trở thành hậu tố palindrome lớn nhất và trở thành nút duy nhất có thể chèn vào cây. Để tạo thêm các liên kết hậu tố ta phải đi theo các liên kết hậu tố cho đến khi tìm thấy xâu palindrome B, có thể thêm được hai chữ x ở hai bên, rồi ta thêm liên kết hậu tố từ nút chứa xâu xAx đến xâu xBx.

Để biết thêm thông tin chi tiết, bạn có thể tham khảo code. (bạn không cần chú ý đến biến num vì nó được cho thêm vào để giải bài toán cụ thể). Bạn có thể thấy code không quá dài cũng như việc cài đặt rất đơn giản.

Độ phức tạp: O(n)

Ứng dụng

- Cho thêm chữ x vào cuối xâu, đếm số lượng palindrome xuất hiện thêm (bằng số nút được cho thêm vào cây Palindrome).

- Đếm số lượng palindrome trong xâu (code ở trên :) ). Bạn có thể dùng thuật toán Manachar để giải, tuy vậy ta nên dùng cây Palindrome vì nó tiện dụng hơn.

- Số lần xuất hiện của Palindrome trong xâu (ngoài cây Palindrome bạn có thể dùng Hash).

Bài tập để luyện tập

Bài 1, Bài 2

SnackDown 2016

HOT HOT HOT! SnackDown 2016 là kỳ thi SnackDown đầu tiên bạn có cơ hội được đến với Mumbai - trụ sở chính của CodeChef.

Bắt đầu từ hè năm ngoái, VNOI đã hợp tác tham gia dịch một số kỳ thi do CodeChef tổ chức mà khởi đầu là SnackDown15. Giống như năm ngoái, SnackDown 16 sẽ có đề tiếng Việt để giúp các bạn phá bỏ rào cản về ngôn ngữ, được tiếp cận nhiều hơn với các cuộc thi lớn của Thế giới.

SnackDown là một kỳ thi lớn được host bởi CodeChef (một trang web lớn của Ấn Độ đã tổ chức hơn 1200 contest), bạn sẽ thi theo team gồm 2 người. SnackDown16 sẽ gồm những vòng sau:

  • Qualifier: vòng sơ tuyển, team bạn chỉ cần làm được ít nhất một bài sẽ được vào vòng sau.
  • Pre-Elimination Round-A: sẽ chọn ra top 1000 teams để đến vòng loại chính thức
  • Pre-Elimination Round-B: sẽ chọn ra top 1000 teams ( không tính những team đã qua Round-A ) để đến vòng loại chính thức.
  • Elimination: Tại vòng đấu loại sẽ có 2000 teams tham gia và chọn ra 50 teams đứng đầu ( 25 teams đến từ Ấn Độ và 25 teams của thế giới ) tham dự kỳ thi Finale diễn ra tại Mumbai.
  • Finale: 50 teams vào đến vòng cuối cùng này sẽ được mời đến thi đấu tại trụ sở của CodeChef.

Giải thưởng thì vô cùng hấp dẫn:

  • 1st Prize: $10.000
  • 2nd Prize: $5.000
  • 3rd Prize: $3.000
  • Và ngọt ngào hơn nữa là bạn chỉ cần lọt vào top 300 teams ở vòng loại, bạn cũng sẽ có một phần quà ( có thể là một chiếc T-Shirt cực kỳ cool )

Đây là cơ hội vô cùng tốt cho các bạn có thể rèn luyện khả năng coding của mình cũng như trau dồi kiến thức. Nếu bạn thật sự giỏi cộng thêm chút may mắn thì những phần thưởng lớn kia sẽ thuộc về bạn.

Hãy đăng ký ngay và tham gia thôi nào <3
Chi tiết về cuộc thi xem tại: http://snackdown.codechef.com/

P/s: Việc dịch đề lần này do đội ngũ Admins VNOI thực hiện. Rất hi vọng các bạn tích cực tham gia để những contests sau chúng mình có thêm động lực làm việc, không chỉ CodeChef mà còn cả những contests lớn khác. 
 

 

 

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 :))

April Lunchtime 2016

Vào 9h tối Thứ bảy ngày 30/04/2016 sẽ diễn ra kỳ thi April Lunchtime 2016. Kỳ thi sẽ diễn ra trong ba tiếng đồng hồ. Thời gian làm bài sẽ là ba tiếng kể từ lúc bắt đầu. Các bạn sẽ đọc các vấn đề mà kỳ thi đưa ra và giải trong thơi gian thi. Trong lúc làm bài nghiêm cấm chép code. Thông tin thêm về kỳ thi bạn có thể click vào đây hay tấm poster ở dưới.

Chúc các bạn tham gia kỳ thi vui vẻ.

Cách xem đề Tiếng Việt

Khi bạn vào một bài, sẽ hiện ra như hình ở dưới đây. Bạn chỉ cần click vào chữ "Vietnamese" trong khung đỏ là xong.

ReadProblemInVN.png

Đăng ký

Để tham gia kỳ thi bạn chỉ cần một tài khoản codechef. Bạn có thể đăng ký ở đây.

Tham gia

Các bạn sẽ vào trang web của kỳ thi trong trong thơi gian kỳ thi diễn ra để đọc bài và nộp bài.

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

April Cook-Off 2016

Tối nay ngày 17/04/2016, cuộc thi April Cook-Off 2016 sẽ được diễn ra lúc 23h. Cuộc thi kéo dài trong 150 phút và đề thi đã được dịch sang Tiếng Việt.

Chúc các bạn tham gia kỳ thi vui vẻ.

Cách xem đề Tiếng Việt

Khi bạn vào một bài, sẽ hiện ra như hình ở dưới đây. Bạn chỉ cần click vào chữ "Vietnamese" trong khung đỏ là xong.

ReadProblemInVN.png

Đăng ký

Để tham gia kỳ thi bạn chỉ cần một tài khoản codechef. Bạn có thể đăng ký ở đây.

Tham gia

Các bạn sẽ vào trang web của kỳ thi trong trong thơi gian kỳ thi diễn ra để đọc bài và nộp bài.

 

April Challenge 2016

Vào 4h30 chiều Thứ sáu ngày 01/04/2016 tất là hôm nay sẽ diễn ra kỳ thi April Challenge 2016. Đây là một kỳ thi diễn ra trong nhiều ngày. Thời gian làm bài sẽ là 10 ngày kể từ lúc bắt đầu. Các bạn sẽ đọc các vấn đề mà kỳ thi đưa ra và giải trong thơi gian thi. Trong lúc làm bài nghiêm cấm chép code. Thông tin thêm về kỳ thi bạn có thể click vào đây hay tấm poster ở dưới.

Chúc các bạn tham gia kỳ thi vui vẻ.

Cách xem đề Tiếng Việt

Khi bạn vào một bài, sẽ hiện ra như hình ở dưới đây. Bạn chỉ cần click vào chữ "Vietnamese" trong khung đỏ là xong.

ReadProblemInVN.png

Đăng ký

Để tham gia kỳ thi bạn chỉ cần một tài khoản codechef. Bạn có thể đăng ký ở đây.

Tham gia

Các bạn sẽ vào trang web của kỳ thi trong trong thơi gian kỳ thi diễn ra để đọc bài và nộp bài.

 

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.

March Challenge 2016

Vào 4h30 chiều Thứ sáu ngày 04/03/2016 tất là hôm nay sẽ diễn ra kỳ thi March Challenge 2016. Đây là một kỳ thi diễn ra trong nhiều ngày. Thời gian làm bài sẽ là 10 ngày kể từ lúc bắt đầu. Các bạn sẽ đọc các vấn đề mà kỳ thi đưa ra và giải trong thơi gian thi. Trong lúc làm bài nghiêm cấm chép code. Thông tin thêm về kỳ thi bạn có thể click vào đây hay tấm poster ở dưới.

Chúc các bạn tham gia kỳ thi vui vẻ.

Cách xem đề Tiếng Việt

Khi bạn vào một bài, sẽ hiện ra như hình ở dưới đây. Bạn chỉ cần click vào chữ "Vietnamese" trong khung đỏ là xong.

ReadProblemInVN.png

Đăng ký

Để tham gia kỳ thi bạn chỉ cần một tài khoản codechef. Bạn có thể đăng ký ở đây.

Tham gia

Các bạn sẽ vào trang web của kỳ thi trong trong thơi gian kỳ thi diễn ra để đọc bài và nộp bài.