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

Kỳ thi VOI 2016 đã kết thúc.

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.

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

Sáng nay vừa diễn ra ACM VN national

• Đề bài
• Bảng rank (sau 4h đầu)

Các bạn vào đây thảo luận nhé :D

Như các bạn đã biết, tính điểm VOJ (gồm bảng rank + lấy dữ liệu từ VOJ về VNOI) đã không hoạt động khá lâu. Hiện tại bọn mình (Bảo) đang sửa phần này. Trong vòng 1 tuần nữa điểm sẽ nhảy loạn xạ, các bạn đừng lo lắng.

Khi nào điểm ổn định mình sẽ hú 1 tiếng nữa cho mọi người biết :D

Vòng loại phía Bắc của ACM Việt Nam vừa diễn ra :D Bạn nào vừa thi vào đây trao đổi nhé.

Cho những ai chưa biết:

• Đề bài
• Rank (1h trước khi kết thúc)

Đội mình làm đc 10 bài (trừ B, bọn mình làm 3^14 nhưng TLE suốt :'( ), không biết các đội làm như nào :D

Trong thời gian này, việc tính điểm & submit gặp nhiều sự cố, nên bọn mình đã phải tắt phần tính điểm để sửa lỗi. Vì vậy trong thời gian này các bài nộp qua VNOI và xếp hạng VOJ sẽ không được cập nhật.

Bọn mình sẽ cố gắng sửa sớm trong 1-2 tuần tới. Rất mong các bạn thông cảm.

IOI 2015 - ngày 1 sẽ diễn ra vào 10h sáng ngày mai ở Kazakhstan. Đội tuyển chúng ta năm nay gồm 4 bạn:

• Nguyễn Tiến Trung Kiên
• Phạm Văn Hạnh
• Nguyễn Việt Dũng
• Phan Đức Nhật Minh (lớp 11)

4 bạn đều học Tổng hợp <3

Nghe nói sẽ có bảng rank online, nhưng giờ chưa có link (bao giờ mình có link sẽ update vào đây).

Các bạn có thể vào đây chém gió, cổ vũ đội tuyển chúng ta, dự đoán kết quả... nhé :v

Mình dự đoán 1 vàng 3 bạc :D

Thay mặt admin VNOI chúc các bạn dành thắng lợi lớn trong kỳ thi ngày mai.

UPD: Link rank --> http://scoreboard.ioinformatics.org/Ranking.html

Chào các bạn,

Như đã thông báo ở đây, T7 tuần này sẽ diễn ra VNOI Marathon vòng 1.

Hè đã đến, và đây là thời gian tuyệt vời nhất để các bạn cày bài và tăng trình độ vì không phải vướng víu công việc ở trường. VNOI Marathon, bắt đầu từ năm 2008, được lập ra với mục tiêu giúp các bạn học được kiến thức mới. Vì vậy bọn mình để thời gian thi 12h khá dài, để các bạn có thể chày cối cả ngày và phát minh ra những ý tưởng kỳ diệu.

Những điều bạn nên biết trước khi thi:

• Bạn chỉ cần có account VOJ là có thể thi
• Bạn đọc đề và submit ở đây. Khi kỳ thi bắt đầu, đề bài sẽ tự động xuất hiện.
• Trong quá trình thi, bài của bạn chỉ được chấm với test ví dụ. Đối với 1 số bài đặc biệt bạn được chấm nhiều test hơn, thì sẽ được nói cụ thể rõ ràng trong đề bài.
• Bạn được nộp bài nhiều lần, kết quả cao nhất sẽ được tính là kết quả cuối.
• Nếu bài của bạn chạy trên máy đúng, mà nộp lên không hiểu sao sai, thì bạn có thể submit thử ở ideone, nhưng chú ý là bạn cần đặt chế độ private, nếu không các thí sinh khác có thể tình cờ và bất ngờ đọc được code của bạn. Trong trường hợp 2 bài thí sinh giống nhau, bọn mình có quyền chấm thành 0 điểm mà không nhất thiết phải giải thích thêm.
• Trong quá trình thi, nếu có thắc mắc gì, các bạn có thể đặt câu hỏi ở đây. Bọn mình sẽ cố gắng giải đáp thắc mắc trong thời gian sớm nhất có thể.
• Trong trường hợp đề bài / việc chấm bài có vấn đề, các thông báo sẽ được đăng ở đây. Vì vậy các bạn nên thỉnh thoảng quay lại kiểm tra topic này.

Muốn bùng cháy,

VNOI Admin team.

UPDATE#1: Link đề bài

UPDATE#2: Tạm thời trình chấm bài VMCUT đang bị sai và sẽ được sửa trong thời gian sớm nhất. Các bài nộp của các bạn sẽ được rejudge sau khi trình chấm được sửa xong.

UPDATE#3: Hiện tại trình chấm bài VMCUT đã chính xác. Các bài đã được rejudge

UPDATE#4: Đề bài VMSALARY bị viết sai. Đề đã được sửa lại:

"Nếu nhân viên x là cấp trên trực tiếp của nhân viên y và nhân viên y là cấp trên của nhân viên z thì x là cấp trên (nhưng không trực tiếp) của nhân viên z."

UPDATE#5: 3 bài VMSALARY, VMDAOBIT và VMPIZZA đã được chấm xong. Bài VMCUT do có 1 chút sự cố kĩ thuật nên sẽ được chấm sau. Dự kiến bài VMCUT sẽ được chấm xong trong 1-2h nữa.

UPDATE#6: Mình đang rejudge lại bài VMPIZZA do có 2 test yếu. Nếu các bạn 100 điểm thì khả năng cao là sẽ không bị ảnh hưởng gì. Bài VMCUT mình đang rejudge lại từ đầu do rejudge sai khiến các bạn bị 0

UPDATE#7: Mình đã add 3 bài VMPIZZA, VMSALARY, VMDAOBIT lên VOJ. Bài VMCUT sẽ được up lên sau.

UPDATE#8: Bảng rank đã có ở đây. Với những bạn nộp nhiều lần, kết quả cao nhất sẽ được tính.

Vậy là VNOI mới đã ra mắt các bạn được 2 tuần. Với hầu hết team admin bọn mình, đây là lần đầu bọn mình ra mắt 1 trang web có người dùng. Cá nhân mình thì trước khi làm VNOI mình cũng biết sơ sơ về lý thuyết làm web, nhưng kinh nghiệm thực tế thì cũng chưa có :D, nên vô cùng háo hức & lo lắng, như đang chăm sóc đứa con đầu lòng của mình vậy :v

1 chút tổng kết trong thời gian qua:

• Sau 2 tuần, chúng ta có gần 450 user, hơn 250 bạn đã kết nối account VOJ.
• Số lượt submit lên VOJ qua VNOI là chưa đến 400. Mình biết là hiện tại có rất nhiều lỗi khi submit qua VNOI như ko submit đc, submit đc nhưng ko đc chấm, kết quả chấm bị sai so với VOJ. Bọn mình đang cố gắng khắc phục những lỗi này. Hiện tại theo mình biết thì các bạn đã có thể submit bình thường. Nếu bạn nào vẫn còn bị lỗi thì hãy nói cho bọn mình ngay ở đây.
• Số bài post trên VNOI chỉ hơn 300, trong đó chắc hầu hết là của admin :D 1 phần cũng có thể do bọn mình ko thân thiện lắm, ví dụ như ở đây. Mình hi vọng là các bạn dần dần sẽ bớt ngại, bớt sợ admin và nói nhiều hơn :D Các bạn nói ngây thơ hoặc linh tinh cũng đc, cơ mà cứ tự nhiên nói cho có không khí :)). Nếu các bạn để ý thì giờ nếu bị trừ cũng không ảnh hưởng gì (hiện tại, đóng góp không bị giảm và bạn còn có thể tự cộng cho chính mình nếu cảm thấy mình nói quá hay).
• Hiện tại đã có hơn 20 bài viết trong Thư viện, và mình hi vọng con số đó sẽ còn tăng lên nhiều.
  • Rất cảm ơn 2 bạn ttdpro98 và only_love97 đã đóng góp rất nhiều bài viết cho Thư viện VNOI :D
• Thỉnh thoảng server vẫn bị không vào được và hiện lỗi 500, 502. Thông thường là do bọn mình đang cập nhật tính năng mới cho VNOI, hoặc đang phải sửa sự cố khẩn cấp nào đó. Nếu gặp trường hợp này các bạn có thể quay lại trong 10' hoặc 15' sau, lúc đó hi vọng bọn mình đã kịp thời sửa :D
• 1 vài tính năng mới:
  • Hình quả chuông bên góc phải trên: mỗi lần có người trả lời bài viết của bạn, bạn sẽ nhận được thông báo (hi vọng các bạn post bài nhiều hơn để test tính năng này :)))
  • Ở phần danh sách bài tập, đã có đánh dấu xanh với những bài bạn đã làm được.
• 1 vài tính năng sắp ra mắt:
  • Màu user ở bảng rank, forum (hiện tại đã có ở bài viết trên trang chủ :D)
  • Ẩn các bài đã làm ở danh sách bài tập
  • [Hot] Xem chi tiết kết quả chấm bài VOJ (test nào AC, test nào WA, test nào TLE...). Dự kiến tính năng này sẽ ra mắt trong vòng 1 - 2 tháng nữa. Để bọn mình có thể test tính năng này khi ra mắt, hi vọng các bạn tích cực nộp bài qua VNOI hơn :p
• Hôm mới ra mắt, forum có bị darksabers hack (post vài nghìn bài trong khoảng thời gian ngắn). Hiện bạn ý đã vào team admin và giúp bọn mình hoàn thiện trang web hơn :). Team làm web VNOI từ đầu đến giờ gồm có mình, iamquang95, khoaplt, tmbao, darksabers, net12k44, quochuu_96, infrmtcs và Hoàng Yến. Tuy nhiên hiện giờ có 1 số bạn đã không làm tiếp nữa, và mình đang tuyển thêm người mới. Nếu bạn nào muốn gia nhập team thì có thể nói với mình, nếu bạn không biết code web thì mình có thể dạy từ đầu.

Nếu có phát hiện bug, các bạn có thể trả lời vào ngay trong topic này hoặc ở đây :D

Rất cảm ơn các bạn,

RR