HỎI ĐÁP LẬP TRÌNH THI HỌC SINH GIỎI

Lập Trình Thuật Toán

Hỏi – Đáp lập trình thi học sinh giỏi Tin học

Những câu hỏi học sinh và phụ huynh hay gửi về: chọn C++ hay Python, lộ trình ôn thi HSG và chuyên Tin, kinh nghiệm phòng thi, quy hoạch động, tìm kiếm nhị phân, lỗi code thường gặp và gợi ý lời giải một số bài.

43 câu hỏi trong 8 chủ đề. Bấm vào câu hỏi để xem câu trả lời.

• Định hướng & lộ trình11
• Kỳ thi & kinh nghiệm phòng thi8
• Phương pháp học2
• Tìm kiếm nhị phân2
• Quy hoạch động (QHĐ / DP)6
• C++, Python & tài liệu9
• Gợi ý lời giải bài cụ thể3
• Chủ đề khác2

Chưa có câu hỏi nào khớp từ khóa này. Thử từ khóa ngắn hơn, hoặc để lại câu hỏi ở phần bình luận cuối bài.

Định hướng & lộ trình

11 câu

Nên học ngôn ngữ nào, bắt đầu từ đâu và ôn theo thứ tự nào cho từng mục tiêu.

1Lớp 6 vừa học xong Scratch, bây giờ nên học Python hay C, C++?

Chào em, lớp 6 mà đã học xong Scratch và biết tự tìm hướng đi tiếp là rất tốt rồi đấy. Việc chọn Python hay C++ thì tùy vào mục tiêu của em nhé.

Nếu em muốn học để hiểu lập trình, làm các chương trình nhỏ, sau này tìm hiểu về AI hay dữ liệu thì Python là lựa chọn dễ bắt đầu hơn. Cú pháp gọn, gần với tiếng Anh, chuyển từ Scratch sang sẽ đỡ bị ngợp.

Còn nếu em có ý định thi học sinh giỏi Tin, thi vào lớp Chuyên Tin sau này thì nên xác định sẽ theo C++, vì đây là ngôn ngữ chạy nhanh và được dùng phổ biến nhất trong các kỳ thi lập trình.

Thầy gợi ý là em có thể học Python trước khoảng vài tháng để làm quen với biến, vòng lặp, câu lệnh điều kiện, mảng. Khi đã vững tư duy thì chuyển sang C++ sẽ rất nhanh, vì bản chất giống nhau cả, chỉ khác cách viết thôi. Còn nếu em đã chắc chắn muốn đi thi thì học thẳng C++ luôn cũng được, chỉ cần kiên nhẫn hơn một chút lúc đầu.

Quan trọng nhất không phải là ngôn ngữ nào mà là em luyện tư duy giải bài đều đặn, và song song vẫn học tốt môn Toán nhé.

2Lớp 7, đã biết chút C++ và Python, có nên tiếp tục học không? Về Tin em hơn các bạn nhưng các môn khác chỉ tạm được.

Chào em, lớp 7 mà đã biết C++ với Python lại còn có đam mê thật sự thì rất đáng quý đấy. Thầy nghĩ em nên tiếp tục học, vì đam mê ở tuổi này là lợi thế rất lớn.

Để em hình dung rõ hơn thì C++ chạy rất nhanh, là ngôn ngữ chính để thi học sinh giỏi Tin, thi vào lớp Chuyên Tin hay thi Olympic, ngoài ra còn dùng để làm game, phần mềm. Còn Python dễ viết hơn, được dùng nhiều trong AI, phân tích dữ liệu, tự động hóa, làm web.

Nếu em muốn đi theo hướng thi HSG và Chuyên Tin thì nên tập trung vào C++ trước. Học chắc phần cơ bản như vòng lặp, mảng, xâu, hàm, rồi bắt đầu học thuật toán: sắp xếp, tìm kiếm, số học (số nguyên tố, ước, bội...), sau đó đến đệ quy, quay lui. Học đến đâu thì lên VNOJ hoặc Codeforces làm bài đến đó cho quen tay.

Còn các môn khác em cũng đừng bỏ bê nhé, nhất là Toán, vì Toán tốt thì tư duy thuật toán lên rất nhanh. Với lại thi vào trường chuyên vẫn cần điểm các môn chung nữa.

3Năm nay lớp 9, muốn thi chuyên Tin vào 10 và ôn HSG tỉnh, mới bắt đầu chưa biết gì thì nên bắt đầu từ đâu, có kịp không?

Chào em, thầy nói thật là vẫn kịp, nhưng em phải bắt đầu ngay và học đều đặn mỗi ngày. Đề thi chuyên Tin và HSG tỉnh lớp 9 phần lớn tập trung vào kiến thức cơ bản đến trung bình, nên một bạn bắt đầu từ con số 0 mà kiên trì vài tháng vẫn có thể làm tốt được, đặc biệt nếu em khá Toán.

Trước hết em hỏi thầy cô ở trường xem tỉnh mình thi bằng ngôn ngữ nào (C++ hay Python) để học đúng ngay từ đầu. Nếu được chọn thì thầy khuyên C++ vì sau này vào chuyên em cũng sẽ dùng nó.

Lộ trình thầy gợi ý:

• Tháng đầu tiên, làm quen lập trình: nhập xuất, biến, câu lệnh if, vòng lặp for và while. Mỗi ngày làm 3 đến 5 bài nhỏ như tính tổng, đếm ước, kiểm tra số nguyên tố, tách chữ số.
• Tháng thứ hai: mảng, xâu, hàm. Đây là nền tảng của hầu hết bài 1, bài 2 trong đề thi.
• Tháng thứ ba trở đi: sắp xếp, mảng cộng dồn, hai con trỏ, tìm kiếm nhị phân, sàng nguyên tố, rồi đến đệ quy và quy hoạch động cơ bản. Phần này giúp em giải được các bài phân loại.
• Khoảng 1 đến 2 tháng trước kỳ thi: tìm đề HSG và đề thi chuyên Tin của tỉnh mình các năm trước, làm có bấm giờ và tập lấy điểm subtask.

Nguồn luyện bài tiếng Việt có máy chấm em có thể dùng VNOJ và LQDOJ, lọc bài dễ làm trước.

Một lưu ý quan trọng là thi vào chuyên còn tính điểm các môn chung như Toán, Văn, Anh, nên em đừng dồn hết thời gian cho Tin mà bỏ các môn kia nhé. Chia thời gian hợp lý, mỗi ngày code một ít nhưng đều đặn sẽ hiệu quả hơn học dồn.

4Thi tỉnh và thi chuyên bằng Python xong, lên cấp 3 đổi sang C++ được không?

Chào em, hoàn toàn được nhé, và đây cũng là con đường rất nhiều bạn đã đi. Cái quan trọng nhất khi thi là tư duy thuật toán, mà tư duy thì mang theo được sang ngôn ngữ nào cũng được. Em đã vững thuật toán bằng Python thì học cú pháp C++ thường chỉ mất vài tuần đến một, hai tháng là quen tay.

Thậm chí thầy còn khuyên em nên chuyển khi lên cấp 3, vì:

• C++ chạy nhanh hơn Python rất nhiều, đề cấp 3 và đề chọn đội tuyển thường có dữ liệu lớn, Python dễ bị quá thời gian dù thuật toán đúng.
• Thư viện STL của C++ (set, map, priority_queue...) rất mạnh cho thi đấu.
• Phần lớn tài liệu, lời giải và code mẫu ở mức nâng cao đều viết bằng C++.

Khi chuyển, em để ý mấy chỗ khác biệt hay gây lỗi:

• Python tự xử lý số lớn, còn C++ thì int chỉ tới khoảng 2 tỷ, vượt quá là tràn số nên phải dùng long long. Đây là lỗi số một của các bạn chuyển từ Python sang.
• Chia và chia lấy dư với số âm khác nhau: Python -7 // 2 ra -4, còn C++ -7 / 2 ra -3; tương tự -7 % 2 trong C++ ra -1 chứ không phải 1.
• C++ phải khai báo kiểu dữ liệu, chú ý chỉ số mảng và không có sẵn nhiều tiện ích như cắt list hay xử lý xâu của Python.

Cách chuyển nhanh nhất là lấy những bài em đã giải bằng Python rồi viết lại bằng C++. Vì đã biết thuật toán nên em chỉ tập trung vào cú pháp, sẽ quen rất nhanh. Nếu có thời gian, mùa hè sau khi thi chuyên là lúc lý tưởng để làm việc này.

5Đang là HSG lớp 10, chưa biết gì về lập trình, muốn học Python – nên chọn ngôn ngữ nào?

Chào em, thầy góp ý một chút về ngôn ngữ: nếu mục tiêu của em là thi HSG Tin thì thầy khuyên em nên học C++ ngay từ đầu thay vì Python. Lý do là:

• C++ chạy nhanh hơn Python rất nhiều. Đề HSG cấp 3 thường có dữ liệu lớn, cùng một thuật toán đúng nhưng viết bằng Python vẫn có thể bị quá thời gian và mất điểm.
• C++ có thư viện STL (sort, vector, set, map, priority_queue...) rất mạnh cho thi đấu.
• Phần lớn tài liệu, lời giải và đề luyện ở mức HSG trở lên đều dùng C++, sau này em lên đội tuyển cao hơn cũng không phải chuyển ngôn ngữ nữa.

Nhiều bạn nghĩ Python dễ hơn nên chọn, nhưng với người mới bắt đầu thì học C++ cũng không khó hơn bao nhiêu, quan trọng là có lộ trình đúng và được hướng dẫn từ những bài đầu tiên.

Tuy vậy em hỏi lại thầy cô đội tuyển trường mình xem kỳ thi ở tỉnh em có quy định bắt buộc ngôn ngữ nào không nhé, vì một số nơi có hướng dẫn riêng.

Lộ trình học từ con số 0 sẽ đi từ nhập xuất, vòng lặp, mảng, xâu đến thuật toán và cuối cùng là luyện đề HSG.

6Học Python để thi HSG lớp 9 thì nên để tâm đến đâu nhất? Em thấy đề nào cũng khó, em đang tập trung giải đề.

Chào em, thầy thấy vấn đề lớn nhất của em không phải là đề khó, mà là em đang giải đề khi nền chưa vững. Đề HSG là tổng hợp nhiều chuyên đề, nếu từng chuyên đề chưa chắc thì đề nào nhìn cũng thấy khó là đúng rồi.

Thầy khuyên em tạm dừng giải đề lại một chút, chuyển sang học theo chuyên đề. Với HSG lớp 9 em nên để tâm nhất mấy phần sau:

• Xử lý xâu và list, vì gần như đề nào cũng có.
• Số học: số nguyên tố, sàng nguyên tố, ước, bội, UCLN, BCNN, chữ số của một số.
• Sắp xếp, mảng cộng dồn, hai con trỏ, tìm kiếm nhị phân.
• Đệ quy, quay lui và quy hoạch động cơ bản nếu tỉnh em hay ra dạng khó.

Vì em dùng Python nên phải đặc biệt chú ý độ phức tạp. Python chạy chậm hơn C++ khá nhiều, nên những bài dữ liệu lớn mà em vẫn duyệt hai vòng for lồng nhau là rất dễ bị quá thời gian. Em cũng nên biết dùng sys.stdin để đọc dữ liệu nhanh hơn.

Khi đã học xong một chuyên đề thì mới quay lại đề thi, lúc đó em sẽ thấy nhiều bài đọc là nhận ra dạng ngay. Và nhớ là bài khó không làm được trọn vẹn thì vẫn cố viết cách đơn giản để ăn điểm các test nhỏ, đi thi là góp điểm từng chút em ạ.

7Lớp 11 sắp thi HSG tỉnh, xin lộ trình ôn tập kiến thức (từ đầu cũng được) và nguồn học.

Chào em, thầy gửi em một lộ trình đi từ đầu, em tự đối chiếu xem mình đang ở đâu rồi bắt đầu từ giai đoạn đó nhé.

Giai đoạn 1, nền tảng C++: nhập xuất, rẽ nhánh, vòng lặp, mảng, xâu, hàm. Phần này phải làm thật nhiều bài đến mức code không cần nghĩ về cú pháp nữa. Song song làm quen luôn với STL như vector, sort, pair.

Giai đoạn 2, thuật toán cơ bản: độ phức tạp, số học (nguyên tố, sàng, ước, UCLN, modulo, lũy thừa nhanh), sắp xếp, mảng cộng dồn, mảng hiệu, hai con trỏ, tìm kiếm nhị phân và chặt nhị phân theo đáp án. Đây là phần chiếm rất nhiều điểm trong đề tỉnh.

Giai đoạn 3, tư duy giải bài: đệ quy, quay lui, tham lam, rồi đến quy hoạch động (cái túi, dãy con tăng dài nhất, xâu con chung, QHĐ trên lưới). Quy hoạch động là phần hay quyết định giải nên em dành nhiều thời gian cho nó.

Giai đoạn 4, nâng cao: cấu trúc dữ liệu (stack, queue, deque, set, map, priority_queue), đồ thị cơ bản (DFS, BFS, Dijkstra, DSU), có thời gian thì thêm BIT, Segment Tree. Tùy đề tỉnh em khó hay dễ mà đầu tư phần này nhiều hay ít.

Giai đoạn 5, luyện đề: làm đề HSG tỉnh mình và các tỉnh khác những năm gần đây, bấm giờ như thi thật, tập chiến thuật lấy điểm subtask. Đề của tỉnh mình các năm trước là quan trọng nhất vì nó cho em biết họ hay ra dạng gì.

Về nguồn học, em có thể tham khảo:

• VNOI Wiki: có bài viết lý thuyết tiếng Việt gần như đủ các chuyên đề.
• VNOJ và LQDOJ: kho bài tập tiếng Việt, có cả đề HSG các tỉnh.
• CSES Problem Set: bộ bài sắp xếp theo chuyên đề rất chuẩn, làm hết phần cơ bản là nền rất chắc.
• Codeforces: luyện thêm và thi contest để quen áp lực thời gian.
• Sách Giải thuật và lập trình của thầy Lê Minh Hoàng: kinh điển, đọc để hiểu sâu bản chất.

Một lưu ý nhỏ là em đừng học lý thuyết dồn dập rồi mới làm bài. Học đến chuyên đề nào thì làm ngay 10-20 bài chuyên đề đó, tự nghĩ trước rồi mới xem lời giải.

8K11 đỗ lớp Chuyên Tin, đã nắm chắc C++ cơ bản, muốn thi và có giải Duyên hải Bắc Bộ (DHBB) lớp 10 thì phải học chắc những gì?

Chào em, chúc mừng em đã đỗ Chuyên Tin nhé! Đã chắc C++ cơ bản là một nền tảng tốt rồi. Với mục tiêu có giải DHBB lớp 10, em nên học chắc lần lượt các mảng sau:

1. Nền tảng thuật toán: độ phức tạp (để biết thuật nào chạy kịp), sắp xếp, tìm kiếm nhị phân (cả chặt nhị phân theo đáp án), hai con trỏ, mảng cộng dồn, mảng hiệu.
2. STL thành thạo: vector, pair, set/multiset, map, stack, queue, deque, priority_queue. Dùng nhuần nhuyễn sẽ tiết kiệm rất nhiều thời gian code trong phòng thi.
3. Số học: sàng nguyên tố, phân tích thừa số, GCD/LCM, đồng dư – modulo, lũy thừa nhanh, nghịch đảo modulo, tổ hợp cơ bản.
4. Quay lui, đệ quy, tham lam: đây là các dạng hay có trong subtask, giúp em gom điểm.
5. Quy hoạch động: cái túi, dãy con tăng dài nhất, xâu con chung dài nhất, QHĐ trên lưới, QHĐ đoạn cơ bản. Đây là phần quyết định giải nên cần luyện nhiều nhất.
6. Đồ thị cơ bản: DFS, BFS, thành phần liên thông, Dijkstra, DSU, cây khung nhỏ nhất.
7. Nâng cao một chút để lấy giải cao: Fenwick Tree (BIT), Segment Tree cơ bản, Hash xâu, stack đơn điệu.

Cách luyện: học lý thuyết xong phải làm bài ngay trên VNOJ, Codeforces; làm lại đề DHBB các năm trước và bấm giờ như thi thật. Quan trọng là tập chiến thuật lấy điểm subtask, không cố ăn trọn 1 bài mà bỏ cả đề.

9Hiện tại lớp 10 Tin, mục tiêu là đội tuyển HSG Quốc gia – nên có lộ trình ôn như thế nào?

Chào em, vào 10 Tin mà đã xác định mục tiêu đội tuyển QG từ sớm là rất tốt, vì đây là con đường dài, cần kiên trì ít nhất 1,5 đến 2 năm. Thầy gợi ý lộ trình chia theo giai đoạn như sau, em điều chỉnh tùy nền hiện tại nhé:

Giai đoạn 1, học kỳ 1 lớp 10 (nền móng): cài đặt C++ và STL thật thành thạo, độ phức tạp, sắp xếp, cộng dồn, hai con trỏ, chặt nhị phân, tham lam, số học cơ bản (sàng, modulo, lũy thừa nhanh, nghịch đảo, tổ hợp), quay lui và QHĐ kinh điển. Mục tiêu là code nhanh, ít bug, đọc đề là biết độ phức tạp cần đạt.

Giai đoạn 2, học kỳ 2 lớp 10 (cấu trúc dữ liệu và đồ thị): BIT, Segment Tree (kể cả lazy propagation), sparse table, stack/deque đơn điệu, DSU, BFS, DFS, Dijkstra, cây khung, sắp xếp topo, LCA, hash xâu, KMP hoặc Z-function. Đây cũng là lúc hợp để thi DHBB hoặc trại hè như một bài kiểm tra thực lực.

Giai đoạn 3, lớp 11 (nâng cao): QHĐ bitmask, QHĐ chữ số, QHĐ trên cây, các kỹ thuật tối ưu QHĐ; Segment Tree nâng cao, chia căn, các kỹ thuật trên cây; luồng, ghép cặp cơ bản; hình học tính toán cơ bản; số học và tổ hợp nâng cao. Song song là luyện đề HSG cấp tỉnh/thành phố và các đề VOI những năm trước.

Về cách luyện, quan trọng không kém kiến thức:

• Thi contest đều đặn trên Codeforces, AtCoder và VNOJ để quen áp lực thời gian.
• Sau mỗi contest phải upsolve, tức là làm lại những bài chưa giải được. Phần lớn sự tiến bộ nằm ở bước này.
• Luyện bài hơi vượt sức một chút so với trình độ hiện tại, đừng chỉ làm bài dễ cho sướng.
• Tập chiến thuật lấy điểm subtask, vì đề chọn đội tuyển và VOI đều chấm theo subtask.
• Ghi sổ những bài hay và những lỗi hay mắc, trước kỳ thi đọc lại.

Tài liệu để đi theo thì em có thể dùng VNOI Wiki (các bài được đánh dấu độ khó theo sao, khá sát với mức HSGQG) và VNOI Roadmap. Thêm USACO Guide, CSES và cuốn Giải thuật và lập trình của thầy Lê Minh Hoàng.

Một lưu ý cuối là em vẫn cần học ổn các môn khác và ngủ nghỉ đầy đủ. Đường dài thì giữ sức và giữ được hứng thú mới là quan trọng nhất.

10Lớp 10 (2k11), mới học từ hè lớp 9, đến tầm QHĐ cơ bản và BFS, DFS. Aim năm 11/12 thi thành phố và HSGQG thì các dạng bài thường gặp ở 2 kỳ thi đó là gì?

Chào em, mới học từ hè lớp 9 mà đã đến QHĐ và BFS, DFS là tiến độ khá tốt rồi đấy. Còn gần 2 năm nữa nên em hoàn toàn kịp nếu đi đúng hướng.

Đề thi thành phố thường có các bài đi từ dễ đến khó và xoay quanh

• Số học: sàng nguyên tố, ước, UCLN, modulo, lũy thừa nhanh, tổ hợp.
• Kỹ thuật trên mảng: sắp xếp, cộng dồn, hai con trỏ, chặt nhị phân, tham lam, stack đơn điệu.
• QHĐ: từ dạng kinh điển đến biến thể, gần như năm nào cũng có.
• Đồ thị: BFS, DFS, Dijkstra, DSU, cây khung.
• Cấu trúc dữ liệu: BIT, Segment Tree cho bài phân loại.

HSGQG (VOI) thì cao hơn một bậc

Ít bài "nhìn là biết dạng" hơn và đòi hỏi kết hợp nhiều kỹ thuật. Những mảng hay gặp:

• QHĐ nâng cao: QHĐ bitmask, QHĐ trên cây, QHĐ chữ số, và các kỹ thuật tối ưu QHĐ.
• Cấu trúc dữ liệu: Segment Tree với lazy propagation, kết hợp với sắp xếp, xử lý offline, chia căn.
• Đồ thị và cây: LCA, binary lifting, đường đi ngắn nhất có biến thể, thành phần liên thông mạnh, cầu khớp.
• Xâu: hash, KMP, Z-function, trie.
• Toán và tổ hợp: đếm bằng modulo, bao hàm loại trừ.
• Các bài ad-hoc, tham lam cần nhận xét, nơi tư duy quan trọng hơn thuộc thuật toán.

Tất nhiên đề mỗi năm mỗi khác nên em đừng học tủ theo dạng, mà nên phủ rộng chuyên đề và luyện tư duy. Cả hai kỳ thi đều chấm theo subtask, nên kỹ năng lấy điểm từng phần cũng quan trọng không kém.

Với nền hiện tại, bước tiếp theo hợp lý cho em là: củng cố QHĐ với nhiều biến thể, học tiếp Dijkstra, DSU, cây khung, rồi đến BIT, Segment Tree. Song song thi contest đều trên Codeforces, VNOJ và upsolve sau mỗi lần. Em có thể đi theo VNOI Roadmap, trong đó các chủ đề được đánh dấu độ khó khá sát với mức HSGQG.

11Con lớp 7 trường công thích code Python, năm nay chưa được chọn đi thi. Với sự bùng nổ AI thì năm nay dạng đề và thể thức thi vẫn như mọi năm hay sẽ đổi khác?Phụ huynh

Chào anh/chị, đầu tiên thầy rất quý việc anh/chị đồng hành ôn bài cùng con như vậy, ít phụ huynh làm được lắm.

Về câu hỏi của anh/chị, theo những gì thầy biết thì AI chưa làm thay đổi thể thức thi HSG Tin. Thí sinh vẫn làm bài trên máy tính trong phòng thi không có internet, viết chương trình giải các bài toán và được chấm tự động bằng bộ test, nên AI không ảnh hưởng trực tiếp đến việc thi. Tuy vậy mỗi tỉnh, mỗi năm Sở có thể điều chỉnh cấu trúc đề nên anh/chị vẫn nên theo dõi thông báo chính thức của Sở và hỏi thêm cô giáo đội tuyển nhé.

Xu hướng thầy thấy những năm gần đây là đề ngày càng chú trọng tư duy thuật toán hơn là chỉ biết cú pháp, thường chia nhiều mức điểm (subtask), bài khó đòi hỏi chương trình chạy đủ nhanh với dữ liệu lớn. Vì con dùng Python, vốn chạy chậm hơn C++, nên càng cần chú ý đến độ phức tạp thuật toán.

Còn chuyện năm nay con chưa được đi thi, thầy nghĩ đây lại là cơ hội tốt. Con có trọn một năm để xây nền vững, sang lớp 8 đi thi sẽ có lợi thế rất lớn so với các bạn mới bắt đầu. Sau 28 đề, anh/chị có thể cho con học thêm theo chuyên đề như số học, xử lý xâu, sắp xếp, mảng cộng dồn, tìm kiếm nhị phân, rồi dần đến quy hoạch động. Học theo chuyên đề sẽ giúp con nhận dạng bài tốt hơn là chỉ giải đề.

Về AI, nếu con có dùng thì anh/chị nên định hướng con dùng nó như một người gợi ý khi bí, hoặc để giải thích lỗi sai, chứ đừng để con xin code. Vì vào phòng thi thì chỉ có con tự nghĩ thôi.

Kỳ thi & kinh nghiệm phòng thi

8 câu

Môi trường chấm, dạng đề, điểm giải và chiến thuật làm bài.

12Ai đã thi HSG Tin cấp 3 rồi cho em xin kinh nghiệm khi làm bài trong phòng thi.

Chào em, thầy chia sẻ mấy kinh nghiệm làm bài mà thầy thấy các bạn hay mất điểm oan nhất nhé:

Trước giờ thi

• Hỏi kỹ thầy cô về cách nộp bài, quy định đặt tên file, có đọc ghi file hay không, trình biên dịch và IDE được cài.
• Vào phòng thi thì viết thử một chương trình nhỏ, biên dịch và chạy thử để chắc máy hoạt động bình thường.

Khi mới nhận đề

• Dành 10 đến 15 phút đầu đọc hết tất cả các bài, đọc kỹ giới hạn và phần chia subtask. Bài 4 có khi có subtask còn dễ hơn cả bài 2.
• Xếp thứ tự làm bài: chắc ăn trước, khó sau.

Trong lúc làm

• Bài nào chưa nghĩ ra lời giải full thì viết ngay cách duyệt trâu để lấy điểm subtask nhỏ, rồi mới tối ưu. Đừng ngồi nghĩ lời giải hoàn hảo rồi cuối giờ trắng tay.
• Đặt giới hạn thời gian cho mỗi bài, quá giờ mà vẫn bí thì chuyển bài, lát quay lại.
• Giữ lại code trâu, dùng nó để so kết quả với code tối ưu trên vài test nhỏ tự tạo.
• Luôn kiểm tra tràn số, chỗ nào có thể vượt 2 tỷ thì dùng long long.
• Tự thử các trường hợp đặc biệt như n = 1, dữ liệu to nhất, tất cả phần tử bằng nhau, số âm.

15 đến 20 phút cuối

Không sửa lớn nữa, chỉ kiểm tra lại tên file, tên file input output, đã bỏ các dòng in debug chưa, và đã lưu đúng chỗ chưa. Rất nhiều bạn mất cả bài chỉ vì sai tên file hoặc quên bỏ comment dòng freopen (khi đề yêu cầu đọc ghi file).

Một điều cuối là giữ tâm lý bình tĩnh. Gặp bài khó thì nhớ là nó cũng khó với mọi người, cứ gom điểm từng phần là được.

Trước khi thi em nên làm thử đề các năm trước có bấm giờ, tập luôn mấy thói quen trên cho thành phản xạ.

13Đi thi HSG tỉnh dùng Themis phiên bản C++ bao nhiêu? Có dùng được stoi, to_string không?

Chào em, Themis chỉ là phần mềm chấm bài thôi, còn phiên bản C++ là do trình biên dịch (thường là g++ của MinGW) được cài trên máy chấm quyết định. Mỗi tỉnh, mỗi năm cài có thể khác nhau nên không có một con số cố định đâu em. Thường thì ban tổ chức sẽ ghi rõ môi trường chấm trong thông báo hoặc ngay trên đề, em để ý xem nhé, hoặc hỏi thầy cô đội tuyển trường mình vì các thầy cô thường nắm được.

Còn stoi với to_string là hàm của chuẩn C++11 trở lên. Hiện nay đa số các tỉnh dùng trình biên dịch đủ mới nên dùng thoải mái. Tuy nhiên một số bản MinGW cũ có lỗi không nhận hai hàm này dù có bật C++11, nên để chắc ăn em có thể:

• Lúc vào phòng thi, viết thử một đoạn code nhỏ có stoi, to_string rồi biên dịch xem có lỗi không.
• Thuộc sẵn cách thay thế: dùng stringstream, hoặc tự viết hàm chuyển số sang xâu và xâu sang số, chỉ mất vài dòng là xong.

Tự viết được hai hàm đó thì em không bao giờ lo bị động trong phòng thi.

14Thi HSG THPT hay HSGQG thì có nên dùng namespace __gnu_pbds không? Thấy cũng xài ổn.

Chào em, dùng được em nhé, nhưng có vài điều em cần nắm để không bị bất ngờ trong phòng thi.

pbds là thư viện mở rộng riêng của GCC (g++), không phải thư viện chuẩn C++. Phần lớn máy chấm HSG ở mình dùng g++ (MinGW) nên thường chạy được, nhưng nếu máy dùng trình biên dịch khác hoặc bản cài thiếu thì sẽ lỗi biên dịch và mất trắng điểm bài đó. Vì vậy vào phòng thi em nên biên dịch thử một đoạn nhỏ có #include <ext/pb_ds/assoc_container.hpp> và <ext/pb_ds/tree_policy.hpp> trước cho chắc.

Về ưu điểm thì ordered_set (tree với tree_order_statistics_node_update) rất tiện cho các bài cần tìm phần tử thứ k hoặc đếm số phần tử nhỏ hơn x, code ngắn hơn hẳn. Còn gp_hash_table thường nhanh hơn unordered_map.

Nhược điểm là hằng số khá lớn và tốn bộ nhớ, với dữ liệu lớn có khi chậm hơn cách truyền thống. Ngoài ra mẹo dùng less_equal để làm multiset hay bị lỗi khi erase và find, em nên thay bằng cách lưu pair (giá trị, chỉ số) cho an toàn.

Lời khuyên của thầy là em cứ dùng khi nó giúp code nhanh và gọn, nhưng bắt buộc phải biết cách thay thế bằng BIT kết hợp nén số hoặc Segment Tree. Hầu hết các bài dùng ordered_set đều làm được bằng BIT, mà BIT chạy nhanh hơn và không phụ thuộc trình biên dịch. Đừng để pbds là cách duy nhất mình biết.

15Thi HSG tỉnh thì nên học cái gì, họ hay ra những gì?

Chào em, đề HSG tỉnh mỗi nơi mỗi khác một chút, nhưng nhìn chung thường có các bài đi từ dễ đến khó và xoay quanh mấy mảng này, em ưu tiên học theo thứ tự nhé:

Đầu tiên là số học và xử lý xâu. Gần như đề nào cũng có, thường là bài 1, bài 2: kiểm tra số nguyên tố, sàng nguyên tố, ước, bội, UCLN, tách chữ số, đếm ký tự, đảo xâu, kiểm tra xâu đối xứng.

Tiếp theo là các kỹ thuật trên mảng: sắp xếp, mảng cộng dồn, hai con trỏ, tìm kiếm nhị phân. Mấy cái này giúp em từ lời giải duyệt trâu O(n²) xuống O(n log n) hoặc O(n), là chỗ phân loại điểm rất nhiều.

Sau đó là đệ quy, quay lui, tham lam và quy hoạch động cơ bản (cái túi, dãy con tăng dài nhất, QHĐ trên lưới). QHĐ thường là bài 3, bài 4 quyết định giải cao.

Nếu em thi cấp THPT hoặc tỉnh em ra đề khó thì học thêm đồ thị cơ bản (BFS, DFS, Dijkstra) và các cấu trúc dữ liệu như stack, queue, set, map.

Quan trọng nhất là em tìm đề HSG của chính tỉnh mình 3 đến 5 năm gần đây để xem họ hay ra dạng gì, vì mỗi tỉnh thường có "gu" ra đề khá ổn định. Làm đề thì bấm giờ như thi thật, và bài khó không làm trọn được thì cứ viết cách đơn giản để lấy điểm test nhỏ.

16HSG 12 TP.HCM tầm bao nhiêu điểm thì được giải Ba? Kiến thức thường rơi vào những dạng nào?

Chào em, về điểm đạt giải Ba thì thầy nói thật là không có con số cố định đâu em. Ngưỡng điểm phụ thuộc vào độ khó của đề và phổ điểm của thí sinh từng năm, năm đề khó thì ngưỡng thấp, năm đề dễ thì ngưỡng cao. Để có con số tham khảo sát nhất, em nên hỏi thầy cô đội tuyển hoặc các anh chị khóa trên đã thi, họ sẽ nắm kết quả và phổ điểm các năm trước rõ nhất.

Thay vì tập trung vào con số, thầy khuyên em đặt mục tiêu theo bài: chắc chắn ăn trọn các bài đầu và gom được càng nhiều điểm subtask ở bài khó càng tốt. Thường thì làm chắc được như vậy là đã có cơ hội giải rồi.

Về kiến thức, đề thường xoay quanh mấy mảng này:

• Thuật toán cơ bản: sắp xếp, mảng cộng dồn, hai con trỏ, chặt nhị phân, tham lam.
• Số học: sàng nguyên tố, ước, UCLN, modulo, lũy thừa nhanh, tổ hợp.
• Xử lý xâu, có thể có hash.
• Quy hoạch động: gần như năm nào cũng có, từ dạng kinh điển đến biến thể.
• Đồ thị: BFS, DFS, Dijkstra, DSU.
• Cấu trúc dữ liệu: stack, deque, BIT, Segment Tree cho các bài phân loại.

Cách ôn hiệu quả nhất là em tìm đề HSG 12 TP.HCM các năm trước làm thử có bấm giờ, chấm bằng test, là biết ngay mình đang ở đâu và cần bổ sung phần nào. Trên VNOJ và LQDOJ có khá nhiều đề HSG các tỉnh để em luyện thêm.

17Sắp tới TP.HCM có kỳ thi đầu vào đội tuyển HSGQG, mình trường thường thì đề vòng 1 có khó không? Xoay quanh những kiến thức gì?

Chào em, nói thật là đề vòng này khá khó so với mặt bằng chung, vì em sẽ cạnh tranh với các bạn trường chuyên đã được luyện bài bản từ lớp 10. Nhưng khó không có nghĩa là không có cơ hội đâu, vẫn có nhiều bạn trường thường vào được nếu chuẩn bị đúng hướng.

Đề thường có độ khó tăng dần, bài đầu kiểm tra nền tảng, các bài sau mới phân loại. Kiến thức hay xoay quanh mấy mảng này:

• Thuật toán cơ bản nhưng phải vững: sắp xếp, mảng cộng dồn, hai con trỏ, chặt nhị phân, tham lam.
• Số học: sàng nguyên tố, modulo, lũy thừa nhanh, tổ hợp.
• Quy hoạch động: gần như chắc chắn có, từ các dạng kinh điển đến QHĐ đoạn, QHĐ bitmask.
• Đồ thị: BFS, DFS, Dijkstra, DSU, cây khung, xử lý trên cây.
• Cấu trúc dữ liệu: BIT, Segment Tree, stack đơn điệu, hash xâu.

Với đề kiểu này, chiến thuật quan trọng nhất là lấy điểm subtask. Không phải ai cũng giải trọn được bài khó, nên người nào gom được nhiều điểm test nhỏ hơn thì thường là người đi tiếp. Em chắc ăn bài dễ trước, bài khó thì viết cách trâu để lấy điểm rồi mới tối ưu dần.

Em nên tìm đề các năm trước của kỳ thi này để làm thử có bấm giờ, là biết ngay mình đang ở đâu và cần bổ sung phần nào. Trên VNOJ và LQDOJ có khá nhiều đề thi HSG của TP.HCM và các tỉnh để em luyện.

18Kỳ thi chọn ĐTQG TP.HCM thi 2 ngày, thường ngày 1 dễ hơn ngày 2 hay sao?

Chào em, thầy nói thật là không có quy luật cố định ngày 1 dễ hơn ngày 2 đâu em. Với các kỳ thi thi 2 ngày, ban ra đề thường cố gắng cân bằng để mỗi ngày đều có bài dễ, bài trung bình và bài phân loại, nhưng thực tế có năm ngày 1 khó hơn, có năm ngày 2 khó hơn, cũng có khi cảm nhận mỗi bạn mỗi khác tùy dạng bài mình mạnh hay yếu.

Vì vậy em đừng chuẩn bị tâm lý theo kiểu ngày nào dễ ngày nào khó, mà nên coi mỗi ngày là một bài thi độc lập và áp dụng cùng một chiến thuật:

• Đọc hết đề trước, xác định bài nào chắc ăn thì làm trước.
• Bài khó thì viết cách đơn giản để lấy điểm subtask nhỏ trước, rồi mới tối ưu dần.
• Phân bổ thời gian hợp lý, đừng sa lầy một bài quá lâu.

Một điều quan trọng nữa là các kỳ thi hai ngày thường xét tổng điểm, nên nếu ngày 1 làm không tốt thì em cũng đừng nản. Rất nhiều bạn lật ngược tình thế ở ngày 2 vì đề khó với mình thì cũng khó với mọi người. Giữ tâm lý ổn định qua cả hai ngày quan trọng không kém kiến thức đâu em.

Em cũng nên tìm đề các năm trước của kỳ thi này, làm thử cả hai ngày có bấm giờ để quen nhịp.

19Lần đầu thi HSG Tin, thầy cô trên chuyên có tổ chức đề khảo sát khoảng 100k/1 học sinh, đề sát đề thật. Có nên thi không, vì bình thường em toàn làm contest free?

Chào em, câu hỏi này rất thực tế. Thầy nói thẳng là không bắt buộc phải thi đâu em, nhưng nếu điều kiện cho phép thì thi 1, 2 lần cũng có cái lợi riêng mà contest free không có.

Cái lợi lớn nhất của đề khảo sát là:

• Đề do thầy cô chuyên ra nên sát cấu trúc, độ khó và cách chia subtask của đề tỉnh mình hơn contest trên mạng.
• Em biết mình đang đứng ở đâu so với các bạn sẽ thi cùng mình, cái này contest free không cho được.
• Lần đầu đi thi thì được làm quen với không khí phòng thi, cách nộp bài, đặt tên file, đọc ghi file, những lỗi rất hay mất điểm oan.

Còn nếu 100k là khoản khó với em thì hoàn toàn có thể thay bằng cách miễn phí:

• Tìm đề HSG tỉnh mình và các tỉnh lân cận những năm gần đây, nhiều đề có sẵn trên VNOJ và LQDOJ kèm máy chấm.
• Tự thi thử ở nhà như thi thật: bấm đúng giờ, không xem lời giải, đọc ghi file đúng tên, làm xong mới chấm.

Nếu em quyết định thi thì thầy gợi ý chọn 1 đến 2 đợt gần kỳ thi thật là đủ, không cần thi hết. Và để không phí tiền thì sau khi thi nhớ xin lại đề, test và lời giải nếu có, rồi làm lại những bài chưa được full. Giá trị thật nằm ở bước làm lại này chứ không phải ở con số điểm.

Phương pháp học

2 câu

20Em học nhiều hiểu ít, tư duy không bao giờ khá lên được. Một số bài nhìn hiểu mà không biết code, một số bài đọc không hiểu gì, code xong ngày hôm sau không hiểu gì hết.

Chào em, tình trạng của em rất nhiều bạn mới học lập trình gặp phải, không phải do em kém đâu mà chủ yếu là do cách học chưa đúng thôi. Thầy góp ý mấy điều thế này nhé.

Thứ nhất, học nhiều mà hiểu ít thường là do học quá nhanh, xem lời giải nhiều nhưng tự làm ít. Em thử giảm số bài lại, mỗi ngày chỉ cần 2-3 bài nhưng phải tự làm ra, kể cả mất cả tiếng cũng được. Tự nghĩ ra một bài có giá trị hơn xem lời giải mười bài.

Thứ hai, bài nhìn hiểu mà không biết code là do em đang nhảy thẳng từ ý tưởng sang code. Trước khi gõ, em hãy viết ra giấy từng bước cần làm bằng lời của mình, kiểu như bước 1 nhập gì, bước 2 duyệt cái gì, bước 3 kiểm tra điều kiện gì. Viết được các bước rồi thì chuyển sang code sẽ dễ hơn rất nhiều.

Thứ ba, bài đọc không hiểu thì em lấy ví dụ trong đề ra tự tính tay trên giấy xem tại sao lại ra kết quả đó. Làm tay được ví dụ thì gần như là hiểu đề rồi.

Thứ tư, code xong hôm sau không hiểu gì là chuyện bình thường nếu em code xong rồi bỏ đó. Em nên đặt tên biến cho rõ nghĩa, ghi chú vài dòng giải thích ý tưởng ngay trong code, và sau 2-3 ngày thử xóa đi tự code lại bài đó mà không nhìn bài cũ. Code lại được thì mới là hiểu thật.

Tư duy lập trình không lên trong một sớm một chiều đâu em, nhưng học đúng cách thì sau vài tháng em sẽ thấy khác hẳn.

21Có ai pass lại khóa học (trả phí) của người khác không? – Chuyện bản quyền khóa học

Chào em, thầy hiểu là khóa học trả phí đôi khi khá đắt với học sinh, nhưng thầy cũng muốn nói thật với em một chút về chuyện pass lại khóa học nhé.

Phần lớn các khóa học online đều chỉ cấp quyền học cho người đã đăng ký, và việc chia sẻ tài khoản, bán lại hay quay video phát tán lại là vi phạm bản quyền của người dạy. Đằng sau mỗi khóa học là rất nhiều thời gian biên soạn bài giảng, đề bài, test chấm, nên khi khóa bị phát tán thì người dạy mất đi nguồn thu nhập để tiếp tục làm ra những nội dung tốt cho chính các em.

Ngoài ra cũng có rủi ro cho em nữa: tài khoản dùng chung có thể bị khóa giữa chừng, còn những người rao bán lại khóa học trên mạng thì không ít trường hợp là lừa đảo, chuyển tiền xong là mất liên lạc.

Nếu em thực sự muốn học khóa đó, em thử nhắn trực tiếp cho bên tổ chức hỏi xem có ưu đãi, học bổng hay hình thức trả góp không, nhiều nơi rất sẵn lòng hỗ trợ học sinh có hoàn cảnh. Còn nếu chưa có điều kiện thì vẫn có rất nhiều nguồn miễn phí hợp pháp và chất lượng như VNOI Wiki, VNOJ, CSES, Codeforces EDU, học nghiêm túc với mấy nguồn này cũng đủ để đi rất xa.

Tìm kiếm nhị phân

2 câu

22Em mãi không giác ngộ được tìm kiếm nhị phân, tìm kiếm nhị phân kết quả, chỉ làm được mấy bài rất cơ bản như kiểm tra phần tử có trong mảng hay không.

Chào em, chặt nhị phân là phần rất nhiều bạn bị kẹt, nhưng chỉ cần hiểu đúng một ý là mọi thứ sẽ sáng ra ngay.

Ý quan trọng nhất là thế này: em đừng nghĩ chặt nhị phân là "tìm một số trong mảng", mà hãy nghĩ là "tìm chỗ chuyển từ sai sang đúng". Tức là em có một hàm check(x) trả về đúng hoặc sai, và khi x tăng dần thì kết quả có dạng sai sai sai ... đúng đúng đúng (hoặc ngược lại đúng ... đúng sai ... sai). Chặt nhị phân chỉ làm đúng một việc là tìm ra chỗ chuyển đó thôi.

Khi gặp một bài, em tự trả lời 3 câu hỏi:

• Đáp án nằm trong khoảng nào? (giá trị nhỏ nhất và lớn nhất có thể)
• Nếu ai đó đưa cho em một đáp án x, em có kiểm tra được x có thỏa mãn không? Đó chính là hàm check.
• Nếu x thỏa mãn thì x+1 (hoặc x-1) có chắc chắn cũng thỏa mãn không? Nếu có thì bài đó chặt nhị phân được.

Ví dụ bài: có n khúc gỗ, cần cắt ra ít nhất k đoạn bằng nhau, hỏi đoạn dài nhất được bao nhiêu. Tìm trực tiếp thì khó, nhưng nếu thử "cắt mỗi đoạn dài x thì được bao nhiêu đoạn" thì chỉ cần cộng a[i]/x lại là xong. x càng nhỏ thì càng cắt được nhiều đoạn, nên có tính đơn điệu, và em chặt nhị phân x để tìm x lớn nhất mà vẫn đủ k đoạn.

Một mẹo nữa là em nên chọn một mẫu code cố định rồi dùng mãi, ví dụ:

// Tìm x LỚN NHẤT thỏa mãn check(x)
long long l = lo, r = hi, ans = -1;
while (l <= r) {
    long long mid = (l + r) / 2;
    if (check(mid)) { ans = mid; l = mid + 1; }
    else r = mid - 1;
}

// Dạng tìm x NHỎ NHẤT thỏa mãn thì đảo lại:
//   if (check(mid)) { ans = mid; r = mid - 1; } else l = mid + 1;

Cách này không bao giờ bị lặp vô hạn, em chỉ cần tập trung vào viết hàm check thôi.

Lộ trình luyện thì em làm lại lower_bound, upper_bound bằng tay trước, sau đó làm các bài kinh điển như cắt gỗ, chia dãy thành k đoạn sao cho tổng lớn nhất là nhỏ nhất, xếp bò vào chuồng. Làm tầm 10-15 bài theo đúng 3 câu hỏi trên là em sẽ thấy "à ra là vậy".

23Cho em xin tài liệu free về tìm kiếm nhị phân.

Chào em, thầy gửi em mấy nguồn miễn phí mà thầy thấy chất lượng nhất về tìm kiếm nhị phân nhé:

• VNOI Wiki: bài viết tiếng Việt, giải thích từ cơ bản đến chặt nhị phân theo đáp án, em nên đọc cái này trước.
• Codeforces EDU, khóa ITMO Academy phần Binary Search: thầy khuyên nhất cái này. Có video bài giảng, bài đọc và bài tập chia thành từng step từ dễ đến khó. Tiếng Anh nhưng dễ hiểu, em bật phụ đề là theo được.
• USACO Guide, phần Binary Search: giải thích gọn, có code mẫu và danh sách bài luyện kèm lời giải.
• CP-Algorithms: viết kỹ về bản chất và các biến thể, hợp để đọc khi em đã biết cơ bản.

Về bài tập, em làm thêm hai bài chặt nhị phân kinh điển trên CSES: Factory Machines và Array Division.

Một lưu ý là em đừng đọc hết tài liệu rồi mới làm bài, mà nên đọc đến đâu làm bài đến đó. Chặt nhị phân hiểu lý thuyết thì nhanh, nhưng phải làm nhiều bài mới nhận ra được khi nào bài toán dùng được nó.

Quy hoạch động (QHĐ / DP)

6 câu

24Em học QHĐ nhưng chỉ hiểu cách code các bài cơ bản, không thực sự hiểu cách tư duy. Tài liệu trên mạng chỉ có công thức với chữa chứ không dạy tư duy...

Chào em, em nhận ra được vấn đề là mình chỉ thuộc code chứ chưa hiểu tư duy là đã tốt hơn nhiều bạn rồi đấy. Quy hoạch động thật ra có một khuôn suy nghĩ khá cố định, thầy chia sẻ để em tập nhé.

Với mỗi bài, em luôn trả lời lần lượt mấy câu hỏi sau, và viết hẳn ra giấy:

Câu 1: dp[i] (hoặc dp[i][j]) nghĩa là gì? Phải viết được thành một câu tiếng Việt rõ ràng, ví dụ "dp[i] là tổng lớn nhất khi xét i phần tử đầu và bắt buộc chọn phần tử i". Đa số các bạn bí là vì bỏ qua bước này, hoặc định nghĩa mơ hồ.

Câu 2: để đi đến trạng thái này thì bước cuối cùng có thể là gì? Đây là câu quan trọng nhất. Ví dụ bài leo cầu thang mỗi lần 1 hoặc 2 bậc, muốn đứng ở bậc i thì bước cuối chỉ có thể là từ bậc i-1 hoặc i-2 bước lên, nên dp[i] = dp[i-1] + dp[i-2]. Công thức không phải để nhớ, mà tự ra khi em liệt kê đủ các khả năng của bước cuối.

Câu 3: trường hợp cơ sở là gì, tính theo thứ tự nào, và đáp án cuối cùng nằm ở ô nào.

Nếu chưa nghĩ ra được trạng thái, em thử cách này: viết lời giải quay lui (đệ quy thử hết) trước. Sau đó nhìn xem hàm đệ quy của em đang phụ thuộc vào những tham số nào, thì chính những tham số đó là trạng thái dp. Thêm mảng lưu lại kết quả đã tính là em có QHĐ rồi. Đây là cách tự nhiên nhất để "nghĩ ra" QHĐ chứ không phải đoán mò công thức.

Về cách luyện, khi đọc lời giải em đừng chỉ xem công thức, mà hãy tự hỏi: tại sao họ định nghĩa dp như vậy, nếu bỏ bớt một chiều thì sao không được. Tốt nhất là tự viết định nghĩa dp của mình trước rồi mới đối chiếu. Hai bộ bài rất phù hợp để luyện tư duy là AtCoder Educational DP Contest (26 bài đi từ dễ đến khó, mỗi bài một dạng) và phần Dynamic Programming trên CSES. Làm hết hai bộ này theo đúng 3 câu hỏi trên là em sẽ thấy QHĐ khác hẳn.

25Ai giúp em phần quy hoạch động với ạ, em yếu phần này lắm.

Chào em, QHĐ là phần rất nhiều bạn thấy "yếu", nhưng thường không phải do khó mà do học theo kiểu nhớ công thức từng bài. Thầy gợi ý em đi lại theo cách này nhé.

Với bài nào em cũng trả lời đúng 3 câu, viết hẳn ra giấy:

1. dp[i] nghĩa là gì? Phải nói được thành một câu rõ ràng, ví dụ "dp[i] là số cách leo lên bậc thứ i".
2. Để đến được trạng thái đó thì bước cuối cùng có thể là gì? Liệt kê đủ các khả năng là ra công thức. Ví dụ leo 1 hoặc 2 bậc thì bước cuối là từ bậc i-1 hoặc i-2, nên dp[i] = dp[i-1] + dp[i-2].
3. Trường hợp cơ sở là gì và đáp án nằm ở ô nào.

Nếu bí chưa nghĩ ra dp[i] là gì, em viết thử lời giải đệ quy thử hết trước. Hàm đệ quy phụ thuộc vào tham số nào thì tham số đó chính là trạng thái, thêm mảng nhớ kết quả là thành QHĐ.

Thứ tự bài nên làm: leo cầu thang, đổi tiền, cái túi, dãy con tăng dài nhất, xâu con chung dài nhất, QHĐ trên lưới. Mỗi dạng làm 3-5 bài biến thể cho quen.

Tài liệu em có thể đọc VNOI Wiki (tiếng Việt) và luyện bộ AtCoder DP Contest, 26 bài từ dễ đến khó.

Quan trọng nhất là khi xem lời giải, đừng chép công thức mà hãy tự hỏi vì sao người ta định nghĩa dp như vậy, rồi vài hôm sau tự làm lại không nhìn.

26Ai có tài liệu DP (quy hoạch động) cơ bản cho em xin với.

Chào em, thầy gửi em mấy nguồn miễn phí về QHĐ cơ bản mà thầy thấy dễ học nhất nhé:

• VNOI Wiki, QHĐ cơ bản phần 1 và phần 2: tiếng Việt, giải thích từ khái niệm trạng thái, công thức qua các bài kinh điển. Em nên đọc cái này trước.
• USACO Guide, phần Introduction to DP: giải thích gọn, có code mẫu và bài luyện kèm lời giải.
• AtCoder Educational DP Contest: 26 bài từ dễ đến khó, mỗi bài một dạng kinh điển. Em làm tầm 10 bài đầu là đã nắm được nền.
• CSES Problem Set, phần Dynamic Programming, để luyện thêm.

Thứ tự học thầy gợi ý là bắt đầu từ leo cầu thang, đổi tiền, rồi đến cái túi, dãy con tăng dài nhất, xâu con chung dài nhất, QHĐ trên lưới. Với mỗi bài em tự hỏi dp[i] nghĩa là gì và bước cuối cùng để đến dp[i] có thể là gì, trả lời được hai câu đó là ra công thức.

27Em chưa biết gì về quy hoạch động trong Python thì nên tiếp cận, tìm nguồn tự học ở đâu?

Chào em, quy hoạch động là tư duy chung, học bằng Python hay C++ thì bản chất vẫn y như nhau, nên em cứ đọc tài liệu QHĐ chung rồi tự cài đặt bằng Python là được nhé. Thầy gợi ý lộ trình thế này:

Trước khi học QHĐ, em cần chắc đệ quy và list (kể cả list 2 chiều). Sau đó bắt đầu từ các bài rất cơ bản như dãy Fibonacci, leo cầu thang, đổi tiền, rồi đến các bài kinh điển như cái túi, dãy con tăng dài nhất, xâu con chung dài nhất.

Về nguồn tự học miễn phí:

• VNOI Wiki phần QHĐ cơ bản (phần 1, phần 2), tiếng Việt, giải thích từ khái niệm trạng thái, công thức qua ví dụ cụ thể.
• AtCoder Educational DP Contest, 26 bài từ dễ đến khó, mỗi bài một dạng, nộp được bằng Python. Em làm tầm 10 bài đầu là đã nắm được nền.
• CSES Problem Set, phần Dynamic Programming, để luyện thêm.

Mấy lưu ý riêng khi làm QHĐ bằng Python:

• Nên viết dạng vòng lặp (tính từ nhỏ đến lớn) thay vì đệ quy, vì Python giới hạn độ sâu đệ quy và chạy đệ quy khá chậm.
• Nếu muốn dùng đệ quy có nhớ thì em tìm hiểu thêm lru_cache trong functools và sys.setrecursionlimit.
• Tạo list 2 chiều phải viết dp = [[0] * m for _ in range(n)], đừng viết [[0] * m] * n vì các hàng sẽ dùng chung một list, sửa một hàng là cả bảng đổi theo. Đây là lỗi rất nhiều bạn mới học mắc phải.

Khi làm bài, em luôn tự hỏi dp[i] nghĩa là gì, và để đến được dp[i] thì bước cuối cùng có thể là gì. Trả lời được hai câu đó là ra công thức.

28Năm nay cuối cấp 2, đang học DP nhưng thấy khó quá, ai có tips gì không? Mấy dạng kiểu knapsack và nhiều bài khác em thấy hơi khó làm.

Chào em, lớp 9 mà đã học QHĐ và cái túi là đi nhanh rồi đấy, thấy khó là bình thường em ạ. Thầy chia sẻ vài mẹo, lấy luôn bài cái túi làm ví dụ nhé.

Mẹo 1: luôn viết ý nghĩa của dp thành một câu tiếng Việt trước khi code. Với cái túi: dp[i][w] là giá trị lớn nhất khi chỉ được chọn trong i món đầu tiên và tổng khối lượng không quá w.

Mẹo 2: tự hỏi "với món cuối cùng, mình có những lựa chọn nào?". Món thứ i chỉ có 2 khả năng:

• Không lấy: dp[i][w] = dp[i-1][w]
• Lấy (nếu w >= khối lượng món i): dp[i-1][w - khối lượng i] + giá trị i

Lấy cái lớn hơn là xong. Công thức không phải để học thuộc, mà tự ra khi em liệt kê đủ lựa chọn.

Mẹo 3: với ví dụ nhỏ (3 món, túi 5kg) em kẻ bảng ra giấy và điền tay từng ô. Điền xong một bảng là hiểu QHĐ hơn đọc 10 bài lời giải.

Mẹo 4: khi chuyển sang mảng 1 chiều để tiết kiệm bộ nhớ, nhiều bạn hay nhầm chiều duyệt:

• Mỗi món chỉ lấy 1 lần: duyệt w từ lớn về nhỏ.
• Mỗi món lấy bao nhiêu lần cũng được: duyệt w từ nhỏ lên lớn.

Em thử điền tay cả hai cách sẽ thấy vì sao.

Mẹo 5: nhận ra "họ hàng" của cái túi. Rất nhiều bài thực ra là cái túi đổi tên: kiểm tra có chọn được các số có tổng bằng S không, đổi tiền ít đồng xu nhất, đếm số cách đổi tiền, chia dãy thành hai phần có tổng gần bằng nhau nhất. Em làm hết mấy biến thể này là gặp bài mới sẽ nhận ra ngay.

Bài luyện thì em làm Knapsack 1 (bài D) trong bộ AtCoder DP Contest. Nên làm từ bài A đến bài D trước vì đây là các bài QHĐ nhập môn rất chuẩn.

Còn những bài em thấy khó, lần sau em đăng cụ thể một bài lên, thầy và mọi người sẽ gợi ý cách đặt dp cho em.

29Có cách phân biệt khi nào dùng top-down (hàm đệ quy riêng) hay bottom-up (các vòng for) không?

Câu hỏi hay đấy em. Về bản chất hai cách giống nhau: cùng trạng thái, cùng công thức, chỉ khác thứ tự tính. Top-down là gọi từ bài toán lớn xuống, gặp ô nào chưa tính thì đệ quy tính rồi lưu lại. Bottom-up là tự xếp thứ tự và tính từ ô nhỏ lên bằng vòng for. Đa số bài viết cách nào cũng được, nhưng có mấy dấu hiệu để chọn như sau.

Nên dùng top-down (đệ quy có nhớ) khi

• Khó xác định thứ tự tính, ví dụ QHĐ trên cây, trên đồ thị không chu trình (DAG), QHĐ chữ số. Đệ quy tự lo việc tính đúng thứ tự, mình khỏi phải nghĩ.
• Không phải trạng thái nào cũng cần đến. Top-down chỉ tính những ô thực sự được gọi tới, còn bottom-up thì tính hết cả bảng.
• Em vừa viết được lời giải quay lui. Chỉ cần thêm mảng nhớ vào hàm đệ quy là thành QHĐ, rất tự nhiên khi mới học.

Nên dùng bottom-up (vòng for) khi

• Thứ tự tính rõ ràng: dp[i] chỉ phụ thuộc dp[i-1], dp[i-2]... hay dp[i][j] phụ thuộc ô bên trên, bên trái. Cái túi, dãy con tăng, QHĐ trên lưới đều thuộc loại này.
• n lớn (cỡ 10⁵, 10⁶ trở lên). Đệ quy sâu dễ bị tràn stack, nhất là với Python. Vòng for không bị vấn đề này.
• Cần tối ưu bộ nhớ, ví dụ cái túi dùng mảng 1 chiều. Các kỹ thuật này chỉ làm được với bottom-up.
• Cần chạy nhanh hơn một chút, vì gọi hàm đệ quy tốn chi phí hơn vòng lặp.

Mẹo thực tế là khi mới nghĩ bài, cứ viết top-down cho dễ đúng. Nếu bị quá thời gian, tràn stack, hoặc cần giảm bộ nhớ thì chuyển sang bottom-up. Em nên tập viết cùng một bài theo cả hai cách, ví dụ Fibonacci, leo cầu thang, cái túi, làm vài lần là chuyển qua lại rất nhanh.

C++, Python & tài liệu

9 câu

30Em đang bắt đầu tự học C++, có nguồn tài liệu nào free mà chất lượng không?

Chào em, tự học C++ hiện giờ có rất nhiều nguồn miễn phí chất lượng, thầy gợi ý mấy nguồn này nhé:

Học lý thuyết

• W3Schools: dễ đọc nhất, mỗi bài ngắn gọn có ví dụ và chạy thử ngay trên web, hợp với người mới bắt đầu.
• LearnCpp: giải thích rất kỹ và chuẩn, học xong là hiểu bản chất chứ không chỉ biết cú pháp. Tiếng Anh nhưng viết dễ hiểu, em có thể dùng dịch trang nếu cần.
• cppreference: không phải để học từ đầu mà để tra cứu khi cần biết một hàm dùng thế nào.

Luyện bài tập (quan trọng nhất)

• VNOJ và LQDOJ: kho bài tiếng Việt, có máy chấm tự động, em lọc bài dễ làm trước.

Thầy gợi ý thứ tự học là: nhập xuất, biến và kiểu dữ liệu, câu lệnh rẽ nhánh, vòng lặp, mảng, xâu, hàm, rồi đến STL cơ bản như vector, sort. Mỗi phần học xong em làm ngay 10-20 bài tập, vì lập trình là phải gõ nhiều mới quen, đọc nhiều mà không code thì quên rất nhanh.

31Ai có một số bài C++ cơ bản từ vòng lặp for cho em xin với?

Chào em, thầy gửi em một loạt bài về vòng lặp for xếp từ dễ đến khó, em làm lần lượt nhé:

Mức 1, làm quen

1. Nhập n, in ra các số từ 1 đến n.
2. Tính tổng 1 + 2 + ... + n.
3. Tính tổng các số chẵn từ 1 đến n.
4. In bảng cửu chương của số n.
5. Đếm có bao nhiêu số chia hết cho k trong đoạn [a, b].

Mức 2, tính toán

6. Tính n! (nhớ dùng long long).
7. Tính a mũ n bằng vòng lặp, không dùng pow.
8. Tính tổng 1 + 1/2 + 1/3 + ... + 1/n (chú ý kiểu số thực).
9. In số Fibonacci thứ n.
10. Nhập n số, tìm số lớn nhất, nhỏ nhất và tổng của chúng.

Mức 3, bắt đầu có tư duy

11. Đếm số ước của n và tính tổng các ước.
12. Kiểm tra n có phải số nguyên tố không (thử cả cách duyệt đến căn n).
13. In các số nguyên tố nhỏ hơn hoặc bằng n.
14. Kiểm tra n có phải số hoàn hảo không (tổng các ước nhỏ hơn n bằng n).
15. In hình tam giác sao chiều cao n (dùng 2 vòng for lồng nhau).

Làm xong 15 bài này là em nắm khá chắc vòng lặp rồi. Muốn có máy chấm tự động thì em vào VNOJ hoặc LQDOJ, lọc các bài dễ để luyện thêm.

Mẹo nhỏ là mỗi bài em tự nghĩ và tự code trước, sai thì chạy tay từng vòng lặp trên giấy xem biến thay đổi thế nào, đừng vội xem lời giải.

32Tách từng chữ số để in số có dấu phẩy ngăn cách (ví dụ 12,345): em viết (n / 1ei) % 10 trong vòng lặp để tìm 10^i thì có đúng không?

Đoạn code bạn gửi kèm câu hỏi

Đoạn code dùng (n / 1ei) % 10 để lấy từng chữ số

Chào em, ý tưởng lấy từng chữ số bằng (n / 10^i) % 10 là đúng rồi, nhưng viết 1ei thì không được em nhé. Cách viết 1e5, 1e9 chỉ dùng được với số cụ thể viết sẵn, không thay bằng biến i được, nên 1ei sẽ báo lỗi biên dịch. Thêm nữa 1e5 là kiểu số thực, nên n / 1e5 ra số thực và không dùng phép % được.

Em cũng đừng dùng pow(10, i) vì pow trả về số thực, với số lớn dễ bị sai số. Cách gọn nhất là tính sẵn 10^(số chữ số - 1) bằng số nguyên, rồi mỗi vòng chia cho 10:

long long p = 1;
for (int j = 1; j < cnt; j++) p *= 10;   // cnt là số chữ số của n
for (; p > 0; p /= 10)
{
    --cnt;
    cout << (n / p) % 10;
    if (cnt % 3 == 0 && cnt > 0) cout << ",";
}

Em để ý thêm điều kiện cnt > 0 nhé, vì nếu không có, đến chữ số cuối thì cnt = 0, mà 0 % 3 == 0 nên sẽ in thừa một dấu phẩy ở cuối.

Ngoài ra còn một cách đơn giản hơn nữa là đổi n sang xâu bằng to_string(n) rồi duyệt từng ký tự, không cần tính lũy thừa gì cả.

33Với code trên thì có cần thêm p /= n để p thay đổi không, chứ không thì p luôn bằng nhau?

Không cần đâu em, p đã tự thay đổi rồi. Em để ý vòng for có 3 phần: for (khởi tạo; điều kiện; cập nhật). Ở đây phần khởi tạo để trống vì p đã tính sẵn ở trên, điều kiện là p > 0, còn phần cập nhật chính là p /= 10. Phần cập nhật này tự chạy sau mỗi lần lặp, giống như ++i hay --i trong vòng for bình thường của em vậy.

Em thử chạy tay với n = 1234 nhé: cnt = 4 nên p = 1000.

• Lần 1: p = 1000, in 1234 / 1000 % 10 = 1, rồi p thành 100.
• Lần 2: p = 100, in 2, p thành 10.
• Lần 3: p = 10, in 3, p thành 1.
• Lần 4: p = 1, in 4, p thành 0 thì dừng.

Kết quả in ra 1,234 đúng không em.

Còn p /= n thì không được em nhé, vì mỗi bước mình muốn lùi xuống một chữ số nên phải chia cho 10. Chia cho n thì p gần như về 0 ngay lập tức.

34Chương trình tách chữ số của em sai ở đâu mà nó không in ra gì hết (chỉ in được dòng "1" và "2" để debug)?

Code và kết quả chạy bạn gửi kèm câu hỏi

Chương trình bạn viết

Kết quả chạy: chỉ in ra dòng 1 và 2

Em sai ở chỗ khai báo p mà chưa gán giá trị ban đầu nhé. Em viết long long n = 12345, n_2, p; thì p chỉ được khai báo thôi, bên trong nó là một giá trị rác bất kỳ (có thể là 0, số âm hoặc số linh tinh). Nhân giá trị rác đó với 10 thì vẫn ra rác, và trường hợp của em là p không lớn hơn 0, nên điều kiện p > 0 sai ngay từ đầu, vòng for không chạy lần nào. Vì vậy mà chỉ thấy in ra 1 và 2.

Em sửa thành p = 1 trước vòng for là được:

long long p = 1;

Với lại em nhớ thêm điều kiện cnt > 0 khi in dấu phẩy:

if (cnt % 3 == 0 && cnt > 0) cout << ",";

Không có cái này thì với n = 12345 em sẽ in ra 12,345, (thừa dấu phẩy ở cuối).

Kinh nghiệm: biến nào dùng để cộng dồn, nhân dồn hay đếm thì luôn phải gán giá trị ban đầu, giống như em đã làm đúng với cnt = 0. Đây là lỗi rất hay gặp, có khi máy em chạy đúng mà nộp lên máy chấm lại sai.

35Trong C++, cách chuyển chữ cái thường sang chữ cái in hoa làm sao?

Chào em, có 2 cách hay dùng nhé:

Cách 1: dùng hàm toupper có sẵn (trong thư viện cctype, nếu em đã include bits/stdc++.h thì dùng luôn được):

char c = 'a';
c = toupper(c); // c thành 'A'

Lưu ý toupper trả về kiểu int, nên nếu in trực tiếp thì phải ép kiểu: cout << (char)toupper(c); không thì nó in ra số 65 chứ không phải chữ A đâu.

Cách 2: tự tính bằng mã ASCII. Chữ thường và chữ hoa cách nhau đúng 32 đơn vị ('a' là 97, 'A' là 65), nên:

if (c >= 'a' && c <= 'z') c = c - 'a' + 'A';

Cách này giúp em hiểu bản chất, và đề thi đôi khi kiểm tra đúng cái này.

Nếu muốn đổi cả xâu thì duyệt từng ký tự:

for (char &c : s) c = toupper(c);

Nhớ có dấu & để sửa trực tiếp vào xâu s nhé, thiếu dấu & là xâu không đổi gì.

Ngược lại, đổi chữ hoa sang chữ thường thì dùng tolower(c) hoặc c - 'A' + 'a'.

36Có nên thay thế hàm bình thường thành hàm inline luôn không? Lý do?

Chào em, câu trả lời ngắn là không cần em nhé. Thêm inline vào mọi hàm gần như không làm chương trình nhanh hơn, lý do như sau:

Thứ nhất, từ khóa inline chỉ là một lời gợi ý cho trình biên dịch, không phải mệnh lệnh. Trình biên dịch có quyền bỏ qua nó.

Thứ hai, khi bật tối ưu (các máy chấm thường dùng -O2), trình biên dịch tự động inline những hàm nhỏ, được gọi nhiều, dù em có viết inline hay không. Nó tính toán việc này còn tốt hơn mình tự đánh dấu.

Thứ ba, những hàm lớn hoặc hàm đệ quy thì không inline được hoàn toàn, mà nếu ép inline hàm lớn còn có thể làm code phình to, chạy chưa chắc đã nhanh hơn.

Trong C++ hiện đại, inline chủ yếu dùng cho mục đích khác: cho phép định nghĩa hàm trong file header được include ở nhiều nơi mà không bị lỗi trùng định nghĩa. Khi làm bài thi chỉ có một file thì em gần như không cần quan tâm đến nó.

Nếu bài bị quá thời gian, em nên xem lại độ phức tạp thuật toán trước, sau đó là nhập xuất nhanh (ios_base::sync_with_stdio(false); cin.tie(nullptr);), truyền vector lớn bằng tham chiếu thay vì truyền bản sao. Mấy cái đó ảnh hưởng tốc độ hơn inline rất nhiều.

37Tính ứng dụng (tác dụng) của lập trình C là gì?

Chào em, C là ngôn ngữ ra đời từ lâu nhưng đến giờ vẫn cực kỳ quan trọng, chỉ là nó nằm ở "tầng dưới" nên ít ai để ý thôi. Một số chỗ C được dùng nhiều:

• Hệ điều hành: nhân Linux được viết chủ yếu bằng C, các phần lõi của Windows, macOS cũng dùng C rất nhiều.
• Lập trình nhúng: phần mềm chạy trong máy giặt, điều hòa, ô tô, thiết bị IoT, vi điều khiển (kể cả Arduino mà nhiều bạn hay chơi) phần lớn viết bằng C hoặc C++.
• Driver, firmware: các chương trình giúp máy tính nói chuyện với phần cứng.
• Công cụ nền tảng: nhiều trình biên dịch, cơ sở dữ liệu (như SQLite), và ngay cả trình thông dịch Python phổ biến nhất (CPython) cũng được viết bằng C.

Còn về mặt học tập, C giúp em hiểu máy tính thật sự hoạt động thế nào: bộ nhớ, con trỏ, cách dữ liệu được lưu. Học C chắc thì sau này học C++, Java hay ngôn ngữ nào cũng nhanh hơn nhiều.

Một lưu ý là nếu mục tiêu của em là thi HSG Tin thì nên chuyển dần sang C++. C++ gần như bao trọn C, cộng thêm thư viện STL (vector, sort, set, map...) giúp code nhanh và gọn hơn rất nhiều trong phòng thi, nên những gì em học ở C không hề phí.

38Năm nay lên cấp 3, muốn học Python để thi HSG, có cuốn sách nào hữu ích không?

Chào em, thầy gợi ý mấy cuốn theo thứ tự từ cơ bản đến thi đấu nhé:

Học Python từ đầu

Think Python của Allen Downey. Cuốn này ngắn gọn, dạy cách tư duy lập trình chứ không chỉ cú pháp, và có bản đọc miễn phí trên mạng. Em chỉ cần đọc các chương về biến, điều kiện, vòng lặp, hàm, xâu, list, dict là đủ nền để thi.

Tư duy thuật toán

Giải thuật và lập trình của thầy Lê Minh Hoàng. Đây là cuốn kinh điển của dân thi Tin ở Việt Nam, code mẫu không phải Python nhưng phần giải thích thuật toán thì dùng cho ngôn ngữ nào cũng được.

Competitive Programmer's Handbook của Antti Laaksonen (miễn phí, tiếng Anh). Trình bày gọn và đúng trọng tâm thi đấu, đi kèm bộ bài tập CSES để luyện.

Ngoài sách, VNOI Wiki có bài viết tiếng Việt cho gần như mọi chuyên đề, còn VNOJ và LQDOJ là nơi luyện bài tiếng Việt có máy chấm, nộp được bằng Python.

Một lưu ý: đọc sách chỉ chiếm một phần nhỏ thôi, phần lớn thời gian em nên dành để code. Học đến đâu làm bài đến đó.

Và vì em mới lên cấp 3, thầy khuyên em hỏi thầy cô đội tuyển xem tỉnh mình có cho thi bằng C++ không. Đề cấp 3 thường có dữ liệu lớn, Python chạy chậm hơn C++ khá nhiều nên dễ bị quá thời gian dù thuật toán đúng. Nếu được chọn thì bắt đầu luôn bằng C++ sẽ đỡ phải chuyển về sau.

Gợi ý lời giải bài cụ thể

3 câu

Chỉ nêu ý tưởng để các bạn tự cài đặt. Các lời giải đã được đối chiếu với thuật toán vét cạn trên nhiều bộ test ngẫu nhiên.

39Bài "Đóng gói sản phẩm" – xin ý tưởng subtask 2 và subtask 3

Đề bài bạn gửi kèm câu hỏi

Câu 3 – Đóng gói sản phẩm (ảnh đề bạn gửi)

Tóm tắt: có n sản phẩm khối lượng a₁, a₂, …, a_n (1 ≤ k ≤ 3; 1 ≤ n ≤ 10⁵; 1 ≤ a_i ≤ 1000). Đóng thành các kiện, mỗi kiện có đúng k sản phẩm, khối lượng các kiện bằng nhau, mỗi sản phẩm thuộc nhiều nhất một kiện. Hỏi đóng được nhiều nhất bao nhiêu kiện. Subtask 2: k = 2. Subtask 3: k = 3, 1 ≤ a_i ≤ 3.

Chào em, bài này mấu chốt ở cả hai sub là a[i] rất nhỏ, nên em đừng làm trên mảng mà hãy đếm số lượng từng giá trị: cnt[v] là số sản phẩm có khối lượng v. Sau đó thử hết các giá trị tổng S có thể của một kiện, với mỗi S tính số kiện nhiều nhất rồi lấy max.

Sub 2 (k = 2)

S chạy từ 2 đến 2000. Với một S cố định, giá trị v chỉ ghép được với đúng một giá trị là S - v, nên các cặp không tranh nhau. Số kiện sẽ là tổng min(cnt[v], cnt[S - v]) với mọi v < S - v, cộng thêm cnt[S/2] / 2 nếu S chẵn. Độ phức tạp khoảng 2000 x 1000, chạy thoải mái.

Sub 3 (k = 3, a[i] từ 1 đến 3)

Chỉ có c1, c2, c3 là số lượng giá trị 1, 2, 3, và S chỉ từ 3 đến 9. Em liệt kê ra sẽ thấy mỗi S chỉ có tối đa 2 kiểu kiện:

S = 3: (1,1,1)
S = 4: (1,1,2)
S = 5: (1,1,3) và (1,2,2)
S = 6: (1,2,3) và (2,2,2)
S = 7: (1,3,3) và (2,2,3)
S = 8: (2,3,3)
S = 9: (3,3,3)

Với S chỉ có 1 kiểu thì tính thẳng, ví dụ S = 4 là min(c1 / 2, c2). Với S có 2 kiểu thì em duyệt x là số kiện kiểu thứ nhất (từ 0 đến n), trừ số lượng đã dùng đi, phần còn lại tính được ngay tối đa bao nhiêu kiện kiểu thứ hai. Ví dụ S = 5: chọn x kiện (1,1,3) thì còn c1 - 2x số 1, số kiện (1,2,2) là min(c1 - 2x, c2 / 2). Tổng cộng chỉ O(n) cho mỗi S.

Em thử với ví dụ 3 trong đề: c1 = 4, c2 = 4, c3 = 2, S = 5 chọn x = 1 thì được thêm 2 kiện (1,2,2), ra đúng 3.

40Bài "Chia hàng ủng hộ" – xin ý tưởng

Đề bài bạn gửi kèm câu hỏi

Câu 3 – Chia hàng ủng hộ (ảnh đề bạn gửi)

Tóm tắt: có n gói đồ dùng, gói thứ i giá v_i (n ≤ 10⁶, k ≤ 10⁶, v_i ≤ 10⁹). Chia n gói thành một hoặc nhiều kiện; kiện có nhiều hơn một gói thì giá chênh lệch giữa hai gói bất kỳ không bé hơn k. Mỗi kiện chỉ phải trả tiền gói đắt nhất. Tìm tổng tiền nhỏ nhất. Subtask: 30% n ≤ 10², 30% n ≤ 10⁴, 40% không ràng buộc thêm.

Chào em, bài này mấu chốt là nhìn lại cách tính tiền cho đúng nhé.

Xét một kiện hàng, em sắp xếp các gói trong kiện tăng dần thì nó giống một chuỗi, gói sau hơn gói trước ít nhất k (điều kiện "hai gói bất kỳ chênh nhau ít nhất k" tương đương với hai gói liền kề trong chuỗi chênh nhau ít nhất k). Mình chỉ trả tiền gói đứng đầu chuỗi, còn mọi gói khác được "miễn phí".

Vậy một gói được miễn phí khi nó đứng ngay dưới một gói khác có giá lớn hơn hoặc bằng v + k, và mỗi gói chỉ có tối đa một gói đứng ngay dưới nó. Bài toán trở thành: ghép mỗi gói muốn miễn phí với một gói "đỡ" riêng, sao cho tổng giá các gói được miễn là lớn nhất. Đáp án = tổng tất cả - tổng các gói được miễn.

Ý tưởng tham lam: sắp xếp mảng, rồi xét các gói từ đắt đến rẻ, ưu tiên miễn phí gói đắt trước. Gói có giá v miễn được nếu số gói đã được miễn trước đó còn nhỏ hơn số gói có giá lớn hơn hoặc bằng v + k (tức là vẫn còn gói đỡ trống). Số gói có giá lớn hơn hoặc bằng v + k thì dùng lower_bound hoặc hai con trỏ đều được.

Vì sao ưu tiên gói đắt đúng? Vì gói càng đắt thì càng ít gói đỡ được nó, tập gói đỡ của gói đắt nằm trọn trong tập gói đỡ của gói rẻ. Nên miễn gói đắt trước vừa được lợi nhiều hơn, vừa không làm mất cơ hội của gói rẻ.

Em thử với ví dụ 2: mảng 1 3 4 5, k = 1. Gói 5 không có gói nào >= 6 nên phải trả. Gói 4 có 1 gói >= 5, đã miễn 0 nên được miễn. Gói 3 có 2 gói >= 4, đã miễn 1 nên được miễn. Gói 1 có 3 gói >= 2, đã miễn 2 nên được miễn. Đáp án 13 - 8 = 5, đúng với đề.

Độ phức tạp O(n log n) do sắp xếp, chạy thoải mái với n = 10⁶. Em nhớ dùng long long cho tổng và nhập xuất nhanh nhé. Nếu chưa nghĩ ra lời giải full thì sub 2 em có thể làm cùng ý tưởng nhưng đếm số gói đỡ bằng vòng lặp O(n²) cũng được.

41Bài "Dividing the star" – đã dùng Ham-Sandwich nhưng chưa xử lý được ràng buộc đi qua 1 điểm mỗi nhóm

Câu hỏi gốc của bạn (tóm tắt, nguồn đề: contest.yandex.ru)cho N điểm thuộc nhóm Neutron và N điểm thuộc nhóm Giant. Tìm đường thẳng y = ax + b (luôn tồn tại) đi qua 1 điểm Neutron và 1 điểm Giant sao cho mỗi nửa mặt phẳng đều có số điểm Neutron và Giant bằng nhau. Bạn hỏi đã dùng định lý Ham-Sandwich và chia nhị phân theo góc quay nhưng chưa thực hiện được ràng buộc phải đi qua 1 điểm mỗi nhóm.

Chào em, hướng Ham-Sandwich là hướng đúng đắn đấy, nhưng bài này có lời giải đơn giản hơn nhiều vì đề không yêu cầu mỗi nửa có đúng N/2 điểm mỗi loại, chỉ cần mỗi nửa có số Neutron bằng số Giant thôi. Đây là bài toán "balanced line" kinh điển, làm được trong O(N log N) bằng sắp xếp theo góc.

Bước 1: Chọn P là điểm trái nhất (x nhỏ nhất, bằng nhau thì lấy y nhỏ nhất). P nằm trên bao lồi nên mọi điểm còn lại đều nằm trong một nửa mặt phẳng nhìn từ P. Giả sử P thuộc nhóm Neutron (nếu là Giant thì làm đối xứng).

Bước 2: Sắp xếp 2N - 1 điểm còn lại theo góc quanh P. Nhờ P là điểm trái nhất, với mỗi điểm Q thì đường thẳng PQ chia các điểm thành đúng hai phần: các điểm đứng trước Q trong thứ tự góc nằm một bên, các điểm đứng sau Q nằm bên còn lại.

Bước 3: Duyệt theo thứ tự góc, Neutron tính +1, Giant tính -1, giữ tổng tiền tố s. Gặp điểm Giant Q đầu tiên mà tại đó s = 0 thì PQ chính là đáp án.

Vì sao đúng và vì sao luôn tồn tại: phía trước Q có s = 0 nghĩa là số Neutron bằng số Giant. Bỏ P và Q ra thì tổng còn lại là N - 1 Neutron và N - 1 Giant, nên phía sau Q cũng tự cân bằng. Còn tồn tại là vì tổng tiền tố đi từ 0 đến (N - 1) - N = -1, mỗi bước thay đổi đúng 1 đơn vị, nên chắc chắn có lần đầu tiên nó rơi từ 0 xuống -1. Bước đó chính là một điểm Giant đứng ngay sau vị trí có s = 0.

Mấy lưu ý khi cài đặt:

• Sắp xếp góc nên dùng tích có hướng (cross product) với số nguyên thay vì atan2 để tránh sai số.
• Thuật toán cần giả thiết không có 3 điểm thẳng hàng, em kiểm tra lại đề có đảm bảo điều này không nhé.
• Đề yêu cầu dạng y = ax + b nên em để ý trường hợp P và Q cùng hoành độ (đường thẳng đứng). Nếu đề không loại trừ trường hợp này thì có thể xoay nhẹ hệ trục hoặc chọn P theo hướng khác.

Chủ đề khác

2 câu

42Đang làm web cho thuê xe, làm tính năng định vị: xe di chuyển mỗi 2 giây gửi tọa độ về Server qua Socket, lưu vào Memory Cache (Class dùng biến Static, Getter/Setter), rồi đẩy lên bản đồ trên Website. Không biết mua phần cứng loại nào và dùng công nghệ như vậy đúng chưa?Sinh viên năm 3

Chào em, hướng đi tổng thể của em (GPS gửi về server, server đẩy xuống web qua socket) là đúng rồi. Thầy góp ý thêm mấy điểm để hệ thống chạy ổn hơn nhé.

Về phần cứng

Nếu lấy vị trí từ app trên điện thoại tài xế thì em không cần mua gì cả, vì điện thoại đã có sẵn GPS và 4G. Nhưng em cân nhắc lại: web cho thuê xe thường là khách tự lái, không có tài xế cài app, và người dùng có thể tắt app bất cứ lúc nào. Khi đó nên gắn thiết bị định vị cố định trên xe:

• Mua sẵn: các thiết bị GPS tracker cho xe máy có SIM 4G, hầu hết cho phép cấu hình gửi dữ liệu về server riêng qua TCP.
• Tự làm để học: ESP32 + module GPS (NEO-6M hoặc NEO-M8N) + module 4G (ví dụ dòng SIM7600 hoặc A7670). Em tránh các module chỉ có 2G như SIM800L vì mạng 2G ở mình đang bị tắt dần.

Về công nghệ, có mấy chỗ cần sửa

1. Em viết là để theo dõi "hành trình", nhưng Memory Cache chỉ lưu vị trí mới nhất nên không xem lại được lộ trình. Em nên tách hai phần: cache giữ vị trí hiện tại để hiển thị nhanh, còn lịch sử thì ghi vào database (gom lại ghi theo lô mỗi vài giây cho đỡ tải). Nếu dùng PostgreSQL thì có thêm PostGIS rất tiện cho dữ liệu tọa độ.

2. Class với biến static chạy được cho đồ án, nhưng có 3 vấn đề: restart server là mất sạch, không chạy được khi có nhiều server, và nhiều socket ghi cùng lúc dễ bị lỗi đồng bộ nếu dùng map thường. Tối thiểu em dùng cấu trúc thread-safe (ví dụ ConcurrentHashMap nếu là Java), còn làm chuẩn thì dùng Redis để lưu vị trí mới nhất, kết hợp Redis Pub/Sub để đẩy dữ liệu sang web.

3. Chiều từ web đến server dùng WebSocket (hoặc Socket.IO) là hợp lý. Còn chiều từ thiết bị gửi lên thì nếu dùng phần cứng IoT, em nên tìm hiểu MQTT, giao thức nhẹ và chịu được mạng chập chờn tốt hơn. Nếu dùng app điện thoại thì nhớ xử lý việc Android và iOS hay chặn app chạy nền (cần foreground service và quyền vị trí nền).

4. Gửi đều 2 giây một lần khá tốn pin và dữ liệu, nhất là lúc xe đứng yên. Em có thể chỉ gửi khi xe di chuyển quá một khoảng cách nhất định, hoặc tăng chu kỳ lên 5 đến 10 giây và cho marker trên bản đồ trượt mượt giữa hai điểm, người xem vẫn thấy như thời gian thực.

5. Một số chi tiết nhỏ: gửi kèm thời điểm lấy tọa độ để loại bỏ gói đến trễ, xác thực thiết bị bằng token để không ai gửi tọa độ giả được, và bản đồ trên web có thể dùng Leaflet với OpenStreetMap nếu muốn miễn phí.

Với đồ án sinh viên thì em có thể làm bản đơn giản trước (app điện thoại + WebSocket + lưu lịch sử vào database), chạy ổn rồi mới nâng cấp lên Redis hay phần cứng riêng.

43Muốn làm startup app đi thi từ vạch số 0: chưa có kinh nghiệm dự án, chưa biết code app, chưa có team hay mentor – nên làm gì đầu tiên? Làm sao tìm được bạn dev đồng hành?Sinh viên năm 2

Chào em, xuất phát điểm như em là rất bình thường, đa số các đội thi sinh viên đều bắt đầu như vậy. Nếu ở vị trí của em thì thầy sẽ làm theo thứ tự này:

1. Đọc thật kỹ thể lệ và tiêu chí chấm của cuộc thi. Rất nhiều cuộc thi khởi nghiệp chấm nặng về vấn đề, khách hàng và mô hình, còn sản phẩm chỉ cần ở mức bản mẫu demo được. Biết rõ cái này sẽ tránh được việc dồn sức vào code những thứ ban giám khảo không chấm. Nhớ ghi lại cả mốc thời gian nộp hồ sơ để lên kế hoạch ngược từ đó.

2. Kiểm chứng ý tưởng trước khi làm app. Em viết ra trong một trang: app giải quyết vấn đề gì, cho ai, họ đang giải quyết bằng cách nào, và vì sao cách của em tốt hơn. Sau đó đi nói chuyện thật với 10 đến 20 người dùng tiềm năng. Phần này không cần biết code, em làm được ngay hôm nay, và nó cũng là nội dung nặng ký nhất khi thuyết trình trước ban giám khảo.

3. Làm bản mẫu giao diện bằng Figma trước khi code. Chỉ cần vài màn hình chính có bấm chuyển được là đã đủ để đưa người dùng thử và để thuyết phục bạn dev vào team. Nếu chưa tìm được dev, em có thể tự dựng bản MVP bằng công cụ low-code như FlutterFlow hoặc Glide, kết hợp Firebase làm backend.

4. Tự học một framework phổ biến để ít nhất hiểu được cách app được làm ra. Em có thể chọn Flutter hoặc React Native vì một code chạy được cả Android lẫn iOS. Không cần giỏi ngay, nhưng biết cơ bản sẽ giúp em giao việc và ước lượng thời gian với dev sát thực tế hơn.

Về chuyện tìm bạn dev đồng hành

• Tìm ở các CLB lập trình, CLB khởi nghiệp của trường, các nhóm lập trình viên sinh viên, và các buổi hackathon. Người đi hackathon thường là người đang muốn tìm dự án.
• Mang theo thứ cụ thể khi rủ người khác: bản mô tả vấn đề, kết quả phỏng vấn người dùng, bản Figma. Dev sẽ sẵn lòng hơn nhiều khi thấy em đã làm thật chứ không chỉ có ý tưởng.
• Nói rõ vai trò của em (nghiên cứu người dùng, sản phẩm, thuyết trình, làm hồ sơ) và bạn ấy nhận được gì: kinh nghiệm dự án thật cho CV, giải thưởng chia thế nào. Thống nhất những chuyện này ngay từ đầu để sau này không bị mâu thuẫn.

Còn mentor thì em có thể hỏi giảng viên trong khoa, nhiều thầy cô rất sẵn lòng hướng dẫn đội thi của sinh viên, và một số cuộc thi cũng có chương trình mentor cho các đội vào vòng trong.

Chưa thấy câu hỏi của bạn?

Để lại câu hỏi ở phần bình luận bên dưới, hoặc nhắn tin trực tiếp nếu bạn cần lộ trình ôn tập riêng cho mục tiêu thi HSG, thi chuyên Tin của mình.