Vào lúc 8h tối thứ tư (22/06/2022), mình sẽ tổ chức buổi trình bày thứ tư trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Cách nhân nhanh hai đa thức trong ~O(n^{\log_2 3})~ và ứng dụng của việc nhân đa thức trong bài toán Cái túi phiên bản đếm, bài toán đếm cấp số cộng độ dài 3 trong một mảng, bài toán tìm số đoạn thẳng có cùng độ dài và một bài toán xử lí xâu.
• Giới thiệu sơ lược về phương pháp Chia để trị trên cây và phương pháp Chia để trị trên đa giác.

Để có thể theo dõi bài trình bày, bạn cần nắm được các kiến thức Tổ hợp trong chương trình Đại số và Giải tích 11 hoặc trong chương trình Toán 10 mới.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây .

Xin chào các bạn,

😉 Chỉ còn ít ngày nữa thôi, VNOI CUP 2022 sẽ chính thức khởi tranh rồi. Những ngày qua, BTC đã nhận được một số câu hỏi, băn khoăn về cuộc thi, cùng chúng mình giải đáp những thắc mắc này nhé!

❓ “Mình không biết C/C++ hay Pascal như các bạn thi HSG môn Tin, liệu cuộc thi có cho phép các ngôn ngữ lập trình khác không?”

VNOI CUP 2022 được tổ chức trên nền tảng VNOJ và có hỗ trợ các ngôn ngữ khác ngoài Pascal, C/C++ như Java, Python, Kotlin.

❓ “Mình chỉ mới tiếp xúc với Lập trình thi đấu thôi, liệu mình có tham gia VNOI CUP được không?”

Cuộc thi được tổ chức với mục tiêu khuyến khích, phát triển phong trào Lập trình thi đấu tại Việt Nam và rất hoan nghênh sự tham gia nhiệt tình của tất cả các bạn. Ngoài ~75~ áo dành tặng cho ~75~ thí sinh xuất sắc nhất, BTC đã cân nhắc và quyết định dành tặng ~75~ áo VNOI CUP cho ~75~ thí sinh may mắn có tổng điểm ~3~ vòng trên ~0~ như món quà động viên tinh thần tất cả các thí sinh tham dự ❤️.

❓ “Mình muốn tham dự cuộc thi thì mình có thể đăng ký ở đâu?”

Các vòng loại VNOI CUP 2022 được tổ chức online trên nền tảng VNOJ và đăng ký tham gia trực tiếp như các contest khác trên hệ thống. Nếu chưa có tài khoản VNOJ, các bạn có thể đăng ký tại đây.

❓ “VNOI có thể bật mí những tips giúp đạt thứ hạng cao trong cuộc thi không ạ?”

Câu nói được nhắc tới trong mọi kì thi - “Câu dễ làm trước, câu khó làm sau”. Điểm của các bài đã được BTC sắp xếp tăng dần theo độ khó, mỗi bài đều có subtask. Vậy nên các bạn hãy ưu tiên làm từ các bài dễ và đừng bỏ qua việc làm các subtask nhé! Ngoài ra, hãy code thật cẩn thận vì điểm penalty chính là yếu tố phân hạng ngay sau điểm của bài đó.

✨ Mọi thắc mắc về cuộc thi, các bạn có thể gửi tin nhắn về page VNOI. 😉 Đừng quên rằng bạn có hẹn cùng chúng mình tại Vòng loại thứ nhất VNOI CUP 2022 vào ~20h-22h30’~ ngày ~18/6~ nhé!

📢 VNOI CUP 2022 đã chính thức khởi tranh rồi, các coders tài năng của chúng ta đã sẵn sàng chưa?

👉 Vào thứ ~7~ tới ~(18/6)~, vòng loại online thứ nhất của cuộc thi VNOI CUP 2022 sẽ diễn ra trên nền tảng VNOJ, hé lộ ~2~ thí sinh tài năng đầu tiên giành vé vào vòng Chung kết diễn ra tại Đà Nẵng vào tháng ~7~. Ngay sau đây, cùng chúng mình điểm qua một số thông tin của vòng thi nào!

🕗 Thời gian: ~20h-22h30’~ - thứ bảy, ngày ~18/6/2022~

🔗 Địa điểm: https://oj.vnoi.info/contest/vnoicup22_r1

✨ Hình thức:

• Tổ chức dưới hình thức contest tính rating.
• Thời lượng: ~150'~
• Số lượng: ~5~ bài
• Đề bài có ~2~ phiên bản Tiếng Anh và Tiếng Việt. Các bạn có thể lựa chọn bằng cách sử dụng biểu tượng ~2~ lá cờ trên thanh navigation bar.
• Cách thức tính điểm:
  • Điểm của các bài tăng dần theo độ khó; mỗi bài có thể gồm nhiều subtask; thí sinh chỉ được điểm của subtask khi đúng hết tất cả test case của subtask đó.
  • Điểm của bài bằng tổng điểm tất cả các subtask.
  • Điểm penalty được tính là thời gian của lần nộp tăng điểm cuối cùng + ~5~ phút cho mỗi lần nộp sai. Thí sinh được phân hạng theo điểm, nếu bằng điểm sẽ xét tới penalty tăng dần.

✨ Theo dõi chi tiết thể lệ cuộc thi tại đây.

📌 Đừng quên rằng, ~4~ vé tham dự Chung kết & ~150~ áo VNOI CUP vẫn đang chờ đợi các bạn tại bảng xếp hạng tổng điểm ~3~ vòng loại đó, hãy nỗ lực hết mình ở tất cả vòng thi nhé! 😉

❤️ Chúc các bạn có những trải nghiệm vui vẻ tại vòng thi này!

Vào lúc 8h tối thứ ba (14/06/2022), mình sẽ tổ chức buổi trình bày thứ ba trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của tập 3, tập 4, và có thể là tập 5 là "Chia để trị."

Để có thể theo dõi được bài trình bày này, các bạn cần nắm được phương pháp chứng minh quy nạp, cách phân tích độ phức tạp tính toán, cách viết hàm đệ quy. Nếu được thì các bạn cũng nên tìm hiểu trước về hàm lô-ga-rít.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Hàm lô-ga-rít và ứng dụng trong một số bài tập tin học.
• Tìm kiếm nhị phân và ứng dụng trong các bài toán tìm giá trị lớn nhất hoặc nhỏ nhất.
• Cách tính nhanh ~x^n~ với ~n~ lớn.
• Thuật toán Mergesort để sắp xếp dãy số trong ~O(n\log{n})~ trong trường hợp xấu nhất.
• Cách giải bài toán cặp điểm gần nhất (và bài toán đếm số cặp nghịch thế nếu có thời gian)
• Phân tích độ phức tạp tính toán của một thuật toán sử dụng phương pháp Chia để trị bằng phương pháp hình chữ nhật.

Nội dung của một số bài trình bày tiếp theo:

• Cây phân đoạn (Segment Tree) dưới góc nhìn của phương pháp Chia để trị.
• Cách nhân nhanh hai đa thức trong ~O(n^{1.6})~ và ứng dụng.
• Giới thiệu sơ qua về phương pháp Chia để trị trên cây và Chia để trị trên đa giác.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Xin chào các bạn,

🔥 Sau màn khởi động VNOI CUP ~2022~, chúng mình đã nhận được rất nhiều câu hỏi quan tâm tới các mốc thời gian cũng như cách thức tham dự VNOI CUP. Không để các bạn chờ đợi lâu hơn nữa, hãy cũng VNOI tìm hiểu các thông tin về ~3~ vòng loại của VNOI CUP ~2022~ ngay thôi nào!

Cơ cấu giải thưởng

BTC sẽ dành tặng ~150~ áo VNOI CUP cho các thí sinh, trong đó:

• ~75~ áo sẽ được dành tặng cho top ~75~ thí sinh xuất sắc nhất trên bảng xếp hạng tổng điểm ~3~ vòng thi.
• Ngoài ra, sẽ có ~75~ áo được dành tặng cho ~75~ thí sinh may mắn nhất có tổng điểm ~3~ vòng trên ~0~.
• Lưu ý: Các thí sinh tham gia xếp hạng nhận quà và giành quyền tham dự Chung kết VNOI CUP ~2022~ phải dưới ~30~ tuổi tính đến ngày ~18/6/2022~, tính theo ngày tháng năm sinh trên giấy tờ chứng minh hợp lệ.

Các mốc thời gian & cấu trúc kì thi

Từ ~18/6 - 2/7~, các vòng loại online được tổ chức trên nền tảng VNOJ dưới hình thức contest có tính rating. Thí sinh có thể đăng ký tham gia như các contest khác trên hệ thống.

• Vòng loại thứ nhất: ~20h-22h30'~ ngày ~18/6~
• Vòng loại thứ hai: ~20h-22h30'~ ngày ~25/6~
• Vòng loại thứ ba: ~20h-22h30'~ ngày ~2/7~

Thời lượng mỗi vòng thi là ~150~ phút với ~5~ bài tập. Các bài tập trong contest có subtask, bạn chỉ được điểm của subtask khi đúng hết các test case của subtask đó.

Cách thức dự thi

• Các vòng loại VNOI CUP sẽ được tổ chức tại địa chỉ: https://oj.vnoi.info/contests/
• Thí sinh đăng ký tài khoản dự thi tại địa chỉ: https://oj.vnoi.info/accounts/register/
• Các bạn có thể theo dõi các thông tin chi tiết về cuộc thi qua địa chỉ: https://cup.vnoi.info/rule/
• Lưu ý, trong cả ~3~ vòng thi, thí sinh chỉ được sử dụng duy nhất ~1~ tài khoản. BTC sẽ hủy kết quả tất cả các vòng thi và cấm vĩnh viễn tài khoản VNOJ của thí sinh vi phạm.

😉 Vòng loại VNOI CUP đang tới rất gần rồi, đừng quên theo dõi fanpage để cập nhật các thông tin mới nhất về cuộc thi nhé!

Vào lúc 8h tối thứ tư tuần này (08/06/2022), mình sẽ tổ chức buổi trình bày thứ hai trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của buổi thứ hai là "Đánh giá hiệu quả thuật toán." Để có thể theo dõi bài trình bày này, bạn cần nắm được cách chứng minh mệnh đề chứa dấu ~\forall, \exists~ và mệnh đề "nếu ... thì ..." (đã được trình bày ở bài đầu tiên), nắm được khái niệm thuật toán, và biết một số bất đẳng thức đơn giản như ~\forall x \in \mathbb{R}: x^2 \geq 0~ và bất đẳng thức trung bình cộng - trung bình nhân.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Cách phân tích độ phức tạp của một thuật toán.
• Biểu diễn độ phức tạp bằng kí pháp chữ ~O~ lớn. Sử dụng kí pháp chữ ~O~ lớn để đánh giá xem thuật toán có chạy đủ nhanh trong thời gian quy định hay không.
• Một số kĩ thuật tăng tốc độ chạy của thuật toán như lợi dụng hằng số nhỏ của ~\sum i^k~, sử dụng bitset, hai con trỏ, và chia căn đơn giản.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Bài 1:

Phần a:

~P = \sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}}~

Sử dụng hằng đẳng thức ~(a+b)^3 = a^3 + b^3 +3ab(a+b)~ với ~a = \sqrt[3]{7 + 5\sqrt{2}}~ và ~b = \sqrt[3]{7 - 5\sqrt{2}}~, ta có

~P^3 = (7 + 5\sqrt{2}) + (7 - 5\sqrt{2}) + 3\sqrt[3]{7 + 5\sqrt{2}}\sqrt[3]{7 - 5\sqrt{2}}(\sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}})~

~\Rightarrow P^3 = 14 +3\sqrt[3]{49-25 \times 2}P~

~\Rightarrow P^3 = 14 - 3P~

~\Rightarrow P^3 - 3P - 14 = 0~

Ta thấy ~2~ là một nghiệm của phương trình ẩn ~P~ này nên

~P^3 - 2P^2 + 2P^2 - 4P + 7P - 14 = 0~

~\Rightarrow (P-2)(P^2 + 2P + 7) = 0~

~\Rightarrow (P-2)((P+1)^2 + 6) = 0~

Do ~(P+1)^2 + 6 \geq 6 > 0~ nên ~P - 2 = 0 \Rightarrow \boxed{P = 2}~

Phần b:

Giả sử ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Do ~0 \in \mathbb{Z}, P(0) \in \mathbb{Z}~ nên ~c \in \mathbb{Z}~

Do ~1 \in \mathbb{Z}, P(1) \in \mathbb{Z}~ nên ~a + b + c \in \mathbb{Z}~. Do ~\begin{cases} c \in \mathbb{Z} \\ a + b + c \in \mathbb{Z} \end{cases} \Rightarrow (a+b+c) - c \in \mathbb{Z} \Rightarrow a + b \in \mathbb{Z}~

Do ~-1 \in \mathbb{Z}, P(-1) \in \mathbb{Z}~ nên ~a - b + c \in \mathbb{Z}~.

Do ~\begin{cases} a+b+c \in \mathbb{Z} \\ a - b + c \in \mathbb{Z} \end{cases}~ nên ~2a + 2c \in \mathbb{Z}~.

Do ~c \in \mathbb{Z}~ nên ~-2c \in \mathbb{Z}~

Do ~\begin{cases} 2a + 2c \in \mathbb{Z} \\ -2c \in \mathbb{Z} \end{cases}~ nên ~2a \in \mathbb{Z}~

Ta có thể kết luận:

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z} \Rightarrow \begin{cases} 2a \in \mathbb{Z} \\ a + b \in \mathbb{Z} \\ c \in \mathbb{Z} \end{cases}~

Giả sử ~2a, a+b, c \in \mathbb{Z}~, ta cần chứng minh ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Chọn số ~x \in \mathbb{Z}~ bất kì.

Do ~2a \in \mathbb{Z}~, hoặc ~a \in \mathbb{Z}~ hoặc ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Trường hợp 1: Giả sử ~a \in \mathbb{Z}~.

Do ~\begin{cases} a + b \in \mathbb{Z} \\ a \in \mathbb{Z} \end{cases}~ nên ~b \in \mathbb{Z}~

Do ~a,b,c,x \in \mathbb{Z}~ nên ~P(x) \in \mathbb{Z}~

Trường hợp 2: Giả sử ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Do ~a+b \in \mathbb{Z}~, điều này nghĩa là ~b = \frac{n}{2}~ với ~n \in \mathbb{Z}~

Khi đó ~P(x) = \frac{m}{2}x^2 + \frac{n}{2}x + c~

Do ~x \in \mathbb{Z}~ nên ~x = 2k~ hoặc ~x = 2k+1~ với ~k \in \mathbb{Z}~

Trường hợp 2.1: Nếu ~x = 2k~ thì ~P(x) = \frac{m}{2}4k^2 + \frac{n}{2}2k + c = m(2k^2) + nk + c \in \mathbb{Z}~

Trường hợp 2.2: Nếu ~x = 2k+1~ thì ~P(x) = \frac{m}{2}(4k^2 + 2k + 1) + \frac{n}{2}(2k+1) + c = m(2k^2 + k) + \frac{m}{2} + nk + \frac{n}{2} + c = m(2k^2 + k) + a + nk + b + c \in \mathbb{Z}~

Tổng hợp hai trường hợp 2.1 và 2.2, ta được ~P(x) \in \mathbb{Z}~

Do ở cả hai trường hợp, ta được ~P(x) \in \mathbb{Z}~ và ta chọn số ~x \in \mathbb{Z}~ bất kì, ta có thể kết luận

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

và đây là điều phải chứng minh.

Bài 4:

Giả sử có cách viết 10 số thỏa mãn yêu cầu bài toán.

Đánh số các điểm như hình dưới đây

Ta có:

~a_1 + a_5 + a_2 = a_1 + a_8 + a_4 = ... = k~

~\Rightarrow 3(a_1 + a_2 + a_3 + a_4) + a_5 + a_6 + a_7 + a_8 + a_9 + a_{10} = 6k~

~\Rightarrow 2(a_1 + a_2 + a_3 + a_4) + \sum_{i=1}^{10} a_i = 6k~

~\Rightarrow 2(a_1+a_2+a_3+a_4) + 45 = 6k~

~\Rightarrow 45 = 2(3k + a_1 + a_2 + a_3 + a_4) \Rightarrow 2 \mid 45~ (vô lí)

Do đó, giả sử ban đầu sai. Nói cách khác, không có cách viết 10 số thỏa mãn yêu cầu bài toán.

Bài 5:

Phần a:

Gọi 5 điểm được cho là ~A_1, A_2, A_3, A_4, A_5~

Gọi ~H~ là tập các đỉnh của bao lồi của ~5~ điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 5~

Trường hợp 1: ~|H| = 3~

Không làm mất tính tổng quát, giả sử ~H = \{A_1, A_2, A_3\}~. Khi đó, ~A_4~ nằm trong tam giác ~A_1A_2A_3~

~\Rightarrow \angle A_1A_4A_2 + \angle A_2A_4A_3 + \angle A_3A_4A_1 = 360^o~

Khi đó, một trong ba góc này sẽ phải lớn hơn hoặc bằng ~120^o~, tức lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là ~\angle A_1A_4A_2~. Khi đó tam giác ~A_1A_4A_2~ là tam giác tù, tức ta tìm được một tam giác tù.

Trường hợp 2: ~|H| = 4~

Không làm mất tính tổng quát, giả sử bao lồi là tứ giác ~A_1A_2A_3A_4~. Khi đó, ~A_5~ nằm trong tứ giác ~A_1A_2A_3A_4~

~\Rightarrow \angle A_1A_5A_2 + \angle A_2A_5A_3 + \angle A_3A_5A_4 + \angle A_4A_5A_1 = 360^o~

Giả dụ cả bốn góc này không có góc tù nào. Khi đó, cả bốn góc đều có số đo ~90^o~. Ta sẽ có ~\angle A_1A_5A_2 + \angle A_2A_5A_3 = 180^o \Rightarrow \angle A_1A_5A_3 = 180^o \Rightarrow A_1, A_5, A_3~ thẳng hàng, trái với giả thiết ban đầu rằng không có ba điểm nào thẳng hàng. Vì thế giả dụ ban đầu sai, tức ít nhất một trong bốn góc phải là góc tù, và vì thế ta tìm được một tam giác tù.

Trường hợp 3: ~|H| = 5~

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3A_4A_5~. Do đây là đa giác lồi, ta có

~\sum_{i=1}^5 \angle A_i = 180 \times 3 = 540^o~

Do ~\frac{540^o}{5} = 108^o~, sẽ có ít nhất một góc lớn hơn hoặc bằng ~108^o~, tức một góc lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là góc ~A_1A_2A_3~, khi đó tam giác ~A_1A_2A_3~ tù.

Từ ba trường hợp trên, ta có thể kết luận rằng cho 5 điểm bất kì trên mặt phẳng sao cho không có ba điểm nào thẳng hàng, ta có thể tìm được một tam giác có đỉnh là 3 trong 5 điểm được cho.

Phần b:

Gọi 2022 điểm được cho là ~A_1, A_2, A_3, A_4, ..., A_{2022}~

Gọi ~H~ là tập đỉnh của bao lồi của 2022 điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 2022~.

Gọi ~k~ là số điểm nằm trong bao lồi. Ta có ~k = 2022 - |H|~

Nếu ~|H| \leq 4~ thì ~k \geq 2018~. Với mỗi điểm trong bao lồi, ta có thể tìm được một tam giác tù có điểm đó là đỉnh và hai đỉnh còn lại là hai đỉnh của đa giác bao lồi, và vì thế ta tìm được ít nhất ~k~ tam giác tù. Do ~k \geq 2018~, ta có điều phải chứng minh.

Xét trường hợp ~|H| \leq 5~.

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3...A_n~ (~n = |H| = 2022 - k~)

Chia đa giác thành các tam giác ~A_1A_2A_3~, ~A_1A_3A_4~, ..., ~A_1A_{n-1}A_n~. Do không có ba điểm nào thẳng hàng, mỗi điểm trong bao lồi sẽ nằm trọn trong một trong các đa giác này, và từ đó với mỗi điểm trong bao lồi, ta tìm được một tam giác tù có điểm đó là một đỉnh và hai đỉnh còn lại là hai đỉnh của tam giác chứa nó (và đồng thời là hai đỉnh của đa giác bao lồi). Nói cách khác, ta tìm được ~k~ tam giác tù.

Ta có:

~\sum_{i=1}^n \angle A_i = 180(n-2)~

Giả dụ có nhiều hơn 4 góc không tù. Không làm mất tính tổng quát, giả sử các góc ~A_1, A_2, A_3, A_4, A_5~ là các góc không tù, khi đó ~\sum_{i=6}^n \angle A_i > 180(n-2) - 450 = 180(n - \frac{9}{2})~

Nếu ~n = 5~ thì điều này nghĩa là ~0 > 90~, vô lí.

Nếu ~n > 5~ thì điều này nghĩa là có một góc ~\angle A_i \geq \frac{180(n-\frac{9}{2})}{n-5}~. Mà khi ~n > 5~, ~\frac{180(n-\frac{9}{2})}{n-5} > 180~ nên ~\angle A_i > 180^o~. Điều này vô lí do một góc của một đa giác lồi không thể có số đo vượt quá ~180^o~

Do cả hai trường hợp đều dẫn đến điều vô lí, điều này nghĩa là có nhiều nhất 4 góc không tù, tức đa giác bao lồi có ít nhất ~n - 4~ góc tù. Mỗi một góc tù sẽ tạo ra một tam giác tù nên ta có ít nhất ~n - 4~ tam giác tù.

Tổng số tam giác tù ít nhất là ~k + (n-4) = n+k - 4 = 2022 - 4 = 2018~, tức là ta sẽ tìm được ít nhất 2018 tam giác tù.

Kết hợp hai trường hợp, ta có được điều phải chứng minh.