Nguồn: Facebook VNOI
Vậy là chỉ còn hơn 10 ngày nữa, kì thi học sinh giỏi quốc gia sẽ bắt đầu. Để giúp các bạn đạt được kết quả cao trong kì thi này, mình xin được ra mắt chuyên mục Mỗi ngày một lời khuyên. Kể từ mai cho đến trước khi thi, mỗi ngày mình sẽ chia sẻ một kinh nghiệm nho nhỏ để chuẩn bị cho kì thi. Đồng thời, chuyên mục cũng như chiếc đồng hồ đếm ngược từng ngày tới kì thi, làm tăng thêm phần hồi hộp, kịch tính, gay cấn, căng thẳng. Hy vọng rằng, với chiếc đồng hồ này, các bạn thí sinh sẽ cảm thấy thêm áp lực, thêm lo lắng, thêm sợ hãi, tăng xông, tăng huyết áp, ngất xỉu, đột quỵ, rối loạn tiêu hoá, biếng ăn, chậm lớn, còi xương, suy dinh dưỡng, chán đời, thất tình, muốn tự tử. Mình xin cam kết rằng, sau loạt bài viết này, bạn nào vẫn còn đủ can đảm bước vào phòng thi quốc gia thì cũng có đủ sức mạnh để vượt qua mọi sóng gió của kì thi… tuyển sinh vào đại học và sẵn sàng tham gia kì thi này.
Đừng quên check Facebook VNOI mỗi ngày để có được những lời khuyên bổ ích. Lưu ý rằng đây chỉ là những lời khuyên dựa trên kinh nghiệm thi VOI của mình, vì vậy các bạn nên tham khảo và áp dụng cho phù hợp. Chúc các bạn một năm mới tràn đầy niềm vui và gặt hái nhiều may mắn, khởi đầu bằng một kỳ thi HSG thành công rực rỡ.
Nguồn: Facebook VNOI
Trước mỗi kì thi, bạn cần tìm hiểu đề ra những năm trước để ngửi được "hương vị" của nó. Con số 5 năm là vừa đủ, bởi kỳ thi ở những năm trước nữa có thể khác xa so với hiện tại, lại vừa khó kiếm được đề, và trên hết, bạn không phải là một nhà sử học nên không có nhu cầu tìm hiểu xem vào thời Vua Hùng dựng nước, kỳ thi HSGQG đã diễn ra như thế nào; hay vào thời kỳ đồ đá, người ta đã thi lập trình hay chưa. Quan trọng là, bạn cần chú ý đến văn phong ra đề, một số chủ đề hay xuất hiện, hoặc độ khó (trung bình) của nó.
Lưu ý rằng, ĐỀ RA NĂM NAY KHÔNG ĐẢM BẢO SẼ TƯƠNG TỰ NHƯ NHỮNG NĂM TRƯỚC. Bạn cố gắng làm thử, nếu được, giành ra 3h đồng hồ liên tục. Tránh việc làm đc 1h, đi wc 5h, r làm nốt 2h nữa. Vì những j diễn ra trong wc k đảm bảo chất lượng bài thi sẽ giống như lúc bạn thi thật :v Ngoài ra, bạn có thể tìm hiểu mức điểm thi của năm đó để đánh giá trình độ của mình. Điểm thi từng năm có thể khác biệt, nhưng nhìn chung, chất lượng thí sinh thì k thay đổi nhiều.
Dưới đây là danh sách các bài thi chính thức của HSGQG (trên VNOJ), kèm theo bảng điểm trong các năm gần đây:
Kết quả thi chính thức:
Nguồn: Facebook VNOI
Đồ thị là chủ đề phổ biến nhất trong mỗi đề thi quốc gia. Năm nào cũng có đồ thị, ít thì một bài, nhiều thì có thể là hai (2016, 2013, 2012) hay thậm chí ba bài (2014). Không chỉ các đoạn mã nguồn và thuật toán, bạn cần chú ý đến cả phần lý thuyết và những khái niệm như chu trình/đường đi euler/hamilton, chu trình/đường đi đơn, đa đồ thị, khuyên,… để tránh việc không nắm được đề bài nếu như các khái niệm này xuất hiện trong đề. Các thuật toán như khớp, cầu, FordBellman dễ bị lãng quên do số lượng bài về nó không nhiều, nhưng hoàn toàn có thể gặp lại trong đề thi. Bài REFORM (VOI 2015 ) là điển hình của việc nhiều bạn không nhớ các thuật toán về cầu nên không giải được bài này, dù thuật toán của nó khá tự nhiên và đơn giản.
Nguồn: Facebook VNOI
Có một sự thật là, VOI là kì thi đòi hỏi kĩ năng hơn là tư duy thuật toán. Câu nói "cứ trâu hết là vào vòng hai" không phải là không có cơ sở, khi luật thi offline đang đẩy vai trò của sự cẩn thận lên cao hơn bao giờ hết. Nếu bạn đảm bảo toàn bộ code của bạn là không bug, nghĩa là điểm của bạn đúng với khả năng bạn làm được, thì đó đã là lợi thế quá lớn. Mình nghĩ rằng không có quá 30 bạn thí sinh có khả năng giữ được sự ổn định và tính cẩn thận trong khi làm bài, nghĩa là sẽ có rất ít bạn giữ được phong độ thi đấu ổn định giữa hai kì thi PreVOI và VOI. Vì vậy, bạn không được chủ quan. Giải nhất PreVOI hoàn toàn có thể đi kèm với giải ba VOI. Và ở chiều ngược lại, cũng không việc gì phải lo lắng, bởi nếu bạn chịu khó và nỗ lực, một giải ba PreVOI sẽ được nối tiếp bởi giải khuyến khích VOI.
Vì tương lai con em chúng ta, ngay từ lúc này, bạn nên chịu khó code nhiều, code chắc tay, code cẩn thận thay vì nghĩ những bài quá khó.
Nguồn: Facebook VNOI
180p là quá ngắn ngủi để bạn có thể làm trọn vẹn và chắc chắn cả ba bài trong đề thi. Trong 180p, bạn có quá nhiều việc để làm: Đọc đề, nghĩ thuật toán, code, kiểm tra tên file, sinh test chạy trâu so kết quả, đi wc, ăn uống, ngủ nghỉ, chơi dò mìn… Bởi thế, việc phân chia thời gian sao cho hiệu quả đóng vai trò rất quan trọng. Tiếc rằng, chiến lược tối ưu cho mỗi người không giống nhau, tùy thuộc vào khả năng nghĩ, tốc độ code, đặc điểm tâm sinh lý,… Vì vậy, trong hai ngày thi VO tới, bạn cần thực hiện mọi công việc trên như một kì thi thật. Sau khi thi xong, bạn nên nhớ lại quá trình mình làm bài thi, phân tích và đánh giá nó (Thời gian phân chia vào công việc nào bị quá ít, quá nhiều, sắp xếp thứ tự làm bài đã hợp lý chưa,…) Những phân tích này là rất quan trọng, nó giúp bạn rút kinh nghiệm cho ngày thi chính. Vì vậy, ngoài việc tập trung thi, cần ghi nhớ thật kĩ quá trình mình đã làm bài như thế nào.
Chúc các bạn thi tốt :D
Nguồn: Facebook VNOI
Sau khi nghĩ ra một thuật toán, bạn biết được độ phức tạp của nó. Nhưng câu hỏi đặt ra là, làm thế nào để biết một thuật toán là đủ nhanh hay chưa. Nếu biết trước timelimit, thông thường, một thuật toán được coi là đủ nhanh nếu giá trị độ phức tạp ứng với test max là dưới timelimit * 1e8.
Ví dụ, nếu có một thuật toán $O(Nlog^2N)$ và bài toán có giới hạn $N \le 3e5$ thì khi đó Nlog^2N ~ 11e7, nghĩa là nếu timelimt 1s thì sẽ hơi chậm một chút, còn nếu timelimit 2s thì có thể chấp nhận được.
Tuy nhiên, cách đánh giá trên khá phiến diện, vì nhiều lý do: Hàm đánh giá độ phức tạp không thể hiện chính xác thời gian chạy (không tính hằng số), cách cài đặt và tốc độ của mỗi máy chấm một khác. Tệ hại hơn, nếu không biết trước timelimit, thì cũng còn chẳng biết đánh giá ra làm sao. Tuy nhiên, theo mình nghĩ, nếu một thuật toán có độ phức tạp tầm 3e8 trở xuống có thể coi là chấp nhận được. Chấp nhận được ở đây không có nghĩa là thuật toán đó là đủ hiệu quả để đạt điểm tối đa, mà có nghĩa là, bạn nên bắt tay vào việc code thuật toán đó thay vì cố gắng tối ưu thêm. Đôi khi, việc tối ưu thuật toán từ NlogN xuống N hay Nlog^2N xuống NlogN là không đơn giản, tốn nhiều thời gian và đôi khi sự tăng độ khó trong cài đặt sẽ khiến bạn thiếu thời gian làm bài. Chưa kể, những thuật toán có độ phức tạp khoảng tầm 3e8 trở xuống thường chỉ bị TLE một vài test, chứ không phải cả subtask, nên không làm thay đổi quá nhiều điểm số.
Ví dụ, bài MINROAD 2014, hồi đấy mình nghĩ ra một thuật toán O(Nlog^2N), với giới hạn N <= 3e5. Mình ngồi code luôn bài đấy, mà không nghĩ để tối ưu xuống O(NlogN). Về sau, mình phát hiện ra mình là người duy nhất code thuật đó, tất cả mọi người khác trong đội đều làm O(NlogN) hay O(N). Mình nghĩ quyết định lúc đó khá hợp lý, bởi hồi đấy mình code khá chậm và rất tệ, nên cần ưu tiên việc code và kiểm tra hơn và chấp nhận không được điểm tối đa bài đó.
Nguồn: Facebook VNOI
Gần đây, theo khảo sát của một số tổ chức giấu tên, xuất hiện tình trạng nhiều thí sinh của kì thi VOI thích khoe hàng trong phòng thi. Đặc điểm chung, những thí sinh này thường inbox tâm sự riêng với GS. PVH về ham muốn được thể hiện những thuật toán hàng khủng như thuật toán Lehman, Suffix Array, DFS khử đệ quy bằng stack,… Qua điều tra sơ bộ, chúng tôi đã xác định được ba nguyên nhân chính dẫn tới căn bệnh nghiện show hàng này như sau:
Căn bệnh này đang có xu hướng lây lan nhanh trong giới học sinh giỏi tin của các trường chuyên, và diễn biến rất phức tạp. Vì vậy, mình khuyến cáo các bậc phụ huynh cần theo dõi con em mình chặt chẽ, hạn chế cho trẻ tiếp xúc với ma túy, thực phẩm bẩn, nhắc trẻ mang theo não thường xuyên. Nếu thấy con có biểu hiện lạ, cần đưa đến trung tâm GS. PVH gần nhất để được chữa trị kịp thời.
Xin cảm ơn.
Mình nghĩ có lẽ không cần nhắc các bạn vấn đề này, nhưng gần đây có mấy bạn rất hổ báo vào inbox mình hỏi về thuật toán Leman jj đó liên quan đế số nguyên tố. Mình thú thật là mình ứ biết cái thuật toán này là gì, và có lẽ nó khó có thể xuất hiện trong kỳ thi tới.
Tất nhiên, không có bất kỳ giới hạn kiến thức nào trong kì thi này. Nhưng mình vẫn muốn nhắc lại rằng, với những thuật toán dù biết nhưng cài đặt không thành thạo, không dùng thường xuyên, hoặc rất phức tạp (KMP, Suffix Array, Dinitz, DFS khử đệ quy, …) thì bạn không nên cài đặt trong phòng thi. Nếu cài sai, bạn sẽ trong trạng thái tiến thoái lưỡng nan: Debug thì mất quá nhiều thời gian, xóa hết thì phí công code.
Nhớ rằng, VOI không là chỗ thích hợp cho việc phô trương sức mạnh, hãy cẩn thận và chắc chắn để đảm bảo những sự cố thương tâm không xảy ra.
Nguồn: Facebook VNOI
Sau một ngày gián đoạn, hôm nay chuyên mục "mỗi ngày một lời khuyên xin phép đc tiếp tục.
Những bài toán có đặc tính multitest là những bài mà trong đó một file input chứa nhiều bộ dữ liệu. Các bộ dữ liệu (test) này luôn độc lập với nhau, và luôn được chương trình của chúng ta xử lý theo kiểu tuần tự, nghĩa là đọc từng bộ dữ liệu, xử lý, in ra output, rồi mới đọc bộ dữ liệu tiếp theo. Có ba lý do chính dẫn tới kiểu input này:
Trừ trường hợp đầu tiên, khi đó, số lượng test trong một file input sẽ rất lớn (1e3, 1e4, …), và được chỉ rõ trong đề bài, còn hai trường hợp còn lại, số lượng test thường khá nhỏ (và đa số các test trong file input không phải test max), số lượng test có thể không được nhắc đến trong đề, và thuật giải bài toán sẽ y hệt như khi trong file input chỉ có một test.
Trong kỳ thi quốc gia, đa số các bài multitest đều thuộc hai nguyên nhân dưới. Bởi thế, trong quá trình tìm kiếm thuật toán, bạn không cần quan tâm đến số lượng test có trong một file input.
Tuy nhiên, trong khi code, bạn lại cần rất chú ý đến vấn đề multitest, bởi trước khi xử lý một test, bạn cần khởi tạo lại biến, mảng,… để xoá dấu vết của bộ test cũ.
Khi có multitest, việc code bug hoặc quên khởi tạo sẽ tạo hậu quả rất nghiêm trọng (90% là bạn sẽ được 0 điểm). Do đó bạn cần ưu tiên sinh test và kiểm tra kĩ những bài này. Tuy nhiên, việc sinh test trong những bài này lại có lợi thế, bởi khi bạn sinh một file input gồm nhiều test, số test bạn test được lớn hơn rất nhiều. Có một kinh nghiệm nhỏ để giúp các bạn tránh việc khởi tạo thiếu mảng:
Nguồn: Facebook VNOI
Đây là một kĩ năng nhỏ nhưng quan trọng, trong khi làm bài, bạn luôn phải để ý lượng thời gian còn lại, để xem mình nên nghĩ tiếp một bài hay k, hay bắt đầu việc code trâu luôn, hoặc là bạn có thể đi wc thêm bao nhiêu lần nữa,… Hoặc đơn thuần bạn cần biết là sắp hết giờ r để cảm thấy tăng huyết áp, sợ hãi và k làm nổi cái j nữa :v Tưởng tượng, 8h bắt đầu thi, máy tính bạn chỉ 7h. Đến khi máy tính chỉ 9h45, bạn yên tâm còn 75p, quá thừa để AC cả 3 bài, và bắt đầu chìm vào giấc ngủ. Thế nhưng, 15p sau thình lình gv gọi bạn dậy và bạn chợt nhận ra tương lai sụp đổ, cuộc đời bế tắc. Do đó, việc kiểm soát thời gian là vô cùng quan trọng. Một trong những lỗi về chiến lược mà kể cả những ng đã thi nhiều lần mà vẫn mắc, đó là quá cay cú đi tìm lời giải cho một bài toán, kết quả là không còn thời gian chạy trâu các bài còn lại. Nên nhớ rằng, đôi khi sub cuối bài 2 khó hơn rất nhiều, nhưng lại ít điểm hơn sub 1 bài 3, do đó trước khi bắt đầu nghĩ một bài, bạn cần đặt gia hạn mức thời gian nghĩ bài đó.
Với các bạn code C++, việc #include<bitch/stdc++.h> vô cùng tiện lợi, nó giúp bạn khỏi bận tâm về việc include mọi thư viện khác. Tuy nhiên, cách đây ba năm, mọi bản G++ tích hợp sẵn trong Themis đều quá cũ, việc sử dụng thư viện này chắc chắn dẫn tới lỗi biên dịch. Cách đây hai năm, việc sử dụng thư viện này vẫn được coi là điều cấm kỵ trong kì thi học sinh giỏi quốc gia. Ngày nay, do các bản Themis đã được cập nhật, việc sử dụng thư viện trên đã được chấp nhận. Do vậy, theo quan điểm cá nhân, #include<bits/stdc++.h> không phải là lựa chọn mạo hiểm. Tuy nhiên, không một quy định nào nói rõ phiên bản Themis nào sẽ được sử dụng, nên cũng không lấy gì đảm bảo rằng #include<bits/stdc++.h> không phải là tai họa. Bởi vậy, các bạn nên nhớ tên các thư viện sau đây để include thay thế cho thư viện huyền thoại kia.
Trong hai ngày tới, hãy code một số bài đơn giản để thay đổi thói quen include, sẽ không vất vả đâu :) Ghi chú:
Danh sách các thư viện hay dùng:
Kỳ thi quốc gia đã đến thật gần. Các bạn đã bỏ ra rất nhiều công sức, tâm huyết và niềm tin vào những tháng học đôij tuyển rồi phải không :) để có những bước chuẩn bị hoàn hảo cuối cùng, hãy tham khảo bài viết dưới đây. (NOTE: Post này chỉ nhằm mục đích giải trí. Bạn nào cảm thấy quá căng thẳng hoặc có tính mê tín thì có thể k đọc nữa.)
a/ Lựa chọn thức ăn phù hợp:
Ăn gì trong những ngày thi là một câu hỏi khó. Bạn sẽ phải gạch tên rất nhiều những món ăn khoái khẩu của mình để có một kì thi suôn sẻ:
b/ Không nghe các bài hát mang nội dung "nhạy cảm".
Nếu như ăn chuối là điều cấm kị vì nó khiến đề thi của bạn bị chuối, thì cũng như vậy, những bài hát có những từ ngữ xấu cũng nên bị loại bỏ trong giờ phút căng thẳng này. Ví dụ, nghe những bài hát có chữ "trôi" hay chữ "lạc" sẽ khiến bạn làm bài lạc đề, kiến thức bị trôi nổi giữa đời, vì thế bạn nên tránh xa những bài như vậy.
(Đùa tí, các bạn nóng nảy vl. Đừng phẫn nộ mình sau khi đọc đến dòng này nhé)
c/ Không tắm trước khi thi.
Nhiều người không gội đầu trước khi thi vò lo sợ kiến thức trên đầu sẽ bị rửa trôi.Thực tế, kiến thức còn được lưu trữ ở nhiều nơi bí ẩn khác trong cơ thể. do đó, bạn không nên tắm nếu thuật toán được lưu trên da, ghét hay gàu. Ngoài ra, nếu bạn lưu ở bộ phận tích trữ khác, bạn nên kìm nén, nhịn không được phép xả ra ngoài trước khi thi xong.
d/ Chọn chỗ ngồi hợp phong thủy
Phong thủy mang ý nghĩa rất quan trọng với con người. Trước khi làm những việc lớn, như xây nhà, lấy vợ, người ta đều phải xem phong thủy. Thi HSGQG cũng vậy, vì nó ảnh hưởng rất lớn đến tương lai bạn, bạn cũng nên chọn chỗ ngồi, kê bàn ghế theo hướng hợp với phong thủy của mình để có được chất lượng bài thi cao hơn.
e/ Chọn thời gian thi phù hợp.
Giờ hoàng đạo luôn đem lại sự suôn sẻ và những điều tốt lành. Vì vậy, các bạn hãy lựa chọn thời gian thi vào những giờ hoàng đạo để làm bài tốt hơn. Ngày 5/1, các giờ hoàng đạo bao gồm Sửu (1h - 3h), Ngọ (11h - 13h), Mùi (13h - 15h), Tuất (19h - 21h) và Hợi (21h - 23h).
Nếu có thể, hãy làm bài thi quốc gia vào những khoảng thời gian này, sẽ có lợi cho bạn hơn. Trong ngày mai, mình sẽ cố gắng liệt kê thêm những kinh nghiệm khác để chia sẻ với các bạn. Chúc các bạn nghỉ ngơi thoải mái và có một buổi khai mạc rực rỡ :)
Giờ k phải là lúc lo âu căng thẳng hay xám hối vì sự lười nhác của bạn nữa. Hãy nghỉ ngơi, thư giản thoải mái, làm những gì khiến bạn sung sướng nhất trong ngày cuối cùng này.
Chuyên mục của chúng tôi cũng xin được kết thúc tại đây. Rất cám ơn sự chú ý theo dõi và ủng hộ nhiệt tình của các bạn giành cho mình. Hy vọng rằng, qua series bài viết này, bạn tìm ra được cho mình những bài học bổ ích và sẽ áp dụng được chúng một cách hợp lý cho hai ngày sắp tới.
Chắc chắn, sang năm mình sẽ mở ra những chuyên mục hay hơn nữa :D
Cuối cùng, xin chúc các bạn gặp nhiều may mắn, và mọi thứ suôn sẻ trong hay ngày thi sắp tới. Ai ai cũng đạt được ước nguyện của mình.
À quên, chúc 5 bạn NDT, GTTV, DXB, NPD và TQA ngày mai vui vẻ :) Ahihi
Nguồn: Facebook VNOI
Khi đi thi các bạn cần chú ý tránh những code có thể dẫn đến Compile Error:
namespace A {
int y1, next;
void solve() {
cout << "OK" << endl;
y1 = next = 1;
cout << y1 << ' ' << next << endl;
}
};
int main() { A::solve(); }Bài 2 ngày 1 (VO17TV) có 1 số bạn dùng Suffix array. Cách này đúng nhưng cài đặt phức tạp hơn rất nhiều so với dùng hash. Khi đi thi mỗi lựa chọn sai lầm về thuật toán kiểu này sẽ làm bạn tiêu tốn rất nhiều thời gian, và thường không sửa chữa kịp.
Vì vậy khi nghĩ ra bất kỳ thuật toán nào, bạn nên tiếp tục suy nghĩ xem có cách nào đơn giản hơn không. Chỉ bắt đầu code khi thật sự chắc chắn không có cách nào tốt hơn.
Có chiến thuật rõ ràng cho 1 bài. Với những bài cài đặt phức tạp như bài VO17BACH, bạn cần có chiến thuật rõ ràng ngay từ đầu là debug như thế nào.
Ví dụ: