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

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

Thảo luận VO16 - Ngày 2

Vậy là VNOI Online 2016 đã chính thức kết thúc có thể gọi là tốt đẹp, mặc dù ngày 2 có một số sự cố nhỏ. Kết quả sẽ được có muộn nhất là vào ngày mai. Trong lúc chờ đợi kết quả, các bạn có thể tham gia thảo luận, chém gió về thuật toán ngày 2 trong topic này, đồng thời đóng góp ý kiến về đề thi =))

Thảo luận VO16 - Ngày 1

Vậy là thời gian thi chính thức của ngày 1 đã hết. Cảm nhận của các bạn về đề thi ngày 1 thế nào? Topic này là nơi để các bạn chia sẻ suy nghĩ, thảo luận về thuật toán, ý kiến, chửi bới về đề thi cũng như khủng bố tinh thần nhau trước khi bước vào ngày thi 2.

VO2016

Chào tất cả mọi người :")
Như thông lệ hàng năm, VNOI Online sẽ được tổ chức trước khi kỳ thi HSG quốc gia diễn ra để giúp các bạn chuẩn bị và luyện tập tốt nhất.

Thông tin chi tiết về kỳ thi:

  • Thời gian: 3 tiếng, từ 14h đến 17h ngày 26 và ngày 27 tháng 12
  • Đề thi sẽ tương tự như đề HSG quốc gia, mỗi ngày sẽ thi 3 bài.
  • Đối tượng tham gia: tất cả mọi người, chỉ cần bạn có nick VOJ
  • Thi online tại http://www.spoj.com/VO16/

Các Admins mong rằng sẽ góp được chút công sức của mình để giúp các bạn có thêm sự tự tin, tính tập trung và cẩn thận trước khi bước vào kỳ thi thật sự. Hy vọng kỳ thi sẽ mang đến cho các bạn nhiều điều bổ ích và lý thú. 

Thông báo 1: Vì các sự cố nảy sinh trong lúc thi. Các bạn sẽ được thêm 15 phút vào thời gian làm bài. Tất là kỳ thi sẽ diễn ra trong 3h15p thay vì là 3h như ban đầu. Xin các bạn thông cảm.

USACO 2016

USACO là kỳ thi lập trình do Mỹ tổ chức dành cho các học sinh cấp 3 nhằm mục đích training và chọn đội tuyển olympic cho Mỹ. Kỳ thi được tổ chức online nhằm tạo cơ hội cho các bạn cùng tham gia và tranh tài. 

USACO được chia làm 4 bảng Đồng, Bạc, Vàng và Platinum. Sau mỗi vòng thi bạn sẽ giữ nguyên bảng thi hoặc lên bảng thi mới tùy thuộc vào thành tích của bạn.

Năm nay sẽ có 4 vòng thi online : 

Dec 11-14: First Contest 
Jan 15-18: Second Contest 
Feb 19-22: Third Contest 
Apr 1-4: US Open 

Ngay bây giờ các bạn có thể tham gia kỳ thi đầu tiên của USACO tại địa chỉ http://www.usaco.org/index.php

2015 ACM-ICPC Asia Singapore regional.

Vào 8:00 sáng 10/12 (theo giờ Việt Nam), Kỳ thi ACM Asia Singapore Regional Contest 2015 sẽ được diễn ra. Các bạn có thể tham gia online tại địa chỉ: https://open.kattis.com/contests/asiasg15open

Các team có người Việt Nam :3

University of Engineering and Technology - VNU 
Team name:  MEGABYTE

  • Ho Dac Phuong, Coach
  • Duc Thien Bui, Contestant 
  • Hoang Mai Huy, Contestant
  • Phuc Hoang Vu, Contestant

Ho Chi Minh City University of Science  
Team name:  HCMUS - Shine

  • Nguyen Son Tung Pham, Coach
  • Yen Thanh Le, Contestant
  • Viet Khoi Pham, Contestant
  • Minh Bao Truong, Contestant

Can Tho University 
Team name:  CTU.A2LTT

  • Nguyen Khang Pham, Coach
  • Nguyen Hoang Nguyen, Contestant
  • Anh Tran Tuan, Contestant
  • Lan Truong Thi Phuong, Contestant

Can Tho University  
Team name:  CTU.SCORERS

  • Nguyen Khang Pham, Coach
  • Quoc Nhan Nguyen, Contestant
  • Tan Cuong Nguyen, Contestant
  • Thong Nguyen The, Contestant

FPT University   
Team name:  Budweiser

  • Anh Dung Huynh, Coach
  • Minh Duc Bach, Contestant
  • Dai Thien Long Hoang, Contestant
  • Hung Son Le, Contestant

Nanyang Technological University   
Team name:  Secrete

  • Rui Fan, Coach
  • Ngoc Hai Dinh, Contestant
  • Duy Duc Doan, Contestant
  • Hoang Yen Nguyen, Contestant

National University of Singapore  
Team name:  2Ez2ac

  • Jin Zhao, Coach
  • Hiep Bui, Contestant
  • Thanh Dat Duong, Contestant
  • Dinh Quang Dat Vu, Contestant

National University of Singapore 
Team name:  Game of Throws

  • Jin Zhao, Coach
  • Quang Dung Nguyen, Contestant
  • Huu Thanh Nguyen, Contestant
  • Viet Dung Nguyen, Contestant

National University of Singapore  
Team name:  RRwatameda

  • Jin Zhao, Coach
  • Tan Sy Nguyen Nguyen, Contestant
  • Hung Tam Nguyen, Contestant
  • Thanh Trung Nguyen, Contestant

National University of Singapore  
Team name:  MST

  • Jin Zhao, Coach
  • Manh Le Xuan, Contestant
  • Sharon Lynn, Contestant
  • Tung Nguyen Khac, Contestant

National University of Singapore 
Team name:  PS Hunter

  • Jin Zhao, Coach
  • Zhuo Chen, Contestant
  • Cao Nhat Linh Nguyen, Contestant
  • Khanh Truong, Contestant

Còn thiếu gì thì comment để mình bổ sung nha <3 

COCI 2015/2016 #3

Vào 21:00  tối nay 28/11/2015 COCI #3 sẽ diễn ra

Đề thì sẽ gồm 6 bài theo kiểu oi trong thời gian 3 tiếng đồng hồ.

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

2015 ACM-ICPC Asia Hanoi Regional!!!

Ngày mai sẽ diễn ra cuộc chiến được mong đợi nhất của ACM VN :3

Thời gian bắt đầu: 7.45 sáng (theo lịch, hi vọng ko bị hoãn :v)

Sau các vòng online cũng như các kỳ thi trên mạng thì theo mình đánh giá lần này 3 đội mạnh nhất của VN là:

  • BYTE - ĐH Công nghệ, gồm Kiên, Khánh, Hạnh (Codeforces). Trong đó Hạnh là HCV IOI 2015, Kiên có 1 HCD va 1 HCB IOI 2014 & 2015, Khánh HC APIO. Với phong độ ổn định và phối hợp ăn ý từ cấp 3, mình nghĩ team có 50% khả năng vô địch (ko kể các đội TQ). Đội Byte đã #2 subregional ở Thái (thua National Taiwan Univ) và đã có khá chắc chắn vé vào WF.
  • Shine - HCMUS, gồm Yên Thanh, Bảo và Khôi (Codeforces). Trong đó Yên Thanh đã vào WF 2013. Với kinh nghiệm dày dặn, mình nghĩ team có khoảng 20% vô địch. Đội Shine ngoài regional VN sẽ còn thi ở regional Singapore vào tháng 12.
  • No name YET - FPT, gồm Ngọc Trung, Hiệp và 1 bạn nào đó mình ko rõ (Codeforces). Trong đó Ngọc Trung là huyền thoại HCV IMO, mới học code vài tháng nhưng trình độ đã vô cùng khủng khiếp. Mình nghĩ team này có khoảng 14% khả năng vô địch, phụ thuộc nhiều vào đề. Đội này đã thi ở regional Phuket và đứng #4 subregional, gần như chưa có khả năng nào vào WF, vì vậy đây sẽ là cuộc chiến quyết định của team.

Theo mình nghiên cứu thì lần này ko có đội nước ngoài nào mạnh lắm (ko kể các đội TQ do ko cùng subregional). Đội nước ngoài mạnh nhất có vẻ là Taipei-Meow của National Taiwan Univ, tuy nhiên đây ko phải là đội mạnh nhất trường họ. Đội mạnh nhất NTU Taiwan năm nay có vẻ là |_0|_1, đã đi WF năm ngoái và vừa vô địch subregional Thái, tuy nhiên ở Thái đội này cũng chỉ nhỉnh hơn Byte 1 chút :3

Các bạn cổ vũ cho đội nào? :3

Link rank

Final rank

Gần giống như dự đoán:

1. Byte

2. HCMUS Shine

4. Taipei Meow

Chia buồn với đội FPT :(