Đối với các bạn đã theo đuổi Lập trình thi đấu từ lâu, có lẽ cái tên Centroid Decomposition hay Kỹ thuật phân tách trọng tâm cũng không còn xa lạ. Đây là một trong những kỹ thuật xử lý cây mạnh mẽ và phổ biến ở cấp độ các cuộc thi lớn.
Trong bài viết này, chúng mình sẽ cùng nghiên cứu một khía cạnh nhỏ của Kỹ thuật phân tách trọng tâm: ứng dụng của chúng trong việc xử lý các truy vấn online trên cây. Hiện nay tuy chưa có quá nhiều tài liệu đề cập đến vấn đề này, song đây lại là một chủ đề khá phổ biến và xuất hiện trong nhiều cuộc thi lập trình.
Lưu ý, bài viết sử dụng cơ số mặc định cho hàm ~\log~ là cơ số ~2~.
Ý tưởng chung
Nhắc lại Kỹ thuật phân tách trọng tâm
Kỹ thuật phân tách trọng tâm đã được trình bày rất chi tiết và đầy đủ tại bài viết này thuộc nền tảng VNOI Wiki. Mình xin phép nhắc lại ý tưởng chung của kỹ thuật một cách ngắn gọn như sau:
Để xử lý bài toán trên một cây ~T~, ta đặt gốc của nó tại trọng tâm, gọi là ~C~, rồi xử lý thành phần của bài toán liên quan đến đỉnh ~C~.
Gọi ~T_v~ là các cây con của đỉnh gốc ~C~. Ta tiếp tục xử lý đệ quy bài toán trên các cây ~T_v~.
Ảnh minh họa Kỹ thuật phân tách trọng tâm
Quá trình chia để trị được thực hiện đến khi ta được cây chỉ có ~1~ đỉnh. Khi đó ta dừng đệ quy.
Như vậy, bản chất của Kỹ thuật phân tách trọng tâm là một thuật toán Chia để trị trên cây. Ở mỗi tầng chia để trị, tổng kích thước của các cây cần được xử lý là ~\mathcal{O}(N)~ và do ta luôn chọn trọng tâm để phân tách cây nên chiều cao của cây chia để trị chỉ là ~\mathcal{O}(\log N)~.
Cây chia để trị khi thực hiện Kỹ thuật phân tách trọng tâm trên cây
Thông thường khi sử dụng Kỹ thuật phân tách trọng tâm, ta sẽ duyệt cả cây chia để trị trong ~\mathcal{O}(\log N)~ nhân cho độ phức tạp để xử lý một tầng chia để trị. Tuy nhiên, trong nhiều trường hợp, ta cũng có thể sử dụng cây chia để trị này để trả lời các truy vấn online, bằng cách xây dựng trước thông tin của cây chia để trị và chỉ duyệt qua ~\mathcal{O}(\log N)~ cây con chứa thông tin liên quan đến truy vấn cần trả lời.
Bài toán mở đầu
Để nắm rõ mô hình chia để trị trên cây, chúng ta cùng nghiên cứu bài toán interactive sau:
Cho một cây gồm ~N~ đỉnh có gốc là ~1~ và một đỉnh đặc biệt ~x~ không được biết trước. Yêu cầu tìm đỉnh ~x~, sử dụng không quá ~36~ câu hỏi thuộc một trong hai dạng:
Ta cho đỉnh ~u~, trình chấm sẽ trả về ~\texttt{dist}(u, x)~.
Ta cho đỉnh ~u~ bắt buộc phải là tổ tiên của ~x~ và khác ~x~, trình chấm sẽ trả về đỉnh thứ hai trên đường đi từ ~u~ đến ~x~, tức đỉnh gần ~x~ nhất trong các đỉnh kề ~u~.
Giới hạn:
~2 \leq N \leq 2 \cdot 10^5~.
Ý tưởng
Khuyến khích bạn đọc tự giải quyết bài tập trên trước khi tiếp đến phần này
Trong bài viết này, chúng ta sẽ tập trung vào lời giải sử dụng Kỹ thuật phân tách trọng tâm (một lời giải khác sử dụng Heavy-light Decomposition).
Nhìn vào ảnh minh họa cây chia để trị của quá trình phân tách trọng tâm như trên, giả sử ta xét cây ban đầu có trọng tâm là nút màu xanh dương. Nếu có thể xác định xem đỉnh ~x~ cần tìm nằm ở đâu trong 3 cây con màu xanh lá, vàng và hồng, ta có thể chọn đi xuống cây con tương ứng trên cây chia để trị. Khi đó, số lượng đỉnh thuộc tập tìm kiếm sẽ giảm đi ít nhất một nửa.
Lặp lại quá trình tìm kiếm như vậy đến khi ta gặp một cây con có trọng tâm là đỉnh ~x~ cần tìm, hoặc gặp một nút lá trên cây chia để trị. Khi đó ta sẽ có đáp án.
Như vậy, bài toán bây giờ là xác định xem, với một cây ~T~ (là cây con của cây ban đầu) chứa ~x~, khi xóa trọng tâm ~C~ của ~T~ ra khỏi cây, ~x~ sẽ thuộc cây con nào. Tuy nhiên, các câu hỏi được đề bài cho trả về thông tin trên cây ban đầu, ta có thể đưa ra một nhận xét nhỏ rằng việc xét phạm vi của bài toán phụ trên cây ~T~ hay cả cây ban đầu là như nhau.
Một cách giải quyết bài toán phụ bằng 1 truy vấn mỗi loại là:
Đầu tiên, ta sử dụng một truy vấn khoảng cách để xác định xem ~x~ có thuộc cây con của ~C~ hay không (xét cây con ban đầu có gốc là đỉnh ~1~). Câu trả lời là có khi và chỉ khi ~\texttt{depth}[C] + \texttt{dist}(C, x) = \texttt{dist}(1, x)~.
Nếu ~x~ thuộc cây con của ~C~, ta có thể xác định cây con chứa ~x~ khi xóa ~C~ bằng cách hỏi đỉnh thứ hai trên đường đi từ ~C~ đến ~x~. Ta có thể đảm bảo ~C~ là tổ tiên của ~x~ trong trường hợp này.
Ngược lại, ta có thể kết luận ngay ~x~ thuộc cây con chứa các đỉnh nằm ngoài cây con của ~C~.
Một lưu ý nhỏ là ta chỉ cần dùng 1 truy vấn khoảng cách để tính ~\texttt{dist}(1, x)~ trước khi bắt đầu chia để trị. Quá trình tìm kiếm sẽ kết thúc khi ta bắt gặp trường hợp ~\texttt{dist}(C, x) = 0~. Khi đó, đáp án cũng chính là đỉnh ~C~.
Nếu đề bài yêu cầu giải bài toán nhiều lần trên cùng một cây cho trước, ta hoàn toàn có thể tách hàm trả lời ra thành hai phần. Phần đầu tiên tính trước trọng tâm của mọi cây con mà ta có thể đi qua trong quá trình chia để trị và phần thứ hai được thực hiện tương tự code tham khảo ở trên dựa trên dữ liệu đã được tính trước.
Ứng dụng trên truy vấn online trên cây
Như vậy, từ ý tưởng của bài tập interactive trên, ta cũng có thể đưa ra một mô hình áp dụng Kỹ thuật phân tách trọng tâm vào truy vấn online trên cây, dựa vào cây chia để trị được sinh ra từ quá trình sử dụng kỹ thuật này. Nhìn chung, ta sẽ chia thuật toán thành hai giai đoạn:
Tiền xử lý (xây dựng cây chia để trị): Với tầng thứ ~\ell~ của cây chia để trị, ta tính trước ~\texttt{centroid}_\ell[u]~ là trọng tâm của cây chứa ~u~. Nếu đỉnh ~u~ đã bị xóa từ tầng chia để trị cao hơn, ta quy ước ~\texttt{centroid}_\ell[u] = 0~, xem như giá trị này không có ý nghĩa. Ngoài ra, ta có thể tính thêm các giá trị khác tùy vào nhu cầu của bước trả lời truy vấn.
Trả lời truy vấn: Thực hiện chia để trị với thông tin từ mảng ~\texttt{centroid}_\ell[]~.
Việc cài đặt bước tiền xử lý khá giống cài đặt Centroid Decomposition thông thường:
intsz[N],centroid[LOG][N];vector<int>adj[N];boolremoved[N];intszDfs(intu,intp){sz[u]=1;for(intv:adj[u])if(v!=p&&!removed[v])sz[u]+=szDfs(v,u);returnsz[u];}intfindCentroid(intu,intp,intsztr){if(u==p)szDfs(u,u);for(intv:adj[u])if(v!=p&&!removed[v]&&sz[v]>sztr/2)returnfindCentroid(v,u,sztr);returnu;}voiddfsTree(intu,intp,introot,intlevel){centroid[level][u]=root;// tiền xử lý các giá trị cần tính khác ở đây// ...for(intv:adj[u])if(v!=p&&!removed[v])dfsTree(v,u,root,level);}voidcentroidDecomposition(intu,intlevel=0){// tìm trọng tâm của cây rồi đặt làm gốcintroot=findCentroid(u,u);// duyệt cây với gốc mớidfsTree(root,root,root,level);// xóa gốc ra khỏi cây rồi duyệt tiếp các cây conremoved[root]=true;for(intv:adj[root])if(!removed[v])centroidDecomposition(v,level+1);}
Bài tập minh họa
Để giúp bạn đọc hiểu rõ hơn về ý tưởng ứng dụng Kỹ thuật phân tách trọng tâm vào truy vấn online trên cây, ta cùng nghiên cứu hai bài toán minh họa kinh điển cho hai trường hợp truy vấn không cập nhật và có cập nhật.
Ngoài ra, để thuận tiện, chúng ta sẽ thống nhất sử dụng các ký hiệu sau cho phần còn lại của bài viết:
~u \rightarrow v~ hoặc ~v \rightarrow u~ là đường đi đơn giữa ~u, v~ trên cây.
Hàm ~\texttt{centroid}(T)~ là hàm trả về một trọng tâm bất kỳ của cây ~T~.
Hàm ~\texttt{dist}(u, v)~ là số cạnh nằm trên đường đi đơn ~u \rightarrow v~ của cây.
Cho cây gồm ~N~ đỉnh có trọng số cạnh và ~Q~ truy vấn online có dạng:
Cho hai tập đỉnh ~A, B~, tìm ~\min_{s \in A, t \in B} \texttt{dist}(s, t)~.
Giới hạn:
~2 \leq N \leq 5 \cdot 10^5~.
~1 \leq Q \leq 10^5~.
Trọng số cạnh là các số nguyên dương không quá ~10^9~.
Ý tưởng
Khuyến khích bạn đọc tự giải quyết bài tập trên trước khi tiếp đến phần này
Như đã giới thiệu ở phần trước, ta sử dụng ý tưởng chia để trị trên cây. Gọi ~T~ là cây con đang được xử lý và ~A_T, B_T~ là tập truy vấn gồm các đỉnh thuộc cây ~T~. Ta tìm đường đi ngắn nhất giữa một cặp đỉnh ~a, b~ (với ~a \in A_T~ và ~b \in B_T~) đi qua ~C = \texttt{centroid}(T)~, các cặp đỉnh còn lại sẽ được truyền xuống các cây con của đỉnh ~C~.
Đặt gốc của cây ~T~ là đỉnh ~C~, để tính đường đi ngắn nhất cần tìm, ta chỉ cần tính với mọi đỉnh thuộc cây ~T~ một giá trị ~\texttt{depth}[u]~ là khoảng cách giữa ~u~ và đỉnh gốc ~C~. Khi đó, ta chỉ cần duyệt qua các cây con của ~T~ rồi duy trì hai biến ~\texttt{best}_A, \texttt{best}_B~ là giá trị ~\texttt{depth}[u]~ trong các đỉnh nằm trong các cây con đã duyệt.
Như vậy, khi tiền xử lý, ta chỉ cần tính các giá trị ~\texttt{depth}_\ell[u]~ là khoảng cách giữa ~u~ và đỉnh gốc ~\texttt{centroid}_\ell[u]~ tại tầng chia để trị thứ ~\ell~.
Như vậy, độ phức tạp tiền xử lý là ~\mathcal{O}(N \log N)~ và độ phức tạp cho mỗi truy vấn là ~\mathcal{O}((|A| + |B|) \log N)~ do tổng độ phức tạp tại mỗi tầng chia để trị là ~\mathcal{O}(|A| + |B|)~.
Cài đặt
Lưu ý, ta cần cài đặt khéo léo một chút để có thể duyệt các cây con của ~T~ trong ~\mathcal{O}(|A| + |B|)~. Khi đó, độ phức tạp như đã phân tích mới được đảm bảo.
Cho cây gồm ~N~ đỉnh có trọng số đỉnh được cho bởi một dãy ~a~ và ~Q~ truy vấn online, mỗi truy vấn thuộc một trong hai loại:
Cập nhật trọng số của một đỉnh ~v~ theo giá trị ~w~, tức gán ~a_v \leftarrow w~.
Cho đỉnh ~u~, tìm ~\min_{v \neq u} a_v + \texttt{dist}(u, v)~ với ~\texttt{dist}(u, v)~ là số cạnh trên đường đi đơn từ ~u~ đến ~v~.
Giới hạn:
~1 \leq N, Q \leq 2 \cdot 10^5~.
~1 \leq a_v \leq 10^9~.
Trả lời truy vấn
Khuyến khích bạn đọc tự giải quyết bài tập trên trước khi tiếp đến phần này
Một lần nữa, ta sử dụng Chia để trị. Gọi ~T~ là cây con đang được xử lý có trọng tâm ~C~ tại tầng chia để trị ~\ell~, ta xét các đường đi ~u \rightarrow v~ đi qua ~C~, lưu ý rằng ~u~ là đỉnh được cố định trong truy vấn. Như vậy, với mọi cây con ~T_v~ không chứa ~u~, ta chỉ cần duy trì giá trị ~\min_{v \in T_v} a_v + \texttt{depth}_\ell[v]~ và đặt là ~\texttt{opt}_\ell(T_v)~. Khi đó, giá trị cần tính tại tầng chia để trị ~\ell~ là:
Thông thường, việc tính ~\min_{T_v \not\owns u} \texttt{opt}_\ell(T_v)~ sẽ cần đến một cấu trúc dữ liệu hỗ trợ. Tuy nhiên, ta có thể đưa ra nhận xét rằng việc bỏ đi điều kiện ~T_v \not\owns u~ sẽ không làm ảnh hưởng đáp án cuối cùng. Lý do là vì nếu cây con ~T_v \owns u~ được chọn trong hàm ~\min~, điều đó cũng tương đương với việc ta đang chọn một đường đi qua một cạnh nào đó nhiều hơn ~1~ lần. Khi đó, luôn tồn tại một phương án hợp lệ và có chi phí thấp hơn để thay thế khi ta tiếp tục chia để trị xuống cây ~T_v~ đó.
Sau đó, ta tiếp tục chia để trị xuống cây con ~T_v~ chứa ~u~.
Cập nhật
Với công thức rút gọn như trên, với mỗi cây con, ta chỉ cần tính ~\texttt{opt}(T) = \min_{v \in T} (a_v + \texttt{depth}_\ell[v])~. Lúc này, ta cũng không cần quan tâm tầng chia để trị ~\ell~ nữa. Hơn nữa, để tiện cho phần cài đặt, ta có thể sử dụng chính chỉ số của trọng tâm ~\texttt{centroid}(T)~ để đánh số cho các cây ~T~ trong quá trình duyệt.
Như vậy, ta định nghĩa lại mảng ~\texttt{opt}[]~ như sau:
Lúc này, do mỗi nút chỉ được chọn làm trọng tâm đúng một lần trên cả cây chia để trị, ta không cần dùng tham số ~\ell~ để phân biệt các tầng chia để trị nữa.
Để cập nhật một giá trị ~a_v~, ta cần cập nhật các giá trị ~\texttt{opt}[C]~ cho các cây nằm trên đường đi xuống nút ~v~ trên cây chia để trị. Việc cập nhật có thể được thực hiện cùng với một cấu trúc dữ liệu có sẵn như priority_queue hoặc multiset.
Như vậy, ta có độ phức tạp ~\mathcal{O}(\log^2 N)~ cho mỗi phép cập nhật và ~\mathcal{O}(\log N)~ cho mỗi phép trả lời truy vấn, do ta có thể lấy phần tử nhỏ nhất từ một priority_queue hoặc multiset trong ~\mathcal{O}(1)~.
Cài đặt
Với đặc thù của các truy vấn được nêu trong bài toán, ta hoàn toàn có thể chỉ sử dụng đệ quy trong bước tiền xử lý và khử đệ quy khi trả lời truy vấn.
Lưu ý, với cách cài đặt như trên, mỗi lần gọi truy vấn có thể kéo theo các thao tác pop trên priority_queue, khi này độ phức tạp của hàm trên thực tế không phải là ~\mathcal{O}(\log N)~ nữa. Tuy nhiên, số lần thực hiện thao tác pop phụ thuộc vào số thao tác cập nhật trước đó, nên ta có thể xem như độ phức tạp được gây ra bởi thao tác pop được tính cho hàm cập nhật chứ không phải hàm truy vấn.
Em tên là Đặng Huy Hậu, học sinh lớp 11 Tin, trường THPT chuyên Thăng Long - Lâm Đồng. Mọi người sẽ bắt đầu biết đến em qua hai cột mốc: cột mốc đầu tiên là thông qua kỳ thi Tin học trẻ. Cho đến ngày hôm nay thì em đã tham gia kỳ thi này được 8 năm và đạt được nhiều thành tích cao, tính cả từ kỳ thi cấp huyện đến cấp toàn quốc là em đã bắt đầu thi từ lớp 3 rồi. Có thể coi kỳ thi này là một chặng đường đánh dấu sự trưởng thành của em với bộ môn Tin học này. Và cột mốc thứ hai cũng là một trong những thành tích lớn nhất mà em đã đạt được là Huy chương Bạc IOI năm 2025. Bản thân em cảm thấy khá là tự hào khi đã trở thành thành viên của đội tuyển Olympic Quốc tế và đã đem lại thành tích lớn về cho đất nước.
Biên tập:
Phan Nhật Lam Phương - Trường Đại học Công nghệ thông tin, ĐHQG-HCM
Nguyễn Tấn Minh - Trường Đại học Khoa học tự nhiên, ĐHQG-HCM
Nguyễn Trung Quân - Trường Đại học Khoa học tự nhiên, ĐHQG-HCM
Phỏng vấn
Anh có được tiếp xúc với em lần đầu là từ VNOI CUP 2025. Em có thể miêu tả ngắn gọn hành trình mà em đến với VNOI CUP được không?
Em có tham gia VNOI CUP được 3 năm. Trong 2 năm đầu em thi VNOI CUP thì năm thứ nhất em không được áo, năm thứ hai thì có và chưa lần nào em nằm trong top 50 trở lên của vòng loại VNOI CUP những năm đó. Đến năm thứ ba thì em làm khá là tốt, thế nên là được vô chung kết và em được vô địch luôn năm đó ạ.
Vậy tức là em bắt đầu thi VNOI CUP từ năm em học lớp 8 đúng không?
Dạ vâng.
Trở lại với các câu hỏi thì em đã bảo là em thi Tin học trẻ từ năm lớp 3, tức là em đã tiếp xúc với máy tính cụ thể là từ khi nào?
Cái này thì em cũng không nhớ rõ, nhưng mà chắc là phải từ năm lớp 2. Hồi đó là bố mẹ em có cho em một chiếc máy tính cũ để em xài. Lúc đó thì máy tính gần như chỉ để phục vụ cho việc học hoặc là xem YouTube. Ngày xưa thì em còn chơi một số trò chơi trên máy nữa.
Lúc đó em có nghĩ là em sẽ đi theo con đường Tin học này rất là xa đến tận bây giờ không?
Em nghĩ là không. Ngày xưa thì em chỉ sử dụng máy tính gần như là với những mục đích đó thôi. Lên lớp 3 thì bước ngoặt nó xảy ra khi mà em được học tin học và được tiếp xúc với máy tính nhiều hơn. Lúc đó thì em đã mò gần như tất cả phần mềm trên máy của trường, và em thấy phần mềm Scratch. Phần mềm này thì em thấy khá là thú vị, thế nên em đã mò ra hết cả buổi ra chơi hôm đó. Về sau thì em được thầy cô phát hiện và đã được dạy Tin một cách bài bản, và cũng trở thành thành viên của đội tuyển để tham gia Tin học trẻ năm đó luôn. Và đó cũng là lần đầu tiên mà em biết đến kỳ thi này. Nói chung là… từ cấp một thì em coi việc mày mò câu lệnh, làm ra sản phẩm bằng Scratch như là một cái thú vui của em thôi. Em không nghĩ là Tin học nó sẽ là một cái con đường mà mình theo đuổi đến tận bây giờ. Và đến hôm nay khi mà em đã đạt được rất nhiều thành tích thì em cảm thấy bản thân muốn tìm hiểu sâu hơn nữa, không phải là chỉ về CP* mà còn nhiều góc khác của môn Tin học như là AI, rồi HTML, v.v… ạ.
*Ghi chú của biên tập: CP là viết tắt của Competitive Programming, tức Lập trình thi đấu, là nội dung của các kỳ thi Olympic, Học sinh giỏi,... môn Tin học.
Thời gian ấy em có sử dụng máy tính ở trường trong giờ ra chơi, em có được thầy cô nào phát hiện ra khả năng tin học của em và đồng hành với em không?
Có ạ. Hồi đó thì cô Nghĩa là cô dạy Tin cấp 1 của em đã phát hiện ra em, và lúc đó thì cô cảm thấy em có tiềm năng, thế là cho em vào đội tuyển luôn.
Lúc bấy giờ là đội tuyển của em có bao nhiêu người và hình thức học như thế nào?
Đội tuyển thì em nhớ khoảng 4-5 người. Lúc đó thì… ban đầu thì, nếu em nhớ không nhầm thì cô cho em học mấy cái câu lệnh của Word. Mà thực ra thì lúc đó em cũng không biết để làm gì, và tụi em cũng được học Scratch một cách bài bản. Chủ yếu là cô sẽ dạy và đưa đề để tụi em làm, và sau đó tụi em sẽ gửi lại bài cho cô qua Gmail.
Về hình thức chấm điểm sẽ là cô nhận bài của tụi em và tụi em sẽ nhận được điểm qua email của cô hay sao?
Cô sẽ chấm bài và đưa ra những lời khuyên cho em xem là có ổn không ạ.
Vậy cô sẽ tổ chức một buổi sửa bài cho các bạn, hay là chỉ đơn giản là cô nhận xét về bài làm của em?
Dạ không ạ, thời gian đó thì gần như là cái việc mà em mày mò đa số là cái việc mà em sẽ làm khi em theo đuổi môn Tin ạ. Tức là từ cấp 1 thì em đã bắt đầu mày mò tất cả các cái câu lệnh đấy, và em làm ra những cái sản phẩm gọi là "ngẫu hứng" của em, trong đó có làm ra những cái trò chơi kiểu… vớ va vớ vẩn ấy ạ. Nhưng mà kiểu, những cái trò chơi đó em làm khá là nhanh, kiểu 1-2 ngày thì em làm ra một cái sản phẩm rồi. Lâu lâu nếu mà em cảm thấy là nó hay thì em sẽ gửi cho cô.
Tua đến lúc mà em lên cấp hai thì việc học Tin của em bắt đầu thay đổi như thế nào? Đấy có phải là giai đoạn mà em cảm thấy mình tiến bộ nhất không?
Cái thay đổi nhiều nhất đối với em thì chắc là phải chuyển ngôn ngữ từ Scratch sang C++. Tất nhiên là cái việc viết những dòng lệnh trong C++ thì nó khó hơn rất nhiều so với việc mà mình kéo thả những cái câu lệnh có sẵn. Về sau thì mình cũng cần phải cài đặt các cái chương trình phức tạp hơn rất nhiều chứ không phải là mình chỉ kéo thả xong rồi nhìn chương trình một cách dễ dàng. Thì C++ nó phức tạp hơn ở chỗ là các cái câu lệnh nó không còn đơn giản như Scratch nữa, mình phải nhìn kỹ để mình biết là mình sai ở đâu để mình sửa lỗi. Thì đó là một cái giai đoạn mà em khá là khó khăn, khi mà em phải làm quen với ngôn ngữ mới, nhưng mà về sau thì em cũng đã làm quen được. Em vẫn còn nhớ cái thời mà em đã bị bug quên dấu chấm phẩy ở đầu ở cuối câu lệnh rất nhiều, nhưng mà đến bây giờ thì em không còn mắc phải lỗi đó nữa.
Ở thời điểm đấy ngoài thích môn Tin ra thì em còn thích môn học nào nữa không?
Chắc chắn là môn Toán ạ, tại vì môn Toán là cái môn mà em gọi là giỏi nhất. Em hồi cấp 1 thì đã từng nằm trong đội tuyển thi Violympic Toán, nhưng mà lúc đấy thì kiểu chỉ thi cho vui thôi. Em thì lúc nào thi Toán cũng đạt được điểm rất cao. Nhưng mà có một lần em đạt điểm khá là tệ, đó chính là khi em lên lớp 6. Lúc đó là lần đầu tiên phải trả bài và em lại quên học bài, thế nên là phải xin gỡ điểm. Cuối cùng là em được con 7. Và tiếp theo thì em đã tham gia các cái kỳ thi Học sinh giỏi Toán và đạt được giải Nhất cấp huyện, giải Nhì cấp tỉnh. Có một cái sự thật mà em muốn kể ở đây là… em đã lựa chọn Toán là nguyện vọng 1 khi đăng ký tuyển sinh vào chuyên Thăng Long, tức là hồi đó em để Tin là nguyện vọng 2 chứ không phải nguyện vọng 1. Nhưng mà vì nhiều lý do nên là em quyết định không theo toán nữa, và em đã phải cân nhắc là làm sao để rớt Toán. Lúc ấy thì kiểu…, nếu mà giả sử mình bỏ thi thì cũng được thôi! Nhưng mà em gọi là cũng hơi sợ tại vì làm thế này thì không hay lắm. Thế nên là em lại nhớ đến một cái phong cách làm bài trên Codeforces của rainboy. rainboy thì thường hay chỉ làm từ cuối về đầu, nên là khi mà thi Toán chuyên em chỉ làm ba câu cuối và đạt 3.5/20 điểm. Và kiểu này thì chắc chắn là rớt, tại vì điểm liệt của môn Toán chuyên là 4/20.
Vậy nên là em sử dụng điểm đấy để xét tuyển vào môn Tin?
Dạ vâng. Tức là em cố tình để rớt Toán, và môn Tin thì gần như là đề khá là dễ. Thế nên là em dễ dàng đạt được nguyện vọng 2.
Hồi cấp 2 em có đi thi đội tuyển, có bao giờ em cảm thấy mình đi nhanh hơn các bạn nhưng mà nó vô hình tạo thành một cái sự căng thẳng trong em không?
Nếu mà tính đến thời điểm cấp 2 thì gần như em chưa hề có những cái áp lực này. Lúc đó thì em vẫn còn đang làm quen với bộ môn lập trình thi đấu chứ không phải là làm Scratch nữa, giống như kiểu là em vẫn còn cái sự đam mê mày mò của em. Bản thân em thì lúc đó coi môn Tin như một cái môn mà em thật sự muốn chinh phục và em muốn đi nhanh, đi xa hơn nữa.
Trong thời gian đấy thì phong độ cao nhất của em tính theo rating thì em đạt rating bao nhiêu khi mà em chưa lên cấp 3, tức là em chưa thi lớp 10?
Khi mà em chưa lên lớp 10 thì… lúc đó em được giới thiệu Codeforces và em đã bắt đầu làm trên nền tảng đó. Hồi đó thì em làm bài trên Codeforces bằng tài khoản danghuyhau (bây giờ đã đổi tên thành ~i\_love\_huyhau6a2~), và em không biết là em căn kiểu gì mà em lên được đúng rating 2100 luôn. Có một contest Edu em đã AC 5 bài, đáng ra em đã lên M nhưng sau đó đã bị hack nên em phải làm thêm một contest nữa.
Đấy là một rating khá là cao đối với các bạn chưa lên cấp 3. Hiện tại ngoài luyện tập trên những cái nền tảng như là Codeforces thì em còn luyện trên những cái OJ nào nữa không? Ví dụ như những OJ của Nhật, Indonesia, Trung Quốc,...
Em thì không tìm hiểu nhiều về các cái nền tảng. Đa số thì em sẽ chỉ làm một số những cái nền tảng mà quen thuộc thôi. Khi mà em mới học cấp 2 thì em luyện các cái trang như Vinh Dinh Coder với LQDOJ nói chung rất là nhiều, kể cả những giờ học online*. Hồi đó thì em hay chơi cái trò là vừa chép bài xong rồi lại tranh thủ, gọi là mở cam nhưng mà kiểu mình vẫn dùng màn hình thứ hai để ngồi làm bài ấy ạ, để kiếm bài. Về sau thì em luyện thêm các cái trang khác như VNOJ, thì cái này thông qua các cái contest của Bedao với lại VNOI Cup; sau đó là oj.uz, CSES, MarisaOJ, ClueOJ,... nói chung là rất nhiều nền tảng. Với em thì em cũng không phải là một người thích thay đổi môi trường làm bài quá nhiều ấy ạ, cho nên là em nghĩ em sẽ tìm khá là ít trang nền tảng so với mọi người. Với em thì cái nền tảng nào nó cũng sẽ có cái bài hay và chất lượng của mình thôi, kể cả CSES cũng vậy, đa số bài thì em thấy nói chung cũng có thể là cơ bản, nhưng mà có một số bài thì em lại thấy khá là hay và em học được một số điều khi mà em làm những bài đó. Nói chung là… theo em thì tùy vào nhu cầu cá nhân thì mọi người nên chọn cho mình một cái nền tảng phù hợp để làm bài trên đó, hoặc là mọi người có thể cân nhắc làm trên nhiều nền tảng cùng lúc cũng được. Với các thuật toán mới hay lý thuyết cần học thì em sử dụng các nguồn tham khảo phổ thông như USACO, VNOI Wiki, các blog trên Codeforces, đặc biệt là blog này em thường xuyên tra cứu để tìm các dạng bài với thuật toán liên quan, tuy vậy em cũng không khuyến khích mọi người làm hết bài trong đó vì có rất nhiều thuật toán ảo và gần như không ai sử dụng cả, với em thì em coi nó như 1 trong những nguồn để kiếm bài với thuật toán liên quan khi em muốn học thuật toán cụ thể nào đó.
*Ghi chú của biên tập: Thời điểm mà bạn Huy Hậu đề cập đến là lúc đại dịch COVID-19 bùng phát. Tất cả các hoạt động giáo dục trên nước ta đều thực hiện qua các nền tảng trực tuyến.
Theo em thì nền tảng nào em đánh giá là có các bài tập chất lượng nhất?
Cái này thì em cũng chưa đánh giá được ạ, nhưng mà em thì có một thời em cày Codeforces khá là nhiều. Em cày nói chung là phải nghìn bài, và em thấy bài Codeforces thì nói chung là cũng khá là ngẫu nhiên. Có bài thì hay, có bài thì dở, có bài thì gọi là đánh giá theo đúng cái rating của bọn nó. Nhưng mà có những cái bài kiểu nó lại bị đánh giá cao quá hoặc là thấp quá. Ví dụ như là có một cái bài mà em nhớ là bài H của 1 round Div.1+2, nhưng mà ai đó lại lỡ đánh là 2000 (rating) Codeforces, thì cái đấy nó không ổn lắm. Nói chung là khi mình làm bài thì mình vẫn phải chọn lọc bài để mình làm.
Và Codeforces cũng là một trong những nơi có những cái bài toán mà kiểu cơ bản về một số thuật toán, chẳng hạn như là Mo's algorithm, hay là một số trick về gì đó, cái này thì em không nhớ rõ nữa, kiểu siêu nhiều ấy ạ.
Em sẽ ưa luyện tập trên những cái OJ ở trong nước, Codeforces và CSES và ngoài ra em không có luyện ở những trang như USACO hay những nền tảng khác của nước ngoài nữa đúng không?
Em có luyện thêm ~oj.uz~ nữa ạ, tại vì ~oj.uz~ là một trong những nguồn có những đề thi chính thức của nước ngoài nữa. Hiện tại thì em thấy là VNOJ cũng có đề nước ngoài khá là nhiều, có thể thì em sẽ cân nhắc làm nó trong tương lai. Và CSES thì em thấy đa số bài cơ bản, nhưng mà có những bài em lại thấy khá là hay. Ví dụ như có một bài tồn tại một cái trick mà gần như đã làm cho em phải suy nghĩ vắt óc hơn một ngày liền, và cuối cùng thì em phải đọc solution. (cười)
Tính ở thời điểm hiện tại, khi nhìn lại hành trình vừa qua của em thì em thấy thành tích nào là cột mốc khiến em đáng nhớ nhất? Tức là đấy không nhất thiết phải là thành tích cao nhất của em nhưng mà nó là một cái thành tích khiến em thay đổi bản thân mình?
Theo em thì có thể là Tin học trẻ, tại vì Tin học trẻ em đã thi 8 năm, từ lớp 3 đến lớp 10, và em đã được đi rất nhiều nơi, em được trải nghiệm kỳ thi Tin học trẻ ở rất nhiều nơi khác nhau, và em cảm thấy nó là một phần trong cái hành trình trưởng thành của em ấy, kiểu Tin học trẻ nó đồng hành với em từ năm lớp 3 đến lớp 10, từ khi mà em còn mới học Scratch đến thời điểm mà em bước chân vào lập trình thi đấu. Và đến khi em trưởng thành rồi thì nó vẫn đang đồng hành với em, có lẽ là nó sẽ đồng hành với em đến hết cấp 3 luôn. Và một cái cột mốc nữa mà em muốn nhắc đến là Huy chương Bạc IOI 2025. Khi mà em đứng trước cái sân khấu và em được vinh dự đeo huy chương, em cảm thấy như là mình đã trưởng thành hơn rất nhiều so với cái thời điểm mà em chập chững. Khi mà em mới bắt đầu Scratch thì em không nghĩ là mọi thứ nó sẽ… Tức là trước khi mà thi APIO em còn không nghĩ là mình sẽ được trở thành một thành viên của đội tuyển IOI cơ. Nhưng mà khi mà em đã đạt được thành tích như vậy thì em cảm thấy bản thân mình đã trưởng thành hơn nhiều, và những cái nỗ lực của mình đã là xứng đáng. Đến bây giờ thì em vẫn còn khá là hoài niệm cái thời điểm mà em học chung với đội tuyển APIO và IOI trong năm 2025. Đó là một cái khoảng thời gian mà tụi em đã trò chuyện tâm sự với nhau rất nhiều, rồi cùng nhau động viên để tiếp tục, và còn rất nhiều cái khoảnh khắc vui vẻ nữa mà em sẽ không thể kể hết được. Và có lẽ cái khoảnh khắc này thì em sẽ không bao giờ quên.
Như em đã nói là em được tham gia rất là nhiều kỳ thi, và khi bước vào những cái kỳ thi lớn thì điều mà em cảm thấy khó khăn khi đối mặt nhất thì thường là những cái bài toán hay là những cái áp lực về tâm lý?
Ở nhà em luyện bài thì kiểu chỉ là làm một phát AC* luôn, thế nên gọi là kiểu này khá là lạ. Tại vì bình thường thì mọi người sẽ luyện chiến thuật phòng thi nhưng mà em chỉ áp dụng chiến thuật khi mà em trong phòng thi thôi. Trong phòng thi thì nói chung em làm bài rất là nghiêm túc, em phân bổ thời gian, chiến lược thi rất rõ ràng. Ở trong kỳ thi vòng hai (TST) gần nhất thì nói chung em thấy chiến thuật em khá là ổn khi mà em cắn hết tất cả các bài xong rồi sau đó em mới quay lại để kiếm điểm và làm những cái subtask** quan trọng. Nhưng mà… theo em thì áp lực tâm lý mới là cái mà gọi là khó nhất khi mà tham gia bất kỳ kỳ thi nào, vì cái việc mà mình làm bài trong phòng thi nó rất là khác. Trong phòng thi thì có thể diễn ra nhiều thứ mà không thể lường trước được, hoặc là thêm vào đó thì mình cũng có áp lực thời gian, áp lực phòng thi, rồi giám thị, tùm lum tà la nữa. Em thì trước khi thi vài ngày và vào trong phòng thi thì mình nên giữ cho mình một cái đầu lạnh và tỉnh táo, để khi mà vào phòng thi mình sẽ đạt được một cái performance tốt nhất có thể. Vì thế trước khi thi thì em sẽ không làm bài quá nhiều, và đa số gọi là chỉ chơi thôi để mình refresh lại cái não của mình. Trong phòng thi thì em sẽ cố tập trung hoàn toàn vào bài toán, không để xao nhãng bởi những thứ xung quanh hay suy nghĩ vớ vẩn như là hôm nay mình ăn gì, tùm lum tà la, v.v… Thêm vào đó thì em có một cái nguyên tắc mà em áp dụng vẫn hiệu quả đến tận bây giờ, nói chung là em sẽ cố mà để không quá coi trọng về cái kết quả của mình ý. Nếu mà mình để ý kỹ quá thì có khi mình sẽ bị áp lực tâm lý. Có thể trước giờ thi luôn, kiểu tự nhiên mình nghĩ đến việc là ngày mai mình thi mình choke thì sao, thì lúc đó nhiều khi tâm lý mình lại không vững ngay từ khi mình bắt đầu luôn rồi. Thế nên là cá nhân em nghĩ thì cái thứ mà em mạnh nhất không phải là về kiến thức logic hay là về cái logic suy nghĩ của em, mà em cảm thấy em mạnh nhất đó chính là một cái tâm lý vững vàng trong phòng thi.
*Ghi chú của biên tập: AC là viết tắt của Accepted, là kết quả trả về của các trang chấm bài online khi lập trình viên đưa ra lời giải xử lý được toàn bộ testcases của một bài toán.
**Ghi chú của biên tập: Subtask là cách gọi một ý nhỏ trong một bài tập lập trình thi đấu, thường các subtask có giới hạn nhỏ hơn, ràng buộc nhiều hơn đề bài gốc để thí sinh dành điểm thành phần nếu không thể đưa ra lời giải trọn vẹn cho bài toán.
Theo anh biết là em cũng có đạt được thành tích là thủ khoa HSGQG đúng không? Anh được biết là kỳ thi VOI nói chung là một cái kỳ thi rất là nặng về tâm lý, tức là nó là một kỳ thi chấm offline, cho nên là mọi người cần phải phân bố thời gian của mỗi bài nó thật hợp lý để kiếm được số điểm tối ưu nhất. Thì trong quãng thời gian đấy em thi VOI thì làm sao để em có thể đạt được một cái phong độ cao đến như vậy? Và khi đi thi thì em đã suy nghĩ những gì, chiến thuật của em ra sao?
Như em nói thì nói chung là em vẫn như cũ thôi, tức là kiểu cái cách của em nó vẫn áp dụng đến tận bây giờ, đó là em luôn giữ cho mình một cái đầu lạnh. Trong phòng thi nói chung là em áp dụng chiến thuật ngày đầu tiên thì em AC bài 1, một cái bài gọi là khá là dễ, kiểu một số bạn mà mới học, mới theo đội tuyển quốc gia cũng có thể làm được bài này, theo em cảm nhận là như thế. Bài 2 thì em đã làm gần như gọi là chỉ còn subtask cuối thôi. Sau đó thì bài 2 em cảm giác em có thể full được, nhưng mà lúc đó em lại chỉ dám làm đến subtask gần cuối, và em dành một tiếng còn lại cho bài 3. Bài 3 thì là một cái bài khá là khó về quy hoạch động chữ số. Lúc đó thì em đã dành ra hơn 1 tiếng và em chỉ làm mỗi subtask 1 thôi. Thế nên là ngày 1 em khá là tiếc tại vì em không làm full bài 2 trong ngày 1. Về ngày 2 thì em gọi là chiến thuật em khá là ảo, khi mà em all-in* hai bài là bài 4 và bài 5. Bài 6 thì em gần như không đọc đề luôn. Tức là bài 4, bài 5 em đầu tư rất là kỹ. Bài 4 thì em gọi là nghĩ một cái ý tưởng full luôn. Còn bài 5, thì em là một trong những người mà kiểu khá là tự tin trong cái cấu trúc dữ liệu, thế nên là em làm gần hết tất cả các subtask, chỉ chừa lại subtask cuối. Em dành 2 tiếng 45 / 3 tiếng để làm bài 4 với bài 5 rồi, thế nên là bài 6 em chỉ còn 15 phút và em phải cài subtask 1 trong thời gian đó. Nhưng mà lúc đó thì gần như gọi là hoảng quá, thế nên là em cài bug cái subtask đó. Về sau thì em có coi mọi người thảo luận, thì cái ý tưởng bài 4 của em là chặt tam phân. Mọi người cứ bảo là sai, nhưng mà lúc đó em cũng khá là hoảng, kiểu "chết lỡ đâu mình sai thì sao?" Nhưng mà kiểu em đã sinh test khá là kỹ cho bài đó, với lại em có đem bài của em đi chấm thử ở rất nhiều nơi, chẳng hạn như là chấm chỗ Trịnh Hữu Gia Phúc, rồi chỗ của thầy Phương, tùm lum tà la, kiểu em đều đạt được điểm tối đa, thế nên là em cũng không còn bị sợ như trước nữa. Và cái mà em bất ngờ nhất, hồi đó thì em chỉ suy nghĩ là mong mình sẽ vào được đội tuyển thi vòng hai thôi. Nhưng mà cái mà em bất ngờ nhất là em lại đạt được thủ khoa năm đó. Đó là một cái điều mà em khá là sốc tại vì em mới chỉ lớp 10 thôi và em không có suy nghĩ kiểu là mình sẽ đạt được thủ khoa, kiểu năm lớp 10 nên là mình thi cho vui thôi. Mình thi để có kinh nghiệm và năm sau mình thi tiếp thôi ạ.
*Ghi chú của biên tập: all-in tức là được ăn cả ngã về không, Huy Hậu muốn nói bạn đã chơi tất tay trong hai bài tập 4 và 5.
Đúng là VOI là một kỳ thi rất là nặng về tâm lý, đề thi có nhiều subtasks và cần cài đặt rất là nhiều. Em cũng nói là lúc còn 15 phút cuối giờ, khi cài bài 6 thì em cũng khá là hoảng. Anh không biết là trước thời gian đấy, khi em làm bài 4 và bài 5 em cũng sinh test rất kỹ rồi mới qua bài 6 đúng không?
Dạ vâng. Mỗi bài thì em đều dành tầm 1 tiếng 20 đến 1 tiếng 30 phút để em làm, trong đó chắc chắn sẽ có khâu sinh test.
Thông thường thì sẽ tốn khoảng bao nhiêu thời gian để em nghĩ một bài mà sau khoảng thời gian đó thì sẽ quyết định cài đặt luôn?
Theo em thì cũng tùy ấy ạ. Có bài thì em nhìn phát nghĩ ra ngay, bởi vì có thể có một cái ý tưởng tương tự mà em đã làm qua rồi. Có bài thì em sẽ mất rất nhiều thời gian, có thể là do đầu của em bị choke hay gì đấy. Nói chung cũng tùy vào độ khó của bài và tùy vào não của em hoạt động thế nào nữa, theo em là như thế. Kiểu não em hoạt động rất là random, có lúc thì nghĩ ra ngay, có lúc thì não em hoạt động chậm,...
Bản thân anh thấy em đi thi rất là nhiều cuộc thi và khá nhiều cuộc thi em thủ khoa hoặc vô địch luôn. Ví dụ như riêng trong 2025 thì em vừa thủ khoa VOI vừa vô địch VNOI Cup. Thậm chí mới nhất là em vô địch cả Olympic 30/4 đúng không?
Dạ vâng ạ.
Khi mà đi thi thì em có hay đặt mục tiêu cho mình làm em phải thủ khoa hay gì không? Hay là em cứ thi hết sức mình thôi chứ em không quan tâm đến kết quả lắm.
Em thì không bao giờ tự đặt ra một cái mục tiêu cụ thể cho mình trước khi thi. Nhiều lúc thì em chỉ ngồi suy nghĩ là mình có thể, mình có thể thôi, sẽ đạt được những thành tích thế này thế này. Chứ em sẽ không bao giờ quá suy nghĩ là mình phải đạt được cái mục tiêu này. Nhiều lúc mà mình cứ phải đạt được một cái mục tiêu nào đó thì nó sẽ tạo ra một cái áp lực tâm lý, nên đi thi thì tâm lý của mình sẽ không ổn định. Như em nói rồi, cái tâm lý là một cái mình cần phải giữ vững trong phòng thi. Nếu không giữ vững được thì mình sẽ bị gãy ngay. Nói chung là em sẽ không đặt ra mục tiêu cho mình trước khi thi mà em sẽ tập trung làm hết sức và làm rất kỹ.
Khi mà em đi thi, có bao giờ em mà em dành thời gian nghĩ một bài rất là nhiều, nhưng mà đến cuối cùng thì chỉ ra được một lời giải chỉ ăn được subtask đầu tiên thôi chẳng hạn không? Vì em đã dành quá nhiều thời gian cho bài đấy nhưng kết quả đạt được không tối ưu, trong những trường hợp đấy thì em sẽ xử lý như thế nào?
Hình như lần duy nhất em bị dính phải trường hợp này là bài 3 VOI năm 2025 mà thôi. Nhưng có một cái lần mà em thi Olympic Sinh viên, lúc đó em định cài bài 2 rồi, nhưng mà em bug quá, xong rồi em chuyển sang bài 3. Bài 3 là một bài interactive, em nhìn phát thì em ra ngay ý tưởng, tại vì cái ý tưởng đó tựa tựa như một cái bài thi IOI 2025 ngày 0. Thế nên là em cài luôn. Và em thật sự rất là bug! Lúc đó tầm 2 tiếng rưỡi, em cảm thấy là chết rồi, cứ như thế này thì mình chết mất. Nhưng về sau thì em cảm thấy là thôi, mình thi cho vui thôi nên em không quan tâm kết quả nữa. Thế nên em vẫn đâm đầu vào bài đấy, và em thực sự là người duy nhất đạt được 100 điểm* trong bài đó.
*Ghi chú của biên tập: Kỳ thi IOI có 2 ngày thi và một ngày luyện tập/thử máy gọi là ngày 0.
**Ghi chú của biên tập: 100 điểm là số điểm tuyệt đối của một bài tập trong kỳ thi được đề cập.
Giống như là, thành công chỉ cách mình một bước thôi đúng không? Nếu như lúc đấy em từ bỏ thì chưa chắc em là người duy nhất đạt full điểm bài đấy.
Có khi là em sẽ chỉ được mấy điểm thôi. Kiểu lúc đó suy nghĩ của em là bây giờ mình không đâm đầu tiếp thì có khi kết quả của em sẽ còn tệ hơn. Tại vì em mới chỉ dành thời gian cho bài 2 và bài 3 thôi. Còn bài 4 thì gần như là em không có hứng làm, vì đó là một dạng mà em không thích lắm là output only. Còn bài 1 năm đấy thì các subtask đầu khá là dễ, thế nên là em để dành đến cuối mới làm. Nhưng mà lúc đó thì em gần như là chơi all-in, thế nên là em tất tay luôn bài 3 cho đến khi tầm 3 tiếng mấy thì em AC. Có một cái đoạn cuối em định xử lý bài 2 mà em bug quá thế nên là em vẫn 0 điểm bài đó.
Anh thấy em có bảo em là một người khá mạnh về cấu trúc dữ liệu. Em cảm thấy ngoài thế mạnh của em về CTDL ra thì em còn mạnh về những cái dạng bài nào nữa không?
Em không có một cảm giác là em mạnh về cái gì. Mà em cảm giác là khi mà em cài đặt thì em sẽ cài khá là chắc tay. Có những bài thì em có ý tưởng là em sẽ chỉ cài tầm vài lần là nó sẽ AC thôi. Nhưng mà cũng có lúc thì em sẽ dành rất nhiều thời gian để em chày cối với cái bài đó, vì bug rất là nhiều.
Anh thấy em là một người đi thi rất là nhiều, mật độ kỳ thi rất là dày đặc. Thông thường, giữa mỗi kỳ thi em có một thời gian nào đấy để em nghỉ ngơi, em làm chuyện khác không phải CP nữa không? Hay sau một kỳ thi nào đấy thì em bắt đầu luyện tập cho kỳ thi tiếp theo luôn?
Khi tham gia các kỳ thi có phần "dễ chịu" thì em cũng sẽ cứ chill chill thôi. Có một cái giai đoạn mà em tạm không làm CP nữa là giai đoạn mà em thi xong IOI, em phải về lớp học. Khi đó thì thầy hiệu trưởng bắt em ở lại lớp để học bình thường. Lúc đó thì em cũng khá là cay, tại vì em thấy các tỉnh khác thì người ta sẽ bắt đầu đầu tư cho mình luôn để chuẩn bị thi vòng 2 (vòng chọn đội tuyển quốc gia năm sau, do các thí sinh tham dự APIO trở lên được đặt cách vòng 1 là kì thi chọn học sinh giỏi quốc gia) luôn, kiểu xuất phát sớm, vì em có thể thi vòng 2 mà không cần thi vòng 1. Nhưng càng về sau thì em lại càng thấy đó không phải một quyết định tệ. Tại vì khi mà em quay lại lớp thì em có một cảm giác là em trở về lại những năm cấp 2, em cảm giác em được học bình thường như xưa và em đã làm quen được một số bạn trong lớp và nói chung em khá là thân. Ngoài ra thì em được trải nghiệm những thứ mới, ví dụ như trong khoảng thời gian đó thì em có trải nghiệm làm việc nhóm vài lần. Hồi cấp 2 thì nói chung em chỉ làm cái trải nghiệm đó 2, 3 lần mà thôi. Ở đây khi mà em lên một ngôi trường chuyên thì phải làm việc nhóm rất nhiều lần. Trong cái học kỳ đó thì chắc em phải làm việc nhóm 4 đến 5 lần rồi. Và còn một trải nghiệm nữa là quay video môn Trải nghiệm Hướng nghiệp, đó là một trải nghiệm khá là thú vị đối với em. Đến bây giờ thì em cảm thấy là thầy hiệu trưởng đã đưa ra một quyết định rất là đúng đắn cho em ạ.
Trong khoảng thời gian đấy thì em có những sở thích nào bên ngoài việc học không? Chơi thế nào hay làm việc gì đấy ngoài giờ?
Em có những sở thích khá là kì. Ví dụ nha, em có một sở thích là chat chit, em có thể ngồi nói chuyện trên Messenger hay Discord mấy tiếng liền. Có cái lần mà em nói chuyện phải tầm 3 đến 4 tiếng, trong lúc mà em đang làm bài. Nhiều lúc mà khi mình đã vào cái guồng của mình rồi thì mình sẽ gọi là theo nó rất là lâu, đến khi mà mình không theo được nữa thì thôi. Và em có chơi game nữa. Trò mà em hay chơi nhất thì là The Battle Cats, cái trò này thì em cũng không biết là có ai chơi hay không, em chỉ thấy có thằng bạn trong lớp em chơi mà thôi. Em cũng khá tò mò xem có ai cũng đã chơi trò này hay chưa.
Một ngày đi học của em, ôn luyện đội tuyển, thì em sẽ dành bao nhiêu thời gian cho môn Tin học và bao nhiêu thời gian cho hoạt động khác?
Như em thì khá là cảm tính, nên em chỉ làm việc khi em thật sự sẵn sàng. Tức là có lúc thì em chán quá em không code nữa, có lúc thì em thấy cảm giác là hôm nay mình phải làm bài nhiều, thì em sẽ làm bài. Nhưng mà đã làm việc thì nói chung là em sẽ làm việc khá là nghiêm túc, em sẽ không chịu nghỉ đến khi em đã làm xong và em không còn làm tiếp được nữa. Nói chung là cách luyện của em thì không năng suất lắm đâu, tại vì, mỗi người một cách luyện khác nhau mà. Em thì cũng không phải là một người thích đọc solution khi mà luyện tập. Nên là bình thường em sẽ không đọc solution, cảm thấy bị kẹt thì em mới mở ra để đọc. Hoặc là em có một cái kiểu là khi đã mở solution ra thì em không làm bài đó nữa, em chuyển qua bài khác luôn. Em thì nói chung là không có một cái lịch học cố định, nhưng mà em sẽ hoạt động nhiều vào buổi sáng và buổi tối. Buổi chiều thì đa số là em ngủ, tại vì buổi tối phải thức đêm, đến tầm 1-2 giờ sáng gì đấy. Cách luyện tập thì em sẽ kiếm bài và làm bài ngẫu nhiên trên các trang web khi mà gặp dạng lạ thì có khả năng em sẽ cân nhắc em học. Em thì không thích học mấy cái dạng lạ cho lắm, nhiều lúc em cảm giác là học dạng lạ thì có khi là mình chỉ dùng được 1-2 lần và có khi là sẽ không dùng nó nữa. Thế nên là em cảm thấy cần học nó thì em mới bắt đầu học nó mà thôi. Về sau thì em nghĩ là em vẫn sẽ học thêm một số dạng nữa, nhưng mà em chỉ sẽ lưu nó dưới dạng template mà thôi. Để trong những trường hợp khẩn cấp thì em mới cần dùng nó.
Về kỳ thi APIO sắp tới, em có đặt target cho mình năm nay là em vào APIO hoặc IOI em đạt huy chương gì hay không?
Hiện tại thì em nghĩ là em vẫn sẽ như cũ, em sẽ không đặt mục tiêu gì hết. Em muốn tạo ra một sự thoải mái cho bản thân em trước khi thi và sau khi thi. Nhưng mà dạo này thì em cảm thấy là mình đang bị chững lại ấy, nhiều lúc em cảm thấy là không biết là mình có đạt được một cái thành tích tốt hơn không. Tại vì năm ngoái em đã được HCB IOI rồi, nên là năm nay mọi người sẽ đặt kỳ vọng ở em nhiều hơn, mọi người bảo em là mong em HCV. Nhưng mà em cảm giác nó cứ như một cái áp lực vô hình với em ấy. Em bây giờ khá là sợ cái việc choke trong giờ thi. Nhiều lúc mà em cảm giác là nếu mình làm bài được kết quả không như kỳ vọng thì mọi người sẽ nhìn và nhận xét em. Ngày xưa khi mà em còn theo đuổi Tin học như một cái thú vui thì em không hề có những cái áp lực trên. Nhưng từ khi em lên cấp 3, khi mà em đã thay đổi nhiều rồi, em cảm thấy là bây giờ thì em rất là sợ trong cái việc mà mình vẫn có một cái áp lực là mình phải làm bài thật là tốt, phải đúng kỳ vọng như mọi người xung quanh. Nhưng với bản thân em thì gần như em không muốn đặt ra một cái mục tiêu nào đó cho mình trước khi thi. Vì mình tự đặt áp lực thì mình cũng sẽ khá là khó để mình làm bài ổn định.
Về tương lai, hết năm sau thì em sẽ cần phải chuẩn bị vào đại học. Em có mục tiêu vào trường đại học nào không? Em sẽ đi du học hay em sẽ chọn một trường ở trong nước?
Hiện tại thì em nghĩ là em có rất nhiều lựa chọn cho tương lai. Vì em nghĩ là em có thể ứng tuyển vào rất nhiều trường, nhưng mà hiện tại thì em chưa tìm hiểu kỹ về việc này đâu. Một trong những lựa chọn mà em thấy khá nhiều người đề xuất cho em là sang NUS. NUS là một trường đại học ở Singapore. Nếu mà vào trường này thì mình cũng sẽ có thể có nhiều cái trải nghiệm mới và môi trường mới. Trong tương lai thì em sẽ tìm hiểu kỹ hơn về những lựa chọn này.
À, em nhớ là hồi cấp 2, em đã từng trả lời phỏng vấn là em sẽ vào trường FPT. Lúc đó thì em gặp câu hỏi này thì em khá là khó khăn vì em chẳng biết gì hết, vì em cũng đâu biết trường đại học nào đâu. Cô của em cũng bảo là ước mơ cũng chỉ là ước mơ thôi, nói chung là mình cũng có thể thay đổi, thế nên là em vẫn quyết định là sẽ trả lời theo ý của cô là mình sẽ chọn vào trường FPT. Lúc đó có khi em còn không biết trường FPT là trường nào nhưng mà vẫn phải trả lời vì mình không biết trả lời gì hết *(cười).
*Ghi chú của biên tập: NUS là viết tắt của National University of Singapore, tức Đại học Quốc gia Singapore.
Về công việc hay ngành mà em theo đuổi, em nghĩ em sẽ theo ngành học về AI, hay là chỉ đơn thuần là khoa học máy tính và sẽ đi ra bên ngoài làm cho những tập đoàn, công ty?
Em thì muốn tìm hiểu sâu hơn về Tin học nên em nghĩ là có thể em sẽ theo AI, có thể sẽ làm những việc khác thay vì đơn thuần CP thôi. Lên đại học thì em vẫn sẽ tham gia ICPC, nói chung em sẽ không thể dành nhiều thời gian cho CP khi lên đại học, nhưng mà em vẫn sẽ tham gia ICPC. ICPC là một trong những kì thi mà có thể coi là một đỉnh cao cuối cùng mà em cần phải chinh phục được. Với cấp 3 thì ở Việt Nam có một bảng thi dành cho THPT, thì em đã chinh phục được, em đã đạt được top 1 ICPC Regional năm vừa rồi. Khi lên đại học thì em muốn đạt được đến đỉnh cao cao hơn nữa, có thể là ICPC World Finals luôn. Em nghĩ là việc có huy chương nó khá là xa vời với em, tại vì khi mình thi ICPC World Finals thì có rất nhiều đội mạnh đến từ các nước khác nhau. Những mà nói chung thì mình vẫn có thể ước mơ, mình vẫn có thể hy vọng chứ đúng không ạ?
Vậy với định hướng AI, em sẽ theo hướng nghiên cứu, tức là làm trong những phòng lab, viết nghiên cứu khoa học? Hay em sẽ theo hướng ứng dụng, đi làm.
Cái này khó quá em chưa tưởng tượng ra. Em chưa nghĩ đến luôn.
Sau này nếu có cơ hội sống và làm việc ở trong nước hay nước ngoài thì em sẽ lựa chọn ở đâu? Em muốn sống ở Việt Nam hay định cư ở nước ngoài hơn?
Em thì không thích sang nước ngoài định cư lắm, vì em sợ khi qua nước ngoài mình phải làm quen lại với nhiều người mới, và em sợ là khi mình ở đấy quá lâu thì mình sẽ cô đơn. Em thì khá thích ở Việt Nam, nói chung Việt Nam là nơi mình sinh ra và lớn lên, và em có rất nhiều người quen ở đây, em rất muốn giữ những mối quan hệ tốt với họ. Trong tương lai em cũng muốn cống hiến nhiều hơn cho nền Tin học nước nhà. Em khá là tò mò về Lập trình thi đấu trong tương lai nó sẽ thay đổi như thế nào và hiện tại thì em đã là một trong những thành viên của TNV VNOI, đây sẽ là một bước tiến quan trọng nếu em muốn tiếp tục cống hiến nhiều hơn trong tương lai ạ.
Em có bao giờ nghĩ đến việc đi dạy học không? Giống như các thầy rất là nổi tiếng như thầy Đông, thầy Hoàng hay như anh Hạnh hiện tại không?
Có ạ. Em cảm thấy việc dạy cũng là một việc khá là thú vị mà em muốn trải nghiệm. Em cảm giác là việc dạy học thì em thấy có rất nhiều anh khi mà lên đại học đã bắt đầu đi dạy rồi, thì em cũng tò mò về việc dạy học nó sẽ như thế nào. Có thể là em sẽ dạy cơ bản cho một số em, nhưng mà em nghĩ là em sẽ hợp hơn với việc dạy cho các bạn trong các đội tuyển quốc gia của các tỉnh.
Ở đội tuyển quốc gia, em học đội tuyển ở trường hay là đội tuyển quốc gia, thì có kỷ niệm nào mà em cảm thấy đáng nhớ không?
Kỷ niệm đáng nhớ thì nhiều quá ạ. Có một kỷ niệm em rất nhớ là trong phòng thi APIO 2025, lúc đó thì trong thời gian giữa giờ em khá là hoảng vì performance (phong độ làm bài) của mình rất là tệ và em chỉ còn hy vọng về việc kiếm điểm bài 3. Bài 1 thì em đã đạt được 78 điểm, và bài 2 thì em chỉ làm được subtask 12 điểm thôi, nên em cũng không còn hy vọng gì nữa. Lúc đó em làm rất nhiều cách, em cắn được subtask 3, 4, 5 nhưng lại không cắn được subtask 2. Về sau thì em khá là may mắn khi em vẫn làm được subtask đó, nhưng không chỉ subtask 2, nó còn vô tình làm cho em AC được cả bài. Trong khi chương trình của em rất là đơn giản. Thế nên lúc đó mới có một bài báo là chương trình chỉ có 4 dòng lệnh ấy ạ*. Nhưng mà cái 4 dòng lệnh đó là trong cái hàm chính của em thôi vì tổng độ dài thì cái code của em phải tận 17 dòng lận. Nói chung là em không dám hét, do có giám thị với lại có các anh thi nữa, lúc đó mà em hét lên thì mọi người sẽ sốc mất. Chỉ biết ngồi há hốc suốt 15 phút còn lại thôi. Tại vì em nghĩ là performance của em đang tệ nhưng mà lúc đó thì việc AC bài 3 đã cứu sống em. Kết quả là em được HCB APIO và đã trở thành một trong những thành viên của đội tuyển IOI 2025.
*Ghi chú của biên tập: Bạn đọc có thể tham khảo bài báo được Huy Hậu đề cập đến tại đây .
Bây giờ có thể quay lại thời điểm ban đầu em học môn Tin, em sẽ đưa ra lời khuyên gì cho chính em ở thời điểm đấy?
Với em thì em cũng không biết khuyên gì nữa (cười). Nhưng mà nói chung là em vẫn mong là bản thân vẫn sẽ giữ được cái nhiệt, giữ được cái đam mê của mình khi mà mình bắt đầu. Nói chung em sẽ khuyên mình không được bỏ cuộc và vẫn tiếp tục theo đuổi cái đam mê của mình.
Nếu em có cơ hội em được gửi lời nhắn của mình cho chính bản thân trong 5 năm sau, thì em sẽ nói điều gì?
Theo em thì em sẽ khá tò mò về bản thân mình trong những năm sau ạ. Có thể là em sẽ muốn tìm hiểu xem trong tương lai mình có còn hồn nhiên ngây thơ như trước hay không. Và em cũng không muốn spoil quá nhiều, nhiều lúc biết trước nhiều thứ quá thì cũng không hay. Em vẫn hy vọng bản thân mình trong tương lai thì vẫn sẽ còn giữ được cái lửa của bản thân mình như những ngày đầu em bắt đầu đến bây giờ và về sau nữa. Vì em cảm thấy là môn Tin là một bộ môn mà em cảm thấy là em sẽ theo nó suốt cuộc đời luôn.
Trong quá trình mà em gắn bó với môn Tin học như thế, em cũng bảo là em dành thời gian rất là nhiều để em chat. Em có những người bạn đồng hành nào không? Người bạn nào em cảm thấy rất là thân và giúp đỡ em nhiều trong việc học Tin?
Em có ạ. Nói chung là nhiều quá thì em cũng không thể nào kể được. Nhưng mà em có mấy câu chuyện thế này, thời điểm đầu tiên mà em được tiếp xúc với những người mà theo đuổi Tin học thì tức là thế này. Hồi cấp 2 lúc em mới bắt đầu học thì em hình như là kiểu chỉ làm bài một mình thôi. Gần như là em cũng không có ai để tâm sự chung ngoại trừ mấy anh trong đội tuyển học sinh giỏi. Thì lúc đó thì em được biết đến TLEOJ, đến bây giờ thì nó đã trở thành SQRTOJ rồi. Khi đó thì em đã tham gia một contest và top 1, sau đó thì em được anh Nguyễn Hữu Nhật Quang cho trở thành admin của TLEOJ, và bước ngoặt bắt đầu từ đây. Em đã được gặp và tiếp xúc với rất nhiều người qua Discord TLEOJ và có một cái kỷ niệm em thấy khá là đáng nhớ, đó là đợt em thi Olympic Miền Trung Tây Nguyên, đó là cái lần đầu tiên mà em thật sự là được gặp một số người quen và tiếp xúc trực tiếp với họ. Bởi vì khi mà mình chỉ nhắn tin qua chat thì mình cũng sẽ khá tò mò về cuộc sống của họ, và mình cũng muốn biết là họ ở ngoài trông như thế nào ấy ạ. Thời gian đó em cũng tham gia rất nhiều hoạt động với TLEOJ như là set bài cho các kì thi, sinh test cho các kì tuyển sinh một số tỉnh, test bài,... Và quan trọng nhất là em đã có thể trao đổi bài với những người chung đam mê với em, thay vì tự mình làm bài như trước. Thì đây cũng là một nơi đã cho em biết và làm quen được rất nhiều người, rất nhiều đàn anh đàn chị cũng có chung đam mê với em. Đến bây giờ thì vì định hướng của em nên là em không còn hoạt động ở trên SQRTOJ nữa và em đã rời khỏi SQRTOJ.
Thông thường khi học Tuyển, bên cạnh những người bạn đồng hành của em thì em còn người thầy nào đồng hành với em xuyên suốt không?
Dạ theo em thì là thầy Tuấn, thầy dạy Tin và là tổ trưởng khối Tin của trường em. Nói chung là thầy động viên em rất là nhiều. Thầy cũng hỗ trợ em rất nhiều trong một số chuyện, chẳng hạn như chuyện tiền bạc, khi mà em cũng không phải là một người quá dư dả nên là lần nào em đi thi thầy cũng cho em tiền hết. Nói chung là em cảm thấy khá là biết ơn vì thầy đã luôn giúp đỡ và đồng hành với em từ giai đoạn đầu em theo CP, và thầy cũng là người đã phát hiện ra em ngay từ cấp 2. Thầy là một trong những người đã hướng dẫn cho em về C++ cơ bản trong những năm em còn học lớp 6 và lớp 7. Về sau thì đa số là em sẽ tự làm bài nên em cũng không cần phải nhờ đến thầy nữa. Nhưng những gì mà thầy đã giúp đỡ em thì em vẫn còn rất biết ơn đến tận bây giờ. Về sau thì em hy vọng là em sẽ có thể trả ơn cho thầy.
Khi có những giai đoạn khi em làm bài và em bị bí ý tưởng, hoặc là em cảm thấy mệt, em cảm thấy mình không thể làm tiếp được nữa, thì thường em sẽ làm những gì để em có thể lấy lại được động lực tiếp tục đi tiếp trên cái con đường này?
Khi mà em gặp phải giai đoạn đấy thì một trong những giải pháp đơn giản nhất của em là mình chỉ không làm bài nữa thôi, và mình chơi cả ngày hôm đó. Nhiều lúc em có một cái cảm giác là, nếu giả sử mình đang ở trong một performance (phong độ) khá là tệ, và kiểu như mình bị burnout, thì nếu mà gặp phải những giai đoạn như thế này thì nhiều lúc mình tập trung mình cũng sẽ không đạt được hiệu quả mà mình mong muốn. Mình còn có thể gặp phải những hệ quả tệ hơn nữa, ví dụ như mình bị ảnh hưởng về mặt cảm xúc, rất nhiều thứ hệ quả sau đó nữa. Thế nên cái quyết định đơn giản nhất của em là sẽ lựa chọn nghỉ ngơi và sau đó quay lại tiếp tục luyện tập.
Về cái việc lấy lại cảm hứng, có bao giờ em dành thời gian để em nghe nhạc hay em xem phim gì không trong những thời gian rảnh? Nếu em nghe nhạc hay xem phim thì đấy sẽ là những thể loại nhạc gì hay bộ phim gì?
Em là một người khá là thích nghe nhạc và đa số nhạc em nghe là nhạc Việt ạ.
Đấy là những bài gì, ca sĩ nào?
Ca sĩ thì nói chung là nhiều lắm ạ, em có nghe những bài của Anh Trai Say Hi, Em Xinh Say Hi, rồi em có nghe qua những nghệ sĩ, để em nhớ đã nhiều quá em không nhớ nữa…
Còn phim thì sao?
Phim thì em cũng không gọi là "nghiện phim" nên là em cũng khá là lười để tìm phim để mà xem ạ.
Em có thích đọc truyện không?
Hồi cấp 1, cấp 2 thì ở nhà em có rất là nhiều truyện tranh, đa số là truyện Doraemon, Trạng Quỳnh rồi Trạng Tí. Thì nói chung hồi đó em khá là nghiện đọc truyện, ngày xưa thì em đọc truyện rất là nhiều, em đọc trong cả giờ ăn cơm luôn. Nhưng mà đến cấp 3 thì em cảm giác là em cũng chẳng còn thời gian để đọc truyện nữa, thế nên là em đem hết truyện hồi cấp 2 cho mọi người luôn rồi. Em còn nhớ là hồi cấp 1 em còn xem hoạt hình nữa, hồi đó em có xem Báo Hồng (Pink Panther), hồi đó em có xem một cái kênh hoạt hình nữa. Hồi đó là em phải trốn mẹ để xem, tại vì mẹ em cũng không thích việc em xem quá nhiều, thế nên là em phải trốn, canh lúc mẹ không có ở nhà để xem. Nhưng mà lên cấp 2 khi mà em không còn xem được cái kênh đó nữa thì em không còn xem hoạt hình luôn.
Em có thể chia sẻ đó là kênh gì không?
Kênh ANT, em nghe bảo là kênh đó chắc là bị xóa rồi, em nghĩ tại vì bây giờ mọi người cũng không xem TV nhiều như trước nữa, mọi người xem YouTube nhiều hơn.
Nếu có ước muốn được đi du lịch nước nào đấy thì em sẽ đi du lịch nước nào?
Em nghĩ là em sẽ muốn thử trải nghiệm Singapore, chắc cũng vì đó là nơi mà em muốn học, cụ thể là ở NUS ấy ạ. Nên em cũng muốn thử xem ở Singapore thì có gì hay, về văn hóa ở đó như thế nào.
Anh không nhớ là IOI năm ngoái mình đi nước nào? Em có thể chia sẻ được không?
Năm ngoái là mình đi ở Bolivia ạ. Bolivia là một cái nước mà cách mình nửa vòng trái đất ấy ạ. Khi mà tụi em đi là tụi em phải bay 3 chuyến, đi ở đâu em quên mất rồi, nói chung là mình phải bay 3 chuyến và có nghỉ giữa chừng. Sau đó mình phải đi thêm một đoạn khá là dài thì tụi em mới tới được cái chỗ để mà ở và thi ạ.
Em có kỷ niệm gì về hành trình đi IOI hồi đấy không? Ví dụ như em có kết được bạn nước ngoài nào không? Hay là em có câu chuyện nào đấy có thể chia sẻ về đoàn IOI nước mình không?
Em khá là dở tiếng Anh… à không, em không nghĩ là em dở tiếng Anh. Nhưng chỉ là đủ để đọc được một cái đề tiếng Anh thôi, và tiếng Anh giao tiếp của em thì em nghĩ là em không đủ thế nên gần như là em không giao tiếp với ai. Em thấy anh Lê Kiến Thành*, tiếng Anh của anh ấy khá là tốt nên anh giao lưu được với những anh ở Poland (Ba Lan). Mấy anh ở Poland em thấy khá là thân thiện.
Có một cái trải nghiệm em thấy khá là thú vị ở IOI đó là khoảnh khắc mà em bước vào trong phòng thi. Khi mà mình trải nghiệm đi thi ở nước bạn thì nó sẽ rất là khác. Phòng thi ở đây không phải là mình chia ra thành nhiều phòng thi khác nhau đâu, mà là mình sẽ thi ở một cái sân vận động luôn. Sân vận động đấy thì có rất là nhiều bàn và có tất cả các thí sinh ở đấy. Khi vào mình còn có thể mang đồ vào trong đó nữa. Có một anh mang cái tờ hình ảnh khá là thú vị và có anh mang cả poster vào trong đó nữa. Có cái nữa là em có thể giơ bảng lên, để làm một số thứ chẳng hạn như xin đồ ăn, xin chuối, xin sô-cô-la, xin nước hay xin đi vệ sinh,... Cái này là trải nghiệm lần đầu tiên. Ví dụ thi ở Việt Nam thì nếu mà mình muốn đi vệ sinh thì mình đơn giản là gọi giám thị thôi và xin giám thị là giám thị cho.
Và có một cái trải nghiệm nữa là em phải sửa Sublime Text, khi mà phần mềm mà em dùng từ cấp 2 đến giờ là DevC++ và em đã quá quen với nó rồi. Nhưng cái trang của IOI thì không có phần mềm DevC++. Trước khi tụi em thi thì tụi em phải học một cái đoạn Sublime Build và tụi em viết cho nó thì mới có thể cho cái Sublime Text dịch được cái chương trình và chạy trong suốt thời gian thi.
*Ghi chú của biên tập: Lê Kiến Thành cũng là thành viên của đội tuyển IOI 2025 và đạt HCV. Hiện tại, Thành đang là sinh viên năm nhất của Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
OK anh có biết cái đó. Môi trường thi IOI là Linux, cái giao diện nó rất là khác máy bình thường đúng không? Có ai hỗ trợ em về phần đó không? Có ai chỉ em về cái đấy hông?
Em được người anh trong đội tuyển IOI chỉ về việc phải làm phải làm Sublime Build. Trước khi thi thì mấy thầy sẽ cho em trước một cái môi trường giống máy tính trong phòng thi ấy ạ. Có rất nhiều phần mềm code trong đó nhưng bọn em thống nhất với nhau là sẽ dùng Sublime Text và học một cái đoạn Sublime Build trước khi thi ạ.
Em có hâm mộ một người nào đấy ở nước ngoài hoặc là ở Việt Nam không?
Về nước ngoài thì em không tìm hiểu kỹ, nhưng em nghĩ là em khá ấn tượng về anh errorgorn, anh errorgorn thì đã từng tham gia VNOI Cup vừa rồi và anh đạt thành tích rất là tốt*. Bên cạnh đó thì anh cũng tham gia rất nhiều hoạt động như là trên nền tảng Codeforces, anh cũng đạt được thành tích rất là cao trong kì thi IOI. Em nhớ là anh đã từng đạt được 1 HCB và 2 HCV.
Một người ở trong nước thì em thấy em khá là nể anh Thành, anh Thành thì em nhớ là anh không phải là một người kiểu học ngay từ đầu như em. Nhưng tư duy của anh Thành khá là tốt và theo như em nhớ thì anh lên lớp 10 mới bắt đầu học, nhưng anh đã đạt được các thành tích rất là cao, và lên lớp 12 thì anh ấy đạt được HCV IOI. Đó là một điều mà em thấy rất là nể phục và em nghĩ là em sẽ cần phải học hỏi nhiều nữa. Anh Thành có một cái mindset khá là hay mà em cũng muốn học hỏi thêm, đến bây giờ em vẫn thấy mindset của anh Thành khá là đáng nể và em nghĩ là có thể em sẽ học hỏi được thêm một số điều từ anh ấy.
*Ghi chú của biên tập: errorgorn là tên biệt danh của Ashley Aragorn Khoo, một lập trình viên người Singapore có thành tích ấn tượng hàng đầu thế giới.
**Ghi chú của biên tập: Ở vòng chung kết VNOI Cup 2025, Ashley Khoo đạt vị trí top 1 bảng mở rộng, đặc biệt hơn, anh có số điểm cao hơn cả thí sinh vô địch bảng chính thức.
Em có thể chia sẻ một số điều đấy không?
Anh Thành từng chỉ cho em một số trick để tối ưu khi chạy chương trình. Mấy cái như là cache-friendly, hoặc là những cái tối ưu ví dụ như mình có thể swap vòng lặp, hoặc là mình có thể set mảng giới hạn cố định để cho chương trình của mình chạy nhanh hơn. Hồi đó thì em có thử code nhân ma trận nhưng mà em cảm giác nhân ma trận này khá là chậm, thế nên em đã quyết định là nhờ anh Thành chỉ dẫn. Em thấy anh Thành nhiều lúc tối ưu khá là ảo nhưng mà anh lại có thể AC được. Em được biết những cái trick đó thì em thấy khá là hay, khá là thú vị.
Một ngôn ngữ lập trình khác ngoài C++ mà em mong muốn học thì nó sẽ là gì?
Em nghĩ là Python. Python là một trong những ngôn ngữ mà em sẽ tìm hiểu sâu hơn. Vì em nghĩ là về sau cũng có thể là mình sẽ cần dùng đến nó. Python cũng là một trong những ngôn ngữ mà em được học ngay thời điểm lớp 8 và lớp 9, vì lớp 8 thì chương trình Tin của mình có ngôn ngữ Python ấy ạ. Nói chung là em học Python lúc đấy chỉ là học chơi chơi thôi và em biết được một số câu lệnh của nó thôi, về sau thì gần như em chẳng bao giờ dùng đến nó nữa. Nhưng mà trong tương lai em có thể sẽ dùng nó nhiều hơn ấy ạ.
Đâu là thuật toán mà em cảm thấy ấn tượng nhất trong số các thuật toán gần đây em được học?
Gần đây thì em nghĩ là em học cũng không nhiều đâu ạ, nhưng mà có một thuật toán em ấn tượng là Segment Tree và Fenwick Tree vì đó là những cái cấu trúc dữ liệu nền tảng cho những cái tư duy mình cần phải có sau này. Ví dụ như Segment Tree thì nó là một trong những cái tư duy cơ bản về chia để trị, hoặc là Fenwick Tree thì khi mình học mình sẽ có thể có được một số tư duy về bit. Hồi cấp 2 có từng tự nghĩ ra một cái trò đó là chặt nhị phân trên cây Fenwick ấy ạ. Cái đó thì em nhớ là đã có ở trên mạng rồi, nhưng mà hồi đó em tự nghĩ ra, lên cấp 3 thì em mới nhận ra là trò này hóa ra nó đã có trên mạng rồi!
Tức là hồi cấp 2 em đã tự nghĩ ra một kỹ thuật mà sau này em mới biết là nó đã có rồi?
Dạ vâng.
Lúc đấy em tìm hiểu ra được kỹ thuật đấy thì em có viết lại hay em có thử nghiệm gì không?
Kỹ thuật đấy nói chung khi mà cài thì em thấy đơn giản lắm. Cài 2-3 dòng là xong. Về sau thì em dùng nó gần như mọi lúc mọi nơi luôn. Nhiều lúc em cảm giác là nếu mà em dùng được thì em sẽ dùng nó luôn. Mặc dù Fenwick Tree nói chung là nó cũng có một cái giới hạn khi sử dụng, nó không đa dụng như Segment Tree. Nhưng nếu em cảm giác em dùng được, và em dùng được walk* thì em dùng nó luôn. Hồi cấp 2 thì có một cái là em không biết về set và multiset, đó là một thiệt thòi mà em nghĩ là không hẳn là quá lớn. Nhiều lúc em sử dụng Fenwick Tree thì nó tối ưu hơn rất là nhiều, và nén số nữa.
*Ghi chú của biên tập: Walk ở đây là kỹ thuật "Walk on Fenwick Tree" tức kỹ thuật chặt nhị phân trên Fenwick Tree mà Huy Hậu vừa đề cập.
Quay về vấn đề khá là nổi cộm gần đây, thì em có biết là bây giờ có rất là nhiều model AI rất là mạnh. Thậm chí là người ta sử dụng những cái model này để đi thi những cuộc thi ở trên mạng, làm cho những kì thi dành cho người mới nó bị quá nhiều gian lận và khiến cho kì thi không còn hay nữa. Theo quan điểm của em về AI là như thế nào? Em nghĩ sao về tình trạng anh vừa nói?
Với em thì em thấy tình trạng này em không thích tí nào. Có một giai đoạn em cảm giác là, nhiều lúc mình học, nhưng mà có khi mình đi thi còn tệ hơn cả những cái model AI. Tức là mình phải tự nghĩ, tự làm bài mà kết quả còn tệ hơn cả những người mà chỉ ngồi prompt và chép code và gì đấy thôi. Về sau thì em cảm thấy là cheat (gian lận) bây giờ thì nó là một vấn đề gần như là phổ biến và nghiêm trọng hơn rất nhiều rồi. Trước thì mình chỉ có vài trò như là nhắn tin hỏi bài rồi chép code gì đấy, mấy cái đấy thì dễ phát hiện thôi vì đã có phần mềm MOSS rồi. Nhưng mà bây giờ thì mình có các model AI thì mọi thứ về gian lận nó phức tạp hơn rất nhiều rồi. Có những người mà rating xám hay xanh lá* mà lại làm được top siêu cao như trong VNOI Cup ngày đầu tiên** thì cái bảng rank đã bị chiếm trọn bởi những người mà rating rất là thấp hoặc là những người mới đăng ký account thôi. Thì đây là một vấn đề mà cần phải giải quyết một cách triệt để. Em cũng có một cái suy nghĩ như thế này, tức là em cảm thấy việc này có khi sẽ khó mà có thể tránh khỏi được, nhiều khi mình phải sống chung với nó. Giống như môn cờ vua vậy. Cái này thì em nghe được từ một người em là Nguyễn Khánh Phúc, em ấy có nói là trong cờ vua cũng vậy. Tức là cờ vua thì tình trạng gian lận cũng xảy ra rất là nhiều rồi, bây giờ người ta có thể cài những cái máy rung vào người, rồi đem vào phòng thi, những cái máy rung nhỏ nhỏ mà mình không thể dò được ấy. Nhưng có những người mà họ vẫn sẵn sàng tham gia thi đấu cờ vua, họ vẫn hết mình với đam mê của họ mà không bị những tình trạng gian lận ảnh hưởng đến mình. Thế nên em nghĩ là nhiều lúc mình vẫn nên giữ cho mình một cái lửa để mình đã theo đuổi CP thì vẫn theo đuổi thôi. Em cảm giác mình nên học CP như là một cái thú vui, chứ không phải là một thứ mà mình chỉ đem ra để đố nhau. Nhiều lúc nếu mà mình cạnh tranh quá, mình sẽ bị gọi là tâm lý không tốt rồi nhiều thứ khác diễn ra, mình có thể bực mình bởi các con AI được sử dụng bởi các "prompt thủ" ấy. Thì đó là quan điểm của em.
*Ghi chú của biên tập: Rating xám là rating newbie và rating xanh lá là rating pupil. Đây là 2 mức rating thấp nhất trên nền tảng Codeforces/VNOJ.
**Ghi chú của biên tập: Tức VNOI Cup 2025, Vòng loại thứ nhất. Đây là vòng loại VNOI Cup ghi nhận nhiều thí sinh bị hủy kết quả vì gian lận nhất.
Đúng như em nói là tình trạng CP bây giờ rất là giống với cờ vua. Cờ vua thì đã có model đánh cờ vua từ lâu rồi, có model có thể có rating (ELO) lên đến 3000, còn cao hơn cả người có rating cao nhất thế giới. Nhưng trên thế giới họ vẫn chế ra những model đó và tận dụng những model đấy để luyện tập. Thì theo quan điểm của em, áp dụng điều đó cho CP, việc sử dụng AI không vì mục đích cheat, mà vì mục đích luyện tập thì em thấy sao? Em đã áp dụng chưa?
Em nghĩ AI nếu mà mình biết áp dụng thì nó sẽ là một công cụ khá là mạnh anh ạ. Nhưng mà em thì trước giờ gần như là chưa bao giờ dùng AI. Vì trước giờ em cảm giác mình tự luyện đã khá là ổn rồi, thế nên là em cũng không muốn bản thân phụ thuộc vào AI ở thời điểm hiện tại. Trong thời điểm hiện tại thì em vẫn cảm thấy là mình tự làm đa số công việc vẫn khá là ổn. Một số việc mà em phải dùng AI là em nhờ làm ảnh hộ thôi (cười), hoặc nhờ làm bài tập về nhà hộ thôi ấy ạ. Nên là em cũng không muốn quá phụ thuộc vào AI trong giai đoạn mà em đang học CP đến bây giờ.
Trong thời gian này em đang ôn thi APIO nhưng mà vẫn dành thời gian với VNOI để phỏng vấn thì đó cũng là một điều rất đáng quý. Team VNOI chúc em có một kì thi thành công và thể hiện được hết khả năng của em để đạt được phong độ cao nhất. Cảm ơn em đã tham gia buổi ngày hôm nay, chúc em có một phong độ chói sáng cho kỳ thi APIO sắp tới!
Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.
Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.
Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng
Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.
Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.
Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.
Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!
Coding Challenge #4
Coding Challenge #4 có tên là Cân xu. Đây là bài toán mở rộng từ bài toán Quy hoạch động trên đồ thị có hướng không chu trình (DAG). Để giải quyết được bài toán lần này, yêu cầu các bạn thí sinh phải đưa ra nhiều nhận xét một cách khéo léo để biến đổi bài toán về một bài tập cấu trúc dữ liệu kinh điển.
Bài toán Cân xu đã được 362 thí sinh thử sức và có 9 lời giải xuất sắc đạt được số điểm tối đa.
Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi lời giải xuất sắc do bạn Nguyễn Hoàng Minh biên soạn.
Đề bài
Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.
Cho ~n~ đồng xu có trọng lượng phân biệt và ~m~ mối liên hệ không mâu thuẫn nhau có dạng ~x > y~, cho biết đồng xu ~x~ nặng hơn đồng xu ~y~. Gọi cấp bậc của một đồng xu là thứ tự của nó khi sắp xếp các đồng xu theo trọng lượng.
Với mỗi đồng xu, ta cần xác định giá trị ~k~ sao cho có thể xác định chính xác cấp bậc của đồng xu đó mà chỉ sử dụng ~k~ mối liên hệ đầu tiên; hoặc cho biết không thể xác định cấp bậc của đồng xu khi sử dụng cả ~m~ mối liên hệ.
Giới hạn:
~2 \leq n \leq 2 \cdot 10^5~.
~1 \leq m \leq 8 \cdot 10^5~.
Lời giải
Subtask 1
Giới hạn: ~n \leq 7~; ~m \leq 20~
Ý Tưởng
Đặt ~P~ là thứ tự của các đồng xu được sắp xếp tăng dần theo cấp bậc của chúng.
Với định nghĩa này, ta có thể biểu diễn ~P~ bằng một hoán vị của ~n~ số tự nhiên đầu tiên.
Ví dụ
Với ~n = 3~, ~P = (2, 3, 1)~ có thể được hiểu như:
Đồng xu ~2~ có cấp bậc là ~1~;
Đồng xu ~3~ có cấp bậc là ~2~;
Đồng xu ~1~ có cấp bậc là ~3~.
Đặt ~e_i = (x_i, y_i)~ là cặp đồng xu được cân ở lần cân thứ ~i~ (~1 \leq i \leq m~; đồng xu ~x_i~ nặng hơn đồng xu ~y_i~).
Đặt ~E_j = \{e_i \vert 1 \leq i \leq j \}~ là tập hợp cặp đồng xu của ~i~ lần cân đầu tiên.
Ta gọi một thứ tự ~P~ là hợp lệ với một tập hợp lần cân ~E~ nếu không tồn tại một cặp đồng xu nào mà thứ tự của chúng không thỏa kết quả của một lần cân nào đó trong ~E~.
Nói cách khác, nếu ~(x, y) \in E~ thì vị trí của đồng xu ~y~ phải nằm phía trước vị trí của đồng xu ~x~ trong ~P~ (đồng xu ~x~ có cấp bậc cao hơn đồng xu ~y~).
Vì dữ liệu đầu vào đảm bảo rằng các kết quả cân không mâu thuẫn với nhau, ít nhất một thứ tự hợp lệ phải tồn tại với tập hợp ~m~ lần cân (~E_m~).
Cấp bậc của đồng xu ~z~ là có thể chắc chắn xác định được với tập hợp lần cân ~E~ nếu trong mọi thứ tự ~P~ hợp lệ so với ~E~, cấp bậc của ~z~ không đổi (tạm gọi đây là điều kiện ~(1)~).
Vì vậy, nếu ta chỉ kiểm tra rằng cấp bậc của từng đồng xu có thể hay không thể được xác định (và đạt ~50~% số điểm của subtask 1), ta có thể:
Duyệt qua tất cả ~n!~ hoán vị để tìm các thứ tự hợp lệ; và
Với mỗi đồng xu, ta kiểm tra liệu có tồn tại hai thứ tự hợp lệ khác nhau mà cấp bậc của đồng xu trong hai thứ tự đó là khác nhau.
Với mỗi đồng xu ~z~, việc tìm được thời điểm sớm nhất mà có thể chắc chắn xác định cấp bậc của đồng xu đó sẽ tương đương với việc tìm ra tập hợp gồm các lần cân đầu tiên với kích thước nhỏ nhất sao cho điều kiện ~(1)~ vẫn thỏa.
Nói cách khác, ta cần tìm ~i~ nhỏ nhất sao cho với ~E_i~, cấp bậc ~z~ có thể chắc chắn xác định.
Để thực hiện điều này, ta có thể duyệt qua một tập hợp lần cân và thực hiện kiểm tra như trên.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(m \cdot n! \cdot (m + n))~.
Ta cần duyệt qua ~O(m)~ tập hợp lần cân.
Với mỗi tập hợp, ta cần duyệt qua ~O(n!)~ hoán vị để tìm các thứ tự hợp lệ.
Với mỗi thứ tự, ta thực hiện kiểm tra tính hợp lệ bằng cách duyệt qua ~O(m)~ lần cân. Nếu thứ tự hợp lệ, chúng ta cần phải kiểm tra cấp bậc của ~O(n)~ đồng xu có khác so với thứ tự hợp lệ khác không.
Code Minh Họa
Code C++ minh họa
#include<bits/stdc++.h>usingnamespacestd;template<classA,classB>boolmaximize(A&a,constB&b){return(a<b)?(a=b,true):false;}template<classA,classB>boolminimize(A&a,constB&b){return(a>b)?(a=b,true):false;}constexprintMAX_N=200'005,MAX_M=800'005,INF=0X3F3F3F3F,NINF=0XC0C0C0C0;intn,m,x[MAX_M],y[MAX_M];voidinput(){cin>>n>>m;for(inti=0;i<m;++i){cin>>x[i]>>y[i];--x[i];--y[i];}}vector<int>findPositions(constvector<int>&permutation){constintn=permutation.size();vector<int>positions(n);for(inti=0;i<n;++i)positions[permutation[i]]=i;returnpositions;}boolcheckValid(constvector<int>&order,constinte){constvector<int>&positions(findPositions(order));for(inti=0;i<e;++i)if(positions[x[i]]>positions[y[i]])returnfalse;returntrue;}boolcheckInvalid(constvector<int>&order,constinte){return!checkValid(order,e);}vector<int>findLevels(constinte){vector<int>levels(n,n),permutation(n);/** level = -1 : The level cannot be determined level = n : The level has not been determined yet (as there is no contradiction, there should no final result with this value) 0 <= level < n : The level is currently determined **/iota(permutation.begin(),permutation.end(),0);do{if(checkInvalid(permutation,e))continue;for(inti=0;i<n;++i){constauto&value=permutation[i];auto&level=levels[value];if(level<0)continue;if(level==n){level=i;continue;}if(level!=i)level=-1;}}while(next_permutation(permutation.begin(),permutation.end()));returnlevels;}vector<int>findWhen(){vector<int>result(n,-1);for(inte=1,i=0;e<=m;++e){constauto&levels(findLevels(e));for(i=0;i<n;++i){if(result[i]>=0||levels[i]<0)continue;result[i]=e;}}returnresult;}intmain(){#ifdef LOCALfreopen("input.INP","r",stdin);#endif // LOCALcin.tie(0)->sync_with_stdio(0);cout.tie(0);input();for(constint&e:findWhen())cout<<e<<' ';cout<<'\n';return0;}
Subtask 2
Giới hạn: ~n \leq 100~; ~m \leq 400~
Ý Tưởng
Ta có thể biểu diễn mối quan hệ trọng lượng tương đối bằng cách dựng một đồ thị.
Cụ thể hơn, đặt ~G = (V, E)~ với:
~V~ là tập hợp các đồng xu
~E~ là tập hợp các lần cân: ~(x, y) \in E~ (tồn tại một cung trực tiếp từ ~x~ tới ~y~) nếu như tồn tại một lần cân xác định được rằng đồng xu ~x~ nặng hơn đồng xu ~y~.
Ta nhận thấy rằng: đồng xu ~x~ có thể được xác định nặng hơn đồng xu ~y~ khi đồ thị ~G~ phải chứa ít nhất một đường đi từ ~x~ tới ~y~.
Giải thích
Giả sử đường đi từ ~x~ tới ~y~ là một dãy các đỉnh ~U_1, ..., U_k~ (với ~k \geq 2~, ~U_1 = x~, ~U_k = y~) thì theo cách ta dựng đồ thị, đồng xu ~U_i~ phải nặng hơn đồng xu ~U_{i + 1}~ (với ~1 \leq i < k~). Vì thế, dựa vào tích chất bắc cầu, ta có đồng xu ~U_1~ (hay ~x~) phải nặng hơn đồng xu ~U_k~ (hay ~y~).
Tập hợp các đỉnh mà có thể đến được từ đỉnh ~x~ cũng đồng thời là tập hợp các đỉnh đại diện cho đồng xu có thể xác định nhẹ hơn đồng xu ~x~.
Tương tự, tập hợp các đỉnh mà có thể đi tới được đỉnh ~x~ cũng đồng thời là tập hợp các đỉnh đại diện cho đồng xu nhẹ có thể xác định nặng đồng xu ~x~.
Cụ thể hơn, ta có thể đặt ~G^T = (V, E^T)~ với ~E^T = \{(y, x) \vert (x, y) \in E\}~
Minh họa đồ thị được dựng từ sample
- Đồ thị được dựng từ sample ~1~
- Đồ thị được dựng từ sample ~2~
Vì vậy, nếu ta chỉ muốn kiểm tra rằng cấp bậc của một đồng xu ~z~ có thể hay không thể được xác định (và đạt ~50~% số điểm của subtask 2, ta có thể thực hiện bằng cách kiểm tra phép hợp của hai tập hợp đến được từ ~z~ và có thể đi đến được ~z~ có chứa mọi đỉnh của đồ thị đã cho không (cấp bậc của đồng xu ~z~ chỉ có thể xác định khi trong lượng tương đối giữa nó và các đồng xu khác đều có thể xác định). Tạm gọi điều kiện của việc kiểm tra này là điều kiện ~(2)~.
Tương tự như subtask 1, với mỗi đồng xu ~z~, việc tìm được thời điểm sớm nhất mà có thể chắc chắn xác định cấp bậc của đồng xu đó sẽ tương đương với việc tìm ra tập hợp gồm các lần cân đầu tiên với kích thước nhỏ nhất sao cho điều kiện ~(2)~ vẫn thỏa.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot m \cdot (n + m))~.
Ta cần duyệt qua ~O(n)~ đỉnh đại diện cho các đồng xu.
Với mỗi đỉnh, ta cần duyệt qua ~O(m)~ tập hợp lần cân.
Với mỗi tập hợp lần cân, việc duyệt đồ thị có thể được thể được hiện tại với thuật toán BFS hoặc DFS với độ phức tạp thời gian ~O(n + m)~.
Subtask 3có thể được giải quyết theo nhiều cách khác nhau.
Cách Thứ Nhất
Ta có nhận xét rằng, với đồng xu ~z~, nếu cấp bậc của ~z~ có thể được xác định với tập hợp ~E_i~, tập hợp của ~i~ lần cân đầu tiên, thì cũng có thể được xác định với ~E_j~ (với ~i < j \leq m~) vì ~E_i \subset E_j~.
Vì vậy, thay vì duyệt tuần tự từng tập hợp lần cân (mỗi lần xét một thêm kết quả cân) như trong subtask 2, ta có thể sử dụng thuật toán chặt nhị phân để tìm được thời điểm sớm nhất.
Cách Thứ Hai
Ý tưởng của cách thứ hai gần giống với thuật toán Prim (sử dụng trong cho bài toán tìm cây khung nhỏ nhất).
Với mỗi cạnh ~e_i~ trong đồ thị ~G~ được định nghĩa trước đó, ta đặt trọng số của cạnh ~e_i~ là ~i~ (thời điểm cặp đồng xu mà ~e_i~ đại diện được cân).
Với một đỉnh ~z~, ta đặt ~V^{+}_{z}~ là tập hợp các đỉnh có thể đến được từ ~z~ trong ~G~ (bao gồm cả ~z~).
Ta nhận thấy rằng việc tìm thời điểm sớm nhất mà tập hợp ~V^{+}_{z}~ cũng sẽ tương đương với việc tối thiểu hóa trọng số lớn nhất trong cây chứa các cạnh ~V^{+}_{z}~.
Tương tự, ta đặt ~V^{-}_{z}~ là tập hợp các đỉnh có thể đến được từ ~z~ trong ~G^{T}~ (bao gồm cả ~z~).
Ta nhận thấy rằng việc tìm thời điểm sớm nhất mà tập hợp ~V^{-}_{z}~ cũng sẽ tương đương với việc tối thiểu hóa trọng số lớn nhất trong cây chứa các cạnh ~V^{-}_{z}~.
Để tối thiểu hóa trong cả hai trường hợp, ta đều có thể thực hiện bằng cách:
Khởi đầu với cây gồm một đỉnh ~z~ duy nhất;
Lần lượt chọn cạnh với trọng số nhỏ nhất nối từ một đỉnh đã thuộc cây và một đỉnh chưa thuộc cây;
Thêm cạnh và đỉnh của cạnh đó và cây;
Thực hiện nhiều lần cho đến khi ta không thể mở rộng được cây nữa.
Nếu ~V^{+}_{z} \cup V^{-}_{z} \neq V~ thì cấp bậc của ~z~ không thể xác định.
Ngược lại, cấp bậc của ~z~ sẽ là giá trị lớn nhất trong hai trường hợp.
Độ Phức Tạp
Ý tưởng trong cách thứ nhất có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot \log m \cdot (n + m))~.
Độ phức tạp có thể được phân tích gần như tương tự như trong Subtask 2 nhưng khi này, ta chỉ xét ~O(\log m)~ thay vì ~O(m)~ tập hợp lần cân.
Ý tưởng trong cách thứ hai có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot (n + m \log m))~.
Ta phải xét qua ~O(n)~ đỉnh.
Với mỗi đỉnh, việc xử lý thông tin các đỉnh có độ phức tạp ~O(n)~.
Nếu chúng ta sử dụng heap để xác định cạnh với trọng số nhỏ nhất, bước xử lý sẽ có độ phức tạp ~O(m \log m)~ bởi chúng ta thêm ~O(m)~ cạnh vào heap với mỗi thao có độ phức tạp ~O(\log m)~.
Ngoài ra, ý tưởng trong cách thứ hai cũng có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot (n + m))~ nếu ta sử dụng một mảng danh sách đánh số theo chỉ số cạnh thay vì dùng heap bởi trọng số cạnh chỉ nằm trong đoạn từ ~1~ tới ~m~.
Vì dữ liệu đầu vào đảm bảo rằng các kết quả cân không mâu thuẫn với nhau, đồ thị ~G~ được dựng trước đó sẽ không chứa chu trình. Điều này đồng nghĩa với việc ~G~ là một DAG (Directed acyclic graph).
Ta đặt ~S~ là một thứ tự Tô-pô của ~G~ và đặt ~T_x~ là vị trí của ~x~ trong thứ tự đó (~T_x~ có thể được xem như chỉ số của ~x~ sau khi ta thực hiện sắp xếp Tô-pô).
Để miêu tả phần còn lại của ý tưởng dễ hơn, ta sẽ đánh số đỉnh đồ thị lại theo thứ tự Tô-pô (với mọi cung ~(x, y)~ trong ~G~ sau khi đã đánh số lại, ta có ~x < y~).
Ta đặt ~R_x~ là chỉ số đỉnh nhỏ nhất mà có cung từ trực tiếp từ ~x~ đến đỉnh đó (có thể xem như ~R_x = +\infty~ nếu như ~x~ không có cung đi ra).
Ta có nhận xét rằng: với mọi đỉnh ~z < x~, nếu như ~R_u \leq x~ với mọi ~z \leq u \leq x~ thì phải tồn tại ít nhất một đường đi từ ~z~ tới ~x~.
Chứng minh
Nhận xét trên có thể được chứng minh bằng cách quy nạp:
Bước cơ sở: với ~z = x - 1~
Vì ~z < R_z~, ta có ~x - 1 < R_z \leq x~. Nói cách khác, ~R_z = x~ hay từ ~z~ đến ~x~ có một cung trực tiếp.
Bước quy nạp: giả định nhận xét trên thỏa với mọi ~z < u \leq x~, ta cần chứng minh nhận xét trên cũng thỏa với ~z~.
Vì ~z~ có cung trực tiếp từ nó đến ~R_z~ (theo như định nghĩa của ~R_z~) và ~R_z~ có đường đi từ nó tới ~x~ (theo như giả định và ~z < R_z \leq x~), ~z~ có đường đi từ nó tới ~x~.
Tương tự, ta đặt ~L_x~ là chỉ số đỉnh lớn nhất mà có cung từ trực tiếp từ đỉnh đó đến ~x~ (có thể xem như ~L_x = -\infty~ nếu như không có cung đi đến ~x~).
Ta có nhận xét rằng: với mọi đỉnh ~x< z~, nếu như ~x \leq L_u~ với mọi ~x \leq u \leq z~ thì phải tồn tại ít nhất một đường đi từ ~x~ tới ~z~.
Chứng minh
Nhận xét trên có thể được chứng minh bằng cách quy nạp như nhận xét trước đó:
Bước cơ sở: với ~z = x + 1~
Vì ~L_z < z~, ta có ~x \leq L_z < x + 1~. Nói cách khác, ~L_z = x~ hay từ ~x~ đến ~z~ có một cung trực tiếp.
Bước quy nạp: giả định nhận xét trên thỏa với mọi ~x \leq u < z~, ta cần chứng minh nhận xét trên cũng thỏa với ~z~.
Vì ~L_z~ có cung trực tiếp từ nó đến ~z~ (theo như định nghĩa của ~L_z~) và ~L_z~ có đường đi từ ~x~ tới nó (theo như giả định và ~x \leq L_z < z~), ~z~ có đường đi từ ~x~ tới nó.
Dựa trên hai nhận xét này, nếu ta chỉ muốn kiểm tra rằng cấp bậc của một đồng xu ~z~ (sau khi đã đánh số lại) có thể hay không thể được xác định (và đạt ~50~% số điểm của subtask 4), ta cần kiểm tra cả hai điều kiện sau có thỏa không:
Với mọi đỉnh ~u~ có chỉ số nhỏ hơn ~z~, ~R_u \leq z~.
Với mọi đỉnh ~u~ có chỉ số lớn hơn ~z~, ~z \leq L_u~.
Để xác định chính xác thời điểm sớm nhất cấp bậc của một đỉnh có thể được xác định, nếu ta thực hiện kiểm tra nêu trên nhiều lần với các tập hợp lần cân khác nhau, chi phí tính sẽ quá lớn.
Ta đặt ~C_z~ là số lượng đỉnh ~u~ thỏa mãn điều kiện nếu ta đang xét đỉnh ~z~ (~R_u \leq z~ nếu ~u < z~ hoặc ~z \leq L_u~ nếu ~z < u~). Cấp bậc của đỉnh ~z~ có thể xác định được ở thời điểm ~C_z = n - 1~ sớm nhất.
Ta nhận thấy rằng, nếu ta bắt đầu với một đồ thị chưa có cạnh nào và thêm dần các cạnh theo thứ tự đề bài, giả sử cạnh đang xét là ~(x, y)~ thì ta sẽ chứng kiến những thay đổi này sau đây:
~R_x~ có thể giảm thành ~y~: Khi này, giá trị ~C_u~ tăng thêm một đơn vị với ~u~ trong đoạn từ ~y~ tới ~R_x - 1~.
~L_y~ có thể tăng thành ~x~: Khi này, giá trị ~C_u~ tăng thêm một đơn vị với ~u~ trong đoạn từ ~L_x + 1~ tới ~y~.
Sau khi cập nhật các giá trị ~C_u~ sau mỗi lần thêm cạnh, giá trị ~C_u~ mà ta cần để ý cũng chính là giá trị ~C_u~ lớn nhất (bởi ~n - 1~ cũng là giá trị lớn nhất có thể của ~C_u~).
Ta cần thực hiện update (tăng giá trị) các đoạn khác nhau
Ta cần tìm giá trị lớn nhất trên đoạn.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O((n + m) \log n)~.
Việc tìm thứ tự Tô-pô có thể được thực hiện trong ~O(n + m)~.
Vì ta cần phải duyệt qua ~O(m)~ cạnh và với mỗi cạnh, ta có thể update đoạn với độ phức tạp ~O(\log n)~.
Ngoài ra, mỗi khi cấp bậc của một đỉnh được xác định, ta phải "xóa" đỉnh đó khỏi cấu trúc dữ liệu để có thể tìm được những đỉnh khác. Ta sẽ có ~O(n)~ thao tác "xóa" như vậy và mỗi thao tác có thể có độ phức tạp ~O(\log n)~.
Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.
Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.
Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng
Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.
Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.
Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.
Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!
Coding Challenge #5
Coding Challenge #5 có tên là Vô hạn. Đây là bài toán yêu cầu các thí sinh sử dụng nhiều kỹ năng số học để xử lý. Bài toán Vô hạn đã được 392 thí sinh thử sức và có 36 lời giải xuất sắc đạt được số điểm tối đa.
Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi 2 lời giải xuất sắc do bạn Nguyễn Hoàng Minh (lời giải 1) và Lê Minh Tuấn (lời giải 2) biên soạn.
Đề bài
Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.
Cho ~\mathcal{T}~ câu hỏi có dạng sau:
Cho số nguyên dương ~n~, đếm số cặp số nguyên ~a, b~ thỏa ~1 \leq a, b \leq n~ và ~\frac{a}{b}~ là một số thập phân vô hạn.
Giới hạn:
~1 \leq \mathcal{T} \leq 10~
~1 \leq n \leq 10^{12}~
Lời giải 1
Subtask 1
Giới hạn: ~1 \leq n \leq {10}^{3}~
Ý Tưởng
Một phân số ~\frac{a}{b}~ (với ~a~ và ~b~ là số nguyên dương) có thể được biểu diễn bằng số thập phân hữu hạn nếu như tồn tại hai số nguyên không âm ~k~ và ~e~ sao cho:
~\frac{a}{b} = \frac{k}{{10}^e}~
Nếu ta đặt ~\frac{x}{y}~ là phân số tối giản bằng với ~\frac{a}{b}~ (tức ~\gcd(x, y) = 1~ và ~\frac{x}{y} = \frac{a}{b}~), điều kiện trên sẽ tương đương với việc tồn tại các số nguyên không âm ~c~, ~k~ và ~e~ sao cho:
~\begin{cases}
x \cdot c = k\\[4pt]
y \cdot c = {10}^e
\end{cases}~
Vì ~{10}^e~ không thể chứa ước nguyên tố ngoài ~2~ và ~5~, ~y~ (và ~c~ được chọn) cũng phải thỏa mãn điều kiện tương tự (~1~).
Mặt khác, nếu ~y~ không chứa ước nguyên ngoài ~2~ và ~5~ thì ~y~ có thể được viết dưới dạng ~2^{u} \cdot 5^{v}~ với ~u~ và ~v~ là hai số nguyên không âm. Khi này, ta có thể đặt ~e = \max(u, v)~, ~c = 2^{e - u} \cdot 5^{e - v}~, và ~k = x \cdot c~, ta nhận thấy:
Vì thế ~\frac{a}{b}~ có thể được biểu diễn bằng số thập phân hữu hạn (~2~).
Từ (~1~) và (~2~), ta thấy được rằng phân số ~\frac{a}{b}~ là một số thập phân hữu hạn nếu như mẫu số của phân số tối giản thu được từ việc rút gọn ~\frac{a}{b}~ không chứa bất kì một ước số nguyên tố nào ngoài ~2~ và ~5~.
Với giới hạn của subtask 1, chúng ta có thể đếm số lượng phân số là số thập phân hữu hạn trong thời gian cho phép bằng cách duyệt qua mọi cặp số nguyên dương ~(a, b)~ (~1 \leq a, b \leq n~) và thực hiện kiểm tra như trên.
Số lượng cặp số nguyên dương ~(a, b)~ (~1 \leq a, b \leq n~) mà ~\frac{a}{b}~ là số thập phân vô hạn bằng tổng số ~n^2~ cặp trừ đi số lượng các phân số cho kết quả hữu hạn trên.
Độ Phức Tạp
Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot n^2 \cdot \log(n))~.
Chúng ta cần duyệt qua ~n^2~ cặp số; và
Với mỗi cặp số ~(a, b)~, chúng ta có thể:
xác định phân số tối giản tương đương trong ~O(\log n)~ bằng cách chia tử và mẫu với ước chung lớn nhất của chúng; và
xác định mẫu có chứa ước nguyên tố ngoài ~2~ và ~5~ bằng cách rút một trong hai ước nguyên tố này ra cho đến khi không thể thực hiện được nữa (khi này, phân số sẽ là một số thập phân hữu hạn nếu số được rút gọn bằng một; và một số thập phân vô hạn trong trường hợp còn lại).
Chúng ta sẽ có thể phải thực hiện ~O(\log_2(n) + \log_5(n)) = \log(n)~ bước rút ước số ra.
Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(1)~.
Giới hạn của subtask 2 không cho phép chúng ta duyệt qua mọi phân số như subtask 1 nữa nhưng vẫn cho phép chúng ta có thể duyệt qua mọi giá trị mà tử số hoặc mẫu số có thể có.
Với một phân số ~\frac{a}{b}~ (~1 \leq a, b \leq n~ và ~a, b~ là số nguyên), ta nhận thấy rằng để ~\frac{a}{b}~ là một số thập phân hữu hạn thì với mọi lũy thừa ~p^z~ (~z \in \mathbb{N}~) của một số nguyên tố ~p~ bất kì khác ~2~ và ~5~, nếu mẫu số ~b~ chia hết cho ~p^z~ thì ~a~ cũng phải chia hết cho ~p^z~ bởi như vậy, ta mới triệt tiêu được ước số nguyên tố khác ~2~ và ~5~ khỏi mẫu khi rút gọn phân số ~\frac{a}{b}~ thành phân số tối giản.
~\forall p \in \mathbb{P} \setminus \{2,5\}, \; \forall z \in \mathbb{N}, \; (p^z \mid b \;\Rightarrow\; p^z \mid a)~
với ~\mathbb{P}~ là tập hợp các số nguyên tố.
Một cách tổng quát hơn, nếu ta đặt ~b = 2^u \cdot 5^v \cdot w~ với ~u~ và ~v~ là số tự nhiên, và ~w~ là số tự nhiên không chia hết cho ~2~ và ~5~, thì ta có ~a = w \cdot s~ với ~s~ là số nguyên dương sao cho ~1 \leq a \leq n~.
Vì vậy, với một số tự nhiên ~b~ xác định là mẫu số ~(1 \leq b \leq n)~, ta có thể chọn ~\lfloor \frac{n}{w} \rfloor~ giá trị hợp lệ khác nhau cho ~a~ bởi ~1 \leq s~ và ~w \cdot s \leq n \Rightarrow s \leq \frac{n}{w}~.
Dựa trên quan sát này, ta có thể đếm số lượng phân số là số thập phân hữu hạn bằng cách duyệt qua mọi mẫu số ~b~ (từ ~1~ tới ~n~), xác định thành phần ~w~ được định nghĩa như trên và tính tổng các giá trị ~\lfloor \frac{n}{w} \rfloor~.
Độ Phức Tạp
Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot n \cdot \log(n))~.
Chúng ta cần duyệt qua ~n~ mẫu số; và
Với mỗi mẫu số ~b~, chúng ta sẽ có thể phải thực hiện ~O(\log_2(n) + \log_5(n)) = \log(n)~ bước rút ước số ra khỏi ~b~ để xác định ~w~.
Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(1)~.
Giới hạn của subtask 3 không cho phép chúng ta duyệt qua mọi mẫu số như subtask 2. Tuy nhiên, ta có thể duyệt qua tất cả thành phần ~2^u \cdot 5^v~ khác nhau trong mẫu số (được đề cập trong subtask 2). Cụ thể hơn, ta có ~O(\log_2 n \cdot \log_5 n)~ trường hợp khác nhau bởi điều kiện ~2^u \cdot 5^v \leq n~ phải thỏa:
~u~ có thể đạt giá trị lớn nhất khi ~v = 0~ ~\Rightarrow~ ~2^u \leq n~ hay ~u \leq \log_2 n~
Vì ~u \geq 0~, ~u~ có thể có ~O(\log_2 n)~ giá trị khác nhau;
Tương tự, ~v~ có thể đạt giá trị lớn nhất khi ~u = 0~ ~\Rightarrow~ ~5^v \leq n~ hay ~v \leq \log_5 n~
Vì ~v \geq 0~, ~v~ có thể có ~O(\log_5 n)~ giá trị khác nhau.
Để đếm số lượng phân số là số thập phân hữu hạn, với mỗi thành phần ~2^u \cdot 5^v~, ta cần đếm số lượng cặp số ~(s, w)~ đại diện cho phân số ~\frac{s \cdot w}{2^u \cdot 5^v \cdot w}~ sao cho tất cả điều kiện sau thỏa:
~\gcd(w, 10) = 1~ (tức ~2 \nmid w~ và ~5 \nmid w~): ~w~ không chia hết cho ~2~ và ~5~;
~1 \leq s \leq \lfloor \frac{n}{w} \rfloor~ (bởi ~1 \leq s \cdot w \leq n~);
~1 \leq w \leq \lfloor \frac{n}{2^u \cdot 5^v} \rfloor~ (bởi ~1 \leq 2^u \cdot 5^w \cdot w \leq n~)
Nói cách khác, nếu ta đặt:
~R(x) = \{z \vert (z \in N) \land (1 \leq z \leq x)\}~ là tập các số tự nhiên từ ~1~ đến ~x~
Khi này, ta có ~T(u, v) = N_1(u, v) - N_2(u, v) - N_5(u, v) + N_{10}(u, v)~
~\Rightarrow~ Tổng các giá trị ~T(u, v)~ với mọi ~u~ và ~v~ sẽ chính là số lượng phân số là số thập phân hữu hạn.
Bây giờ, yêu cầu còn lại cần phải được giải quyết là tính các giá trị ~N_x(u, v)~ một cách hiệu quả.
Ta không thể thực hiện bằng cách duyệt qua từng giá trị ~w~ vì ta có thể phải duyệt qua ~O(n)~ giá trị khác nhau.
Tuy nhiên, ta có nhận xét rằng chỉ có ~O(\sqrt n)~ giá trị ~\lfloor \frac{n}{w}\rfloor~ khác nhau.
Giải thích chi tiết
Với ~w \leq \sqrt n~, ta hiển nhiên có ~O(\sqrt n)~ giá trị ~\lfloor \frac{n}{w}\rfloor~ khác nhau vì mỗi giá trị ~w~ ứng với một giá trị ~\lfloor \frac{n}{w}\rfloor~;
Với ~w \geq \sqrt n~, ta có ~\lfloor \frac{n}{w}\rfloor \leq \sqrt n~ và vì thế, ta có ~O(\sqrt n)~ giá trị ~\lfloor \frac{n}{w}\rfloor~ khác nhau;
Dựa vào nhận xét này, thay vì xem xét từng giá trị ~w~, ta xem xét gộp các giá trị ~w~ mà có cùng giá trị ~\lfloor \frac{n}{w} \rfloor~ vào cùng một nhóm. Cụ thể, ta sẽ có ~O(\sqrt n)~ nhóm gồm các giá trị liên tiếp nhau.
~7 \leq w \leq 10 \Rightarrow \lfloor \frac{n}{w}\rfloor = 2~
~11 \leq w \leq 20 \Rightarrow \lfloor \frac{n}{w}\rfloor = 1~
Ta thấy rằng tổng các giá trị ~\lfloor \frac{n}{w} \rfloor~ trong cùng một nhóm có thể được xác định dễ dàng với độ phức tạp thời gian ~O(1)~. Việc tính giá trị ~N_x(u, v)~ sẽ dựa vào việc ta thao tác trên các nhóm này.
Cách tính chi tiết
Ta đặt ~M(l, r, d)~ là số lượng số nguyên trong đoạn từ ~l~ tới ~r~ chia hết cho ~d~. Giá trị hàm này có thể được xác định như sau: ~M(l, r, d) = \max(0, \lfloor \frac{r}{d} \rfloor - \lceil \frac{l}{d} \rceil + 1)~
Ta đặt ~S(l, r, d)~ là tổng ~\lfloor \frac{n}{w}\rfloor~ với mọi số nguyên ~w~ trong đoạn từ ~l~ tới ~r~ chia hết cho ~d~. Nếu ~l~ và ~r~ thuộc cùng một nhóm, giá trị hàm này có thể được xác định như sau: ~G(l, r, d) = M(l, r, d) \cdot \lfloor \frac{n}{l}\rfloor~
Giá trị ~N_x(u, v)~ có thể được tính bằng cách tách các giá trị ~w~ ra các nhóm và tính giá trị ~S~ trên các nhóm đó.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(t \cdot (\sqrt n + \log^2 n))~:
Bước xác định nhóm có độ phức tạp ~O(\sqrt n)~ bởi ta có ~O(\sqrt n)~ nhóm.
Bước duyệt qua từng thành phần ~2^u \cdot 5^v~ nêu trên và đếm số lượng có độ phức tạp ~O(\log^2 n)~ nếu ta thực hiện offline (ta thực hiện duyệt và đếm cùng lúc với xác định từng nhóm theo thứ tự).
Về bộ nhớ, ý tưởng nêu trên có thể được cài đặt với độ phức tạp ~O(\log^2 n)~ để lưu các thành phần ~2^u \cdot 5^v~ nêu trên.
Lưu ý: Ý tưởng trên vẫn có thể được cài đặt theo nhiều cách khác với độ phức tạp khác với độ phức tạp nêu trên.
Cho số nguyên dương ~n~, đếm số cặp (~a, b~) (~1 \le a, b \le n~) thoả mãn ~\frac{a}{b}~ là số thập phân vô hạn.
Subtask 1
~\frac{a}{b}~ là số thập phân vô hạn ~\Leftrightarrow~ mẫu số của ~\frac{a}{b}~ sau khi rút gọn tồn tại ít nhất một thừa số nguyên tố khác ~2~ và ~5~. Chứng minh:
Để đơn giản ta xét các phân số ~\frac{a}{b}~ là phân số tối giản, nghĩa là ~\text{gcd}(a,b)=1~.
Chiều thuận: Giả sử ~\frac{a}{b}~ có biểu diễn thập phân hữu hạn. Khi đó tồn tại số nguyên không âm ~k~ sao cho ~10^k \cdot \frac{a}{b}~ là số nguyên, nghĩa là ~10^k~ chia hết cho ~b~ (do ~(a,b)=1~). Từ đó suy ra ~b~ chỉ chứa các ước nguyên tố ~2~ và ~5~.
Chiều ngược: Giả sử ~b=2^x 5^y~, chọn ~k = \max(x,y)~, khi đó ta có ~10^k \cdot \frac{a}{b}~ là số nguyên ~\Rightarrow~ ~\frac{a}{b}~ là số thập phân hữu hạn.
Từ đó với mỗi test, ta có thể duyệt toàn bộ cặp ~(a, b)~ với ~1 \le a, b \le n~, và kiểm tra điều kiện bằng cách:
Rút gọn phân số ~\frac{a}{b}~ bằng cách gán ~a \leftarrow \frac{a}{\text{gcd}(a, b)}~, ~b \leftarrow \frac{b}{\text{gcd}(a, b)}~
Trong khi ~b~ còn chia hết cho ~2~, chia ~b~ cho ~2~. Tương tự với ~5~.
Nếu ~b>1~ tức là ~b~ còn chứa một thừa số nguyên tố khác ~2~ và ~5~, ta tăng đáp án lên ~1~.
Độ phức tạp của việc duyệt là ~\mathcal{O}(n^2 \log n)~, tuy nhiên không phải việc tính ~\text{gcd}~ lúc nào cũng mất ~\log n~ nên có thể vẫn qua được hết test. Tuy nhiên ta có thể tính trước các mảng:
~g(i, j)~ là ước chung lớn nhất của hai số ~i~ và ~j~,
~f(i)~ trả về ~\texttt{true}~ nếu ~i~ chỉ chứa thừa số nguyên tố ~2~ và ~5~, ~\texttt{false}~ nếu ngược lại.
để việc kiểm tra với mỗi test chỉ còn ~\mathcal{O}(n^2)~, đưa độ phức tạp về ~\mathcal{O}(tn^2)~
Thay vì đếm số lượng số thập phân vô hạn, ta có thể đếm phần bù bằng cách tính số lượng số thập phân hữu hạn, sau đó lấy ~n^2~ trừ đi là ra đáp án cần tìm.
Nhận thấy việc rút gọn phân số như ở subtask 1 là quá tổng quát và không cần thiết cho việc đếm, mà ta chỉ cần biểu diễn phân số ~\frac{a}{b}~ dưới dạng:
~\frac{a}{b} = \frac{a' c}{b' c}~
với:
~c~ không chứa thừa số nguyên tố ~2~ và ~5~,
~b'~ chỉ chứa thừa số nguyên tố ~2~ và ~5~,
~a'~ bất kì.
là đủ, vì ta chỉ cần biết mẫu số sau khi rút gọn chỉ còn các thừa số ~2~ và ~5~ hay không.
Từ đó thay vì duyệt ~a~ và ~b~, ta sẽ duyệt ~c~ và đếm số cặp (~a',b'~) có dạng như trên. Với mỗi ~c~:
Số lượng ~a'~ thoả mãn là ~\lfloor \frac{n}{c} \rfloor~
Số lượng ~b'~ thoả mãn là: số lượng số có dạng ~2^i \times 5^j~ và có giá trị ~\le \lfloor \frac{n}{c} \rfloor~
Ta có thể chuẩn bị trước các số có dạng ~2^i \times 5^j~ theo thứ tự tăng dần vào một mảng. Từ đó với mỗi ~c~, ta có thể dùng hai con trỏ để đếm số lượng số ~b'~ thoả mãn do ~c~ tăng dần ~\Rightarrow~ ~\lfloor \frac{n}{c} \rfloor~ giảm dần.
Từ đó ta cộng vào đáp án một lượng: (Số lượng ~a'~ thoả mãn) ~\times~ (Số lượng ~b'~ thoả mãn).
Đáp án không vượt quá ~10^{12}~, nên ta có thể dùng kiểu ~\texttt{int64}~ và tiến hành mod sau khi đã tính toán xong.
Độ phức tạp: ~\mathcal{O}(tn)~
Cài đặt mẫu:
#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;constintmod=1e9+7;boolf[N];vector<int>cand;intmain(){ios_base::sync_with_stdio(0);cin.tie(0);for(inti=1;i<N;i++){intx=i;while(x%2==0)x/=2;while(x%5==0)x/=5;f[i]=x==1;if(f[i]){cand.emplace_back(i);}}inttc;cin>>tc;while(tc--){intn;cin>>n;int64_tans=0;intptr=int(cand.size())-1;for(intc=1;c<=n;c++){if(c%2==0||c%5==0){continue;}// x <= n/c// y <= n/c and f[y] == 1while(ptr>=0&&1ll*cand[ptr]*c>n)--ptr;ans+=1ll*(n/c)*(ptr+1);}cout<<(1ll*n*n-ans)%mod<<'\n';}return0;}
Subtask 3
Nhận xét:
Chỉ có tối đa ~2\sqrt{n}~ giá trị ~\lfloor \frac{n}{c} \rfloor~ phân biệt.
Nếu ~c \le \sqrt{n}~, rõ ràng số lượng giá trị phân biệt tương ứng với số lượng số ~c~, là ~\sqrt{n}~
Nếu ~c > \sqrt{n}~, thì ~\lfloor \frac{n}{c} \rfloor~ chỉ nhận các giá trị nguyên từ ~1~ đến ~\sqrt{n}~.
Tổng lại ta có số lượng giá trị phân biệt tối đa là ~2\sqrt{n}~.
Các giá trị ~c~ có cùng kết quả khi tính ~\lfloor \frac{n}{c} \rfloor~ nằm trên một đoạn liên tiếp của trục số.
Điều này là dễ thấy dựa vào tính chất đơn điệu của dãy ~\lfloor \frac{n}{c} \rfloor~ như đã trình bày ở subtask 2.
Nếu cố định ~\lfloor \frac{n}{c} \rfloor~, thì đáp án là giống nhau cho dù ~c~ có thay đổi.
Như vậy ta chỉ cần thay đổi phần duyệt ở subtask 2:
Ta sẽ duyệt qua các đoạn ~[l,r]~ sao cho ~\lfloor \frac{n}{c} \rfloor~ là cố định với mọi ~c~ thuộc đoạn ~[l,r]~.
Với mỗi đoạn ~[l,r]~ như vậy, cộng vào đáp án một lượng ~\text{số lượng số trong đoạn [l, r] không chia hết cho 2 hoặc 5}~ ~\times~ ~\lfloor \frac{n}{l} \rfloor~ ~\times~ ~\text{số lượng giá trị b' thoả mãn}~
Sử dụng bao hàm loại trừ để tính số lượng số trong đoạn ~[l, r]~ không chia hết cho ~2~ hoặc ~5~.
Cách tính số lượng giá trị ~b'~ thoả mãn giống như ở subtask 2. Tuy nhiên việc chuẩn bị cần phải tinh tế hơn: thay vì duyệt từ ~1~ đến ~n~ rồi kiểm tra, ta chỉ duyệt các cặp ~(i, j)~ và tính giá trị ~2^i \times 5^j~. Nhận thấy ~i, j \le \log_2 (n)~ nên ta có thể duyệt trâu và sắp xếp được.
Vấn đề cuối cùng là duy trì tập các đoạn ~[l,r]~:
Ta có thể duyệt ~l~ tăng dần từ ~1~. Với mỗi ~l~, ta chặt nhị phân tìm ~r~ xa nhất sao cho ~\lfloor \frac{n}{l} \rfloor = \lfloor \frac{n}{r} \rfloor~. Sau khi tính toán xong, gán ~l \leftarrow r+1~.
Tuy nhiên độ phức tạp cho việc trên có thể lên đến ~\mathcal{O}(t \sqrt{n} \log {n})~.
Ta có thể tìm ~r~ trong ~\mathcal{O}(1)~. Đặt ~q = \lfloor \frac{n}{l} \rfloor~, thì ~r = \lfloor \frac{n}{q} \rfloor~.
Do nếu ta có ~i~ thoả mãn ~\lfloor \frac{n}{i} \rfloor = q~, thì ~i \le \frac{n}{q}~, từ đó ta chọn được số lớn nhất mà vẫn thoả mãn điều kiện.
Độ phức tạp: ~\mathcal{O}(t \sqrt{n})~
Cài đặt mẫu:
#include<bits/stdc++.h>usingnamespacestd;constintMOD=1e9+7;intmain(){ios_base::sync_with_stdio(0);cin.tie(0);vector<int64_t>cand;for(int64_ti=1;i<=1e12;i*=2){for(int64_tj=1;j<=1e12/i;j*=5){cand.emplace_back(i*j);}}sort(cand.begin(),cand.end());inttc;cin>>tc;while(tc--){int64_tn;cin>>n;__int128_tans=0;intptr=int(cand.size())-1;autof=[&](int64_tl,int64_tr,int64_td){return(r/d-(l-1)/d);};autocount_numerator=[&](int64_tl,int64_tr){returnf(l,r,1)-f(l,r,2)-f(l,r,5)+f(l,r,10);};for(int64_tlc=1;lc<=n;){int64_tnc=n/lc;int64_trc=n/nc;while(ptr>=0&&cand[ptr]>nc)--ptr;// so so trong doan [lc, rc] khong chia het cho 2 va 5ans+=__int128_t(count_numerator(lc,rc))*nc*(ptr+1);lc=rc+1;}cout<<(int)((__int128_t(n)*n-ans)%MOD)<<'\n';}return0;}
Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.
Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.
Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng
Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.
Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.
Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.
Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!
Coding Challenge #6
Coding Challenge #6 có tên là Mua hàng. Đây là bài toán có format đặc biệt trong các số coding challenge vừa qua khi là một bài toán interactive, tức chương trình của thí sinh tương tác với chương trình của giám khảo để đưa ra đáp án. Để có được số điểm tối đa cho bài toán, thí sinh cần áp dụng một vài nhận xét về xác suất vào mô hình chia để trị để xây dựng lời giải. Bài toán Mua hàng đã được 344 thí sinh thử sức và có 14 lời giải xuất sắc đạt được số điểm tối đa.
Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi lời giải xuất sắc do bạn Nguyễn Hoàng Minh biên soạn.
Đề bài
Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.
Cho một hoán vị ~p~ bị ẩn đi và một số nguyên ~k~. Yêu cầu tìm chỉ số của ~k~ phần tử có giá trị lớn nhất bằng cách sử dụng ít nhất số lượng câu hỏi có dạng như sau:
Chọn hai số nguyên ~x, y~ (thỏa ~1 \leq x, y \leq n~ và ~x \neq y~), máy chấm sẽ cho biết ~p_x < p_y~ hay ~p_x > p_y~.
Điểm số của thí sinh sẽ là tối đa nếu số lượng câu hỏi ít hơn số câu hỏi mà giám khảo sử dụng; ngược lại, thí sinh càng sử dụng ít câu hỏi hơn sẽ càng nhận được điểm số cao hơn.
Giới hạn:
~1 \leq n \leq 1000~
Lời giải
Ý Tưởng
Bài toán trên có thể được đưa về tìm phần tử lớn thứ ~k~ trong một mảng giá trị với thứ tự bất kì. Cụ thể hơn, nếu ta gọi ~B~ là phần tử lớn thứ ~k~ trong mảng ~n~ phần tử được cho, ~k - 1~ phần tử lớn nhất còn lại (từ phẩn tử lớn thứ nhất đến phần tử lớn thứ ~k - 1~) có thể được xác định bằng cách so sánh giá trị ~B~ với ~n - 1~ phần tử còn lại:
Nếu phần tử ~A~ lớn hơn ~B~ thì ~A~ là một trong ~k~ giá trị lớn nhất.
Ngược lại, ~A~ thuộc tập ~n - k~ giá trị còn lại.
Để có thể xác định được giá trị ~B~, chúng ta cần phải thực hiện ít nhất ~\Omega(n)~ phép so sánh bởi mỗi phần tử còn phải được tham gia vào ít nhất một phép so sánh và mỗi phép so sánh chỉ có thể xác định mối quan hệ giữa hai phần tử.
Một thuật toán mà ta có thể dùng để tìm được giá trị ~B~ nêu trên là thuật toán Quickselect. Thuật toán có thể được miêu tả như sau:
Cho một mảng ~P~ gồm các phần tử phân biệt và một số nguyên ~k~; mục tiêu là tìm phần tử lớn thứ ~k~ trong ~P~.
Chọn một phần tử làm pivot từ mảng ~P~, sau đó phân hoạch mảng thành hai tập con:
~L~ là tập gồm các phần tử lớn hơn pivot; và
~R~ là tập gồm các phần tử nhỏ hơn pivot.
Khi đó:
Nếu ~k \leq |L|~, bài toán tương đương với việc tìm phần tử lớn thứ ~k~ trong ~L~.
Nếu ~k = |L| + 1~, kết quả bài toán sẽ là pivot.
Nếu ~k > |L| + 1~, bài toán tương đương với việc tìm phần tử lớn thứ ~k - |L| - 1~ trong ~R~.
Việc xác định ~k - 1~ phần tử còn lại có thể được thực hiện với ~O(n)~ thao tác so sánh như đã đề cập ở phần trên. Vì vậy, trong trường hợp trung bình, ý tưởng nêu trên sẽ có giá trị kỳ vọng của số thao tác sử dụng là ~O(n)~, gần tương ứng với cận dưới của số thao tác tối thiểu phải sử dụng nêu trên.
Cài Đặt
Sau khi xác định phần tử lớn thứ ~k~, ta có thể không cần so sánh giá trị này với từng phần tử trong ~n - 1~ phần tử còn lại để tìm ~k - 1~ phần tử lớn nhất tiếp theo. Điều này là bởi ~k - 1~ phần tử đó có thể được xác định cùng lúc với khi ta thực hiện chia tập trong quá trình tìm kiếm phần tử lớn thứ ~k~.
Cụ thể hơn, nếu ta đặt ~X(P, k)~ là tập hợp ~K~ phần tử lớn nhất của tập hợp ~P~ gồm các giá trị phân biệt. Nếu ta chia ~P~ thành hai tập ~L~ và ~R~ theo pivot được định nghĩa như trên, ~X(P, k)~ có thể được xác định một cách đệ quy như sau:
Nếu ~k > |L| + 1~, ~X(P, k) = L \cup \{\text{pivot}\} \cup X(R, k - |L| - 1)~
Dù xác suất để thuật toán nêu trên thực hiện số lượng phép so sánh gần với ~O(n^2)~ là thấp nhưng số lượng này vẫn có thể nhiều hơn số lượng thao tác mà giám khảo để sử dụng. Để có thể đặt được số điểm tối đa ở mỗi test, ta có thể cần phải thử nhiều seed khác nhau cho việc sinh số giả ngẫu nhiên cho đến khi đặt số điểm tối đa toàn bộ test.
Code C++ minh họa
#include<bits/stdc++.h>usingnamespacestd;constexprintMAX_N=1'003;namespaceInteractor{intqueryResults[MAX_N][MAX_N];intquery(constintx,constinty){if(x==y)returnx;intresult=0;cout<<'?'<<' '<<x<<' '<<y<<endl;cin>>result;returnresult;}intgetQueryResult(constintx,constinty){returnqueryResults[x][y]?queryResults[x][y]:(queryResults[x][y]=queryResults[y][x]=query(x,y));}boolcheckSmaller(constintx,constinty){returngetQueryResult(x,y)==y;}boolcheckGreater(constintx,constinty){returngetQueryResult(x,y)==x;}intfindMaximum(constintx,constinty){returncheckGreater(x,y)?x:y;}intfindMinimum(constintx,constinty){returncheckSmaller(x,y)?x:y;}intfindMaximum(constvector<int>&indices){intresult=indices.front();for(constint&i:indices){if(i==result)continue;result=findMaximum(result,i);}returnresult;}intfindMinimum(constvector<int>&indices){intresult=indices.front();for(constint&i:indices){if(i==result)continue;result=findMinimum(result,i);}returnresult;}voidprintAnswer(constvector<int>&indices){cout<<'!'<<' '<<1<<' '<<1<<endl;for(constauto&i:indices)cout<<i<<' ';cout<<endl;exit(0);}}template<classT>vector<T>operator+(vector<T>a,constvector<T>&b){a.insert(a.end(),b.begin(),b.end());returna;}template<classT>vector<T>operator-(vector<T>a,constvector<T>&b){constunordered_set<T>s(b.begin(),b.end());intlength=0;for(constauto&value:a)if(s.find(value)==s.end())a[length++]=value;a.resize(length);returna;}intgetRandomInteger(constintn){returnrand()%n;}intgetRandomSample(constvector<int>&values){returnvalues[getRandomInteger(values.size())];}vector<int>getRange(constintl,constintr){vector<int>indices(r-l);iota(indices.begin(),indices.end(),l);returnindices;}vector<int>getShuffledList(vector<int>values){random_shuffle(values.begin(),values.end());returnvalues;}pair<vector<int>,vector<int>>partitionList(constvector<int>&values,constintpivot){vector<int>left,right;for(constint&value:values){if(value==pivot)continue;(Interactor::checkSmaller(value,pivot)?left:right).push_back(value);}returnmake_pair(left,right);}classQuickSelect{private:constintn;vector<int>runRecursion(constvector<int>&indices,constintk)const{if(k==1)returnindices;constintindexCount=indices.size(),R=indexCount-k+1;if(R==1)returnvector<int>(1,Interactor::findMaximum(indices));constintL=indexCount-R;if(L==1)returnindices-(vector<int>(1,Interactor::findMinimum(indices)));constintpivot=getRandomSample(indices);constauto&[left,right]=partitionList(indices,pivot);constintm=left.size()+1;if(m<k)returnrunRecursion(right,k-m);constvector<int>includedIndices=(vector<int>(1,pivot))+right;return(m==k)?includedIndices:(runRecursion(left,k)+includedIndices);}public:QuickSelect(constintn):n(n){};vector<int>operator()(constintk)const{returnrunRecursion(getShuffledList(getRange(1,n+1)),n-k+1);}};intmain(){intn=0,k=0;cin>>n>>k;srand((k<=400)?((n^k)+(n&k)):((n^k)+n+k));// Update this seed until all tests passedInteractor::printAnswer(QuickSelect(n)(k));return0;}
Độ Phức Tạp
Các bước xử lý chính của một cách cài đặt cho ý tưởng nêu trên sẽ có có độ phức tạp thời gian tương ứng với số lượng thao tác sử dụng, tức:
~O(n)~ trong trường hợp trung bình; và
~O(n^2)~ trong trường hợp tệ nhất.
Về độ phức tạp bộ nhớ, tùy vào cách cài đặt mà ta có thể có độ phức tạp ~O(n)~ hoặc ~O(n^2)~.
Một Số Ý Tưởng Khác
Ngoài ra ý tưởng nêu trên để giải bài toán, ta có thể xem xét một số ý tưởng khác. Tuy nhiên, những ý tưởng này có thể không đạt toàn bộ số điểm cho mọi test.
Tuy nhiên so với thuật toán quickselect nêu trên, ý tưởng sử dụng sắp xếp này có thể sử dụng số lượng thao tác lớn hơn nhiều lần trong nhiều trường hợp.
Heap
Ta có thể duyệt qua từng phần tử và sử dụng một min-heap để lưu tối đa ~k~ phần tử lớn nhất trong các phần tử đã duyệt qua.
Cụ thể hơn, khi duyệt qua một phần tử, ta thêm phần tử đó vào heap và loại bỏ phần tử nhỏ nhất khỏi heap nếu heap có nhiều hơn ~k~ phần tử.
Mỗi lần thêm một phần tử vào heap hoặc xóa phần tử nhỏ nhất khỏi heap, ta sẽ thực hiện tối đa ~O(\log k)~ thao tác (vì trong trường hợp này, số lượng phần tử tối đa của heap là ~O(k)~).
Vì vậy, ý tưởng này sử dụng ~O(n \log k)~ thao tác trong trường hợp tệ nhất.
Để giảm số thao tác sử dụng, nếu ~k > \frac{n}{2}~, ta có thể tìm ~n - k~ phần tử nhỏ nhất (bằng cách sử dụng max-heap) thay vì tìm ~k~ phần tử lớn nhất trực tiếp.
Tuy nhiên, cách này chỉ giúp giảm nếu xét về mặt hằng số, số lượng thao tác sẽ vẫn là ~O(n \log k)~.
Cũng tương tự như ý tưởng dùng thuật toán sắp xếp, ý tưởng dùng heap này có thể sử dụng số lượng thao tác lớn hơn nhiều lần trong nhiều trường hợp, đặc biệt khi ~k~ càng gần với giá trị ~\frac{n}{2}~.
Biến Thể của Quickselect
Một số biến thể khác của thuật toán quickselect có thể được xem xét cho bài toán này. Điểm khác nhau chính giữa các biến thể này chủ yếu ở cách chọn pivot.
Median of Medians
Thay vì chọn pivot là một phần tử ngẫu nhiên như ý tưởng được ở phần trên, ta ước tính trung vị của mảng được cho với phương pháp median of medians rồi dùng trung vị này làm pivot.
Để ước tính trung vị, phương pháp median of medians chia mảng thành các block gồm tối đa ~5~ phần tử liên tiếp và tìm trung vị của từng block. Trung vị của mảng được cho sẽ được ước lượng bằng trung vị của các trung vị của các block.
Để tìm trung vị của các trung vị của các block, ta có thể tiếp tục sử dụng thuật toán quickselect để tìm phần tử lớn thứ ~\frac{n}{10}~ trong các trung vị của block (vì ta có ~\frac{n}{5}~ block, phần tử lớn thứ ~\frac{n}{5} \cdot \frac{1}{2} = \frac{n}{10}~ sẽ là phần tử gần trung vị của toàn bộ mảng).
Trong trường hợp trung bình và tệ nhất, thuật toán này sử dụng ~O(n)~ thao tác so sánh. Tuy nhiên, so với cách chọn pivot là một phần tử ngẫu nhiên, yếu tố hằng số trong việc phân tích số lượng thao tác là lớn hơn nhiều. Vì vậy, cách dùng phương pháp median of medians có thể có số lượng thao tác sử dụng lớn hơn số lượng giám khảo sử dụng trong khi cách chọn ngẫu nhiên lại ít hơn.
Thuật toán Floyd–Rivest
Một thuật toán khác có thể được xem xét là thuật toán Floyd–Rivest. So với cách chọn pivot là phần tử ngẫu nhiên hoặc trung vị ước lượng, thuật toán Floyd–Rivest có thể có cách cài đặt phức tạp hơn.
Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.
Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.
Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng
Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.
Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.
Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.
Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!
Coding Challenge #7
Coding Challenge #7 có tên là Tổng mod. Đây là bài toán truy vấn yêu cầu thí sinh phải vận dụng được kỹ thuật đường quét và các cấu trúc dữ liệu cần thiết để xây dựng lời giải. Bài toán Tổng mod đã được 334 thí sinh thử sức và có 10 lời giải xuất sắc đạt được số điểm tối đa.
Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi 2 lời giải xuất sắc do bạn Nguyễn Hoàng Minh (lời giải 1) và Lê Minh Tuấn (lời giải 2) biên soạn.
Đề bài
Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.
Cho dãy ~a~ gồm ~n~ phần tử và ~q~ truy vấn có dạng:
Cho hai số nguyên ~l, r~, tính tổng sau:
~\sum_{i=l}^r a_i \bmod (i - l + 1)~
Giới hạn:
~1 \leq n, q \leq 2 \cdot 10^5~
~1 \leq a_i \leq 2 \cdot 10^5~
Lời giải 1
Subtask 1
Giới hạn: ~n, q \le 7000~
Ý Tưởng
Ta đặt tổng cần tìm cho mỗi truy vấn như sau:
~S(l, r) = \sum_{i=l}^{r}\left(a_i \bmod \left(i - l + 1\right)\right)~
Với giới hạn nhỏ của ~n~ và ~q~ được cho, subtask 1 cho phép chúng ta có thể xử lý từng truy vấn ~(l, r)~ và tính ~S(l, r)~ bằng cách duyệt qua các vị trí từ ~l~ tới ~r~ và trực tiếp tính ~S(l, r)~ theo định nghĩa như trên.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot q)~ bởi ta sẽ duyệt qua ~O(q)~ truy vấn và với mỗi truy vấn, ta duyệt qua ~O(n)~ vị trí để tính tổng ~S~.
Với giới hạn thời gian được cho (~2.5~ giây), chương trình được cài đặt theo ý tưởng nêu trên có thể chạy trong thời gian cho phép.
Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta cần lưu ~O(n)~ phần tử của mảng ~a~ được cho.
Ta có thể viết lại công thức tính tổng cần tìm như sau:
~S(l, r) = \sum_{m = 1}^{r - l + 1}\left(a[l + m - 1] \bmod m\right)~
Ta nhận thấy rằng với hai số nguyên dương ~x~ và ~y~ bất kì, nếu ~x < y~, ta có: ~x \bmod y = x~.
Nếu ta đặt ~A~ là giá trị lớn nhất mà một phần tử của mảng ~a~ có thể có (~A = 200~ trong subtask 2), với một truy vấn ~(l, r)~ mà ~r - l + 1 > A~, ta có:
~S(l, r) = \sum_{m = 1}^{A}\left(a[l + m - 1] \bmod m\right) + \sum_{m = A + 1}^{r - l + 1}\left(a[l + m - 1] \bmod m\right)~
Dựa vào tính chất đề cập được nêu trên, ta có:
~S(l, r) = \sum_{m = 1}^{A}\left(a[l + m - 1] \bmod m\right) + \sum_{m = A + 1}^{r - l + 1}\left(a[l + m - 1]\right)~
Ta nhận thấy rằng, việc tính thành phần tổng mà không phải xét tới phép chia lấy dư tương đương với việc tính tổng các phẩn tử của một mảng con liên tiếp. Vì dãy số ~a~ không thay đổi trong suốt quá trình trả lời truy vấn, ta có thể tính thành phần này bằng cách dùng mảng cộng dồn.
Cụ thể hơn, nếu ta đặt ~P[x] = \sum_{i = 1}^{x}a[i]~ là tổng các phần tử của dãy số ~a~ từ vị trí ~1~ đến vị trí ~x~, ta có:
~\sum_{m = A + 1}^{r - l + 1}\left(a[l + m - 1]\right) = P[r] - P[l + A - 1]~
Mặt khác, giới hạn ~A~ của subtask 2 cho phép ta tính thành phần phải sử dụng đến phép chia lấy dư (thành phần ~\sum_{m = 1}^{A}(a[l + m - 1] \bmod m)~ trong công thức trên) bằng cách duyệt qua từng vị trí như trong subtask 1.
Tương tự, nếu ~r - l + 1 \leq A~, ta có thể tính tổng ~S(l, r)~ như trong subtask 1.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(n + q \cdot A)~ bởi:
Ta cần đọc dữ liệu dãy số ~a~ với ~O(n)~ phần tử và có thể tính mảng cộng dồn với độ phức tạp ~O(n)~.
Với mỗi truy vấn ~(l, r)~, vì tổng các phần tử liên tiếp có thể được tính trong ~O(1)~ sau khi đã xây dựng mảng cộng dồn và ta có thể chỉ cần duyệt thêm qua tối đa ~O(A)~ vị trí để thực hiện việc tính tổng ~S(l, r)~, việc xử lý mỗi truy vấn có thể được thực hiện với độ phức tạp ~O(A)~.
Vì ta có ~O(q)~ truy vấn, việc xử lý hết tất cả truy vấn có thể thực hiện với độ phức tạp ~O(q \cdot A)~.
Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta có thể chỉ cần lưu thêm mảng cộng dồn với ~O(n)~ phần tử so với subtask 1.
Vì biên trái của mọi truy vấn trong subtask 3 luôn nằm ở vị trí cuối cùng, vỡi mỗi vị trí ~i~, phần tử ~a[i]~ sẽ có đóng góp vào tổng ~S(l, r)~ nếu ~l \leq i~ (~r = n~).
Để giải quyết subtask này, ta có thể phân tích xem, với một vị trí ~i~, ~a[i]~ có đóng góp như thế nào tới các tổng ~S(j, n)~ với ~1 \leq j \leq n~.
Nếu ~x~ và ~y~ là hai số nguyên dương, ta có:
~x \bmod y = x - y \cdot \lfloor \frac{x}{y} \rfloor~
Áp dụng điều này vào ~S(l, r)~, ta có:
~
\begin{align}
S(l, r)
&= \sum_{m = 1}^{r - l + 1}
\left(a[i + m - 1] - m \cdot \left\lfloor \frac{a[i + m - 1]}{m} \right\rfloor \right) \\
&= \sum_{m = 1}^{r - l + 1} a[i + m - 1] - \sum_{m = 1}^{r - l + 1} \left( m\cdot \left\lfloor \frac{a[i + m - 1]}{m} \right\rfloor \right) \\
&= \sum_{i = l}^{r} a[i] - \sum_{m = 1}^{r - l + 1} \left( m \cdot \left\lfloor \frac{a[i + m - 1]}{m} \right\rfloor \right)
\end{align}
~
Tương tự như subtask 2, thành phần ~\sum_{i = l}^{r}a[i]~ có thể được tính hiệu quả bằng cách sử dụng mảng cộng dồn. Bài toán con còn lại ta phải giải quyết là làm sao để tính thành phần ~\sum_{m = 1}^{r - l + 1} \left(m \cdot \left\lfloor \frac{a[i + m - 1]}{m} \right\rfloor \right)~ một cách hiệu quả.
Để dễ mô tả phần còn lại của ý tưởng, ta sẽ đặt ~b[i][j] = \left(j - i + 1\right) \left\lfloor \frac{a[i]}{j - i + 1} \right\rfloor~ với ~i, j~ là hai số tự nhiên sao cho ~1 \leq i \leq j \leq n~. Đồng thời, ta đặt ~B[i][j] = \sum_{z = i}^{j}b[i][z]~. Như vậy, với một truy vấn ~(l, r)~, ta cần xác định giá trị ~B[l][r]~.
Ta nhận thấy rằng với một số nguyên dương cố định ~x~ và một số nguyên dương ~y~, giá trị ~\left\lfloor \frac{x}{y} \right\rfloor~ chỉ có thể có tối đa ~O(\sqrt x)~ khác nhau.
Giải thích
Với ~y \leq \sqrt x~, ta chỉ có tối đa ~O(\sqrt x)~ giá trị khác nhau cho ~\lfloor \frac{x}{y} \rfloor~ bởi:
Mỗi giá ~y~ sẽ chỉ dẫn tới một giá trị ~\lfloor \frac{x}{y} \rfloor~;
Ta có tối đa ~O(\sqrt x)~ giá trị ~y~.
Với ~y > \sqrt x~, ta có ~\frac{x}{y} < \sqrt x~. Vì vậy, ~\lfloor \frac{x}{y} \rfloor < \sqrt x~ (vì ~\lfloor \frac{x}{y} \rfloor \leq \frac{x}{y}~). Mặt khác, vì ~\lfloor \frac{x}{y} \rfloor~ là số nguyên, ~\lfloor \frac{x}{y} \rfloor~ chỉ cũng có thể có tối đa ~O(\sqrt x)~ giá trị khác nhau trong trường hợp này.
Dựa trên điều này, ta nhận thấy rằng với một vị trí ~i~, ta có thể phân các vị trí từ ~1~ đến ~i - 1~ thành ~O\left(\sqrt {a[i]}\right)~ nhóm gồm các phân tử liên tiếp trong ~b~ sao cho hiệu giữa hai phần tử liên tiếp là như nhau.
Ví dụ
Giả sử tại vị trí ~67~, giá trị của ~a[67]~ là ~24~. Khi này, với ~m~ là số tự nhiên, ta có:
Ta đặt ~s[i] = S(i, r)~, tức mỗi truy vấn ~(l, r)~ trong subtask 3 sẽ có kết quả là ~s[l]~. Dựa trên phân tích trên, các giá trị ~s[i]~ có thể được tính như sau:
Ban đầu, với mọi vị trí ~i~, ~s[i] = 0~
Với mỗi vị trí ~i~, ta sẽ thực hiện ~O\left(\sqrt{a[i]}\right)~ truy vấn cập nhật bậc thang trên ~s[i]~ với mỗi truy vấn cập nhật bậc thang sẽ tương đương với một nhóm đề cập như trên.
Cụ thể hơn, mỗi truy vấn có thể được đại diện bởi bốn số nguyên ~(l, r, x, y)~, mang ý nghĩa như sau:
Ta cần tăng ~s[r]~ thêm ~x~;
Ta cần tăng ~s[r - 1]~ thêm ~x + y~;
...
Ta cần tăng ~s[l]~ thêm ~x + y \times (r - l)~.
Ví dụ
Nếu ta quay trở lại ví dụ trên, một số truy vấn cập nhật ta phải thực hiện sẽ là:
~(56, 58, 18, 2)~: Ta cần tăng các phần tử ~s~ từ ~56~ tới ~58~ với giá trị ở vị trí trái nhất là ~18~ và step là ~2~.
~(44, 55, 14, 1)~: Ta cần tăng các phần tử ~s~ từ ~44~ tới ~55~ với giá trị đầu tiên là ~14~ và step là ~1~.
...
Vì ta không phải thực hiện các truy vấn cập nhật online, ta có thể tính giá trị ~s~ bằng một cách xử lý offline với mảng hiệu:
Ta đặt ~D_2[i]~ là giá trị của mảng hiệu đại diện tổng hiệu các step của các truy vấn cập nhật có bao gồm vị trí ~i~.
Ta đặt ~D_1[i]~ là tổng các thay đổi cho các truy vấn bắt đầu hoặc kết thúc tại ~i~.
Độ Phức Tạp
Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O\left(q + n \cdot \sqrt{A}\right)~ với ~A~ là giá trị lớn nhất của mảng ~a~.
Ta cần duyệt qua ~O(n)~ vị trí và với mỗi vị trí, ta cần duyệt qua ~O\left(\sqrt{a}\right)~ truy vấn cập nhật. Việc cập nhật hai ~D_1~ và ~D_2~ nêu trên cho mỗi truy vấn có độ phức tạp ~O(1)~.
Ta cần duyệt qua ~O(n)~ vị trí để tính mảng ~s~ với mỗi vị trí có thể được xử lý trong ~O(1)~.
Ta cần duyệt qua ~O(q)~ truy vấn để xử lý các truy vấn. Mỗi truy vấn có thể được xử lý trong ~O(1)~ sau khi đã thực tính mảng ~s~ trên.
Xét với độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta có thể chỉ cần lưu thêm mảng hiệu với ~O(n)~ phần tử so với subtask 2.
Để mở rộng hướng giải quyết của subtask 3 cho subtask 4, ta nhận thấy rằng để nếu ta đã tính được ~B[l][r]~ quả cho truy vấn ~(l, r)~ và mảng hiệu ~D_1~ và ~D_2~ nếu chỉ xét các vị trí từ ~1~ tới ~r~, ta có thể mở rộng hoặc thu hẹp biên ~l~ và ~r~ như sau:
Để xử lý cho truy vấn ~(l - 1, r)~, ta chỉ cần dựa vào ~B[l][r]~, ~D_1[l - 1]~ và ~D_2[l - 1]~ để xác định giá trị ~B[l - 1][r]~ (mảng ~D_1~ và ~D_2~ giữ nguyên).
Tương tự, để xử lý cho truy vấn ~(l + 1, r)~, ta chỉ cần dựa vào ~B[l][r]~, ~D_1[l]~ và ~D_2[l]~ để xác định giá trị ~B[l + 1][r]~ (mảng ~D_1~ và ~D_2~ giữ nguyên).
Để xử lý cho truy vấn ~(l, r + 1)~, ta có thể tính ~b[l][r + 1]~ để cùng với giá trị ~B[l][r]~ tính giá trị ~B[l][r + 1]~.
Đồng thời, để cập nhật mảng ~D_1~ và ~D_2~, ta cần duyệt qua mọi truy vấn cập nhật tạo bởi vị trí ~r + 1~.
Để xử lý cho truy vấn ~(l, r - 1)~, ta có thể tính ~b[l][r]~ để cùng với giá trị ~B[l][r]~ tính giá trị ~B[l][r - 1]~.
Đồng thời, để cập nhật mảng ~D_1~ và ~D_2~, ta cần duyệt qua mọi truy vấn cập nhật tạo bởi vị trí ~r~.
Ta nhận thấy rằng trong cả bốn trường hợp nêu trên, việc tính giá trị ~B~ mới có thể được xử lý ~O(1)~. Vì vậy, việc mở rộng hoặc thu hẹp biên biên trái (bởi một đơn vị) có thể được xử lý trong ~O(1)~.
Tuy nhiên, việc mở rộng hoặc thu hẹp biên phải (bởi một đơn vị) có thể yêu cầu độ phức tạp ~O\left(\sqrt{A}\right)~ bởi ta sẽ cập nhật ~D_1~ và ~D_2~ theo cách trên.
Nếu ta giả định việc duyệt qua các thao tác cập nhật là các thao tác tối thiểu, ta có thể xem xét áp dụng thuật toán Mo bởi:
Độ phức tạp thời gian sẽ là ~O\left(n \sqrt{A} + (n + q) \sqrt{n} Z \right)~ với ~O(Z)~ là độ phức tạp của việc mở rộng hoặc thu hẹp một trong hai biên. Vì vậy, nếu ta xử lý việc thay đổi biên đủ hiệu quả, thời gian chạy của chương trình vẫn có thể trong giới hạn cho phép.
Ta có thể trả lời các truy vấn một cách offline.
Việc gộp hai cấu trúc dữ liệu (giá trị ~B~ của biên đang xét, mảng ~D_1~ và ~D_2~ được định nghĩa như trên) có thể phức tạp, không đáp giới hạn được đề ra.
Một cách sắp xếp xử lý truy vấn để có thể áp dụng thuật toán Mo là ta sắp xếp theo chỉ số block của biên ~l~ giảm dần và biên ~r~ giảm dần nếu chỉ số block của biên ~l~ là giống nhau.
Cách sắp xếp này có thể giúp ý tưởng có độ phức tạp trong giới hạn cho phép bởi giữa hai truy vấn có biên phải trong cùng một block:
Ta sẽ đi qua tối đa ~O\left(\sqrt{n}\right)~ vị trí khi thay đổi biên trái. Mặt khác, việc cập nhật giá trị ~B~ khi chỉ thay đổi biên phải là ~O(1)~ như đã đề cập trước đó.
Khi thay đổi (giảm) biên phải, ta sẽ duyệt qua các truy vấn cập nhật có ít nhất một vị trí nằm trong block đang xét. Độ phức tạp cho một lần giảm biên phải như vậy sẽ là ~O\left(\sqrt A\right)~.
Ta có thể đưa ra nhận xét là với một vị trí ~r~, tổng số truy vấn cập nhật ta phải duyệt qua khi giảm ở biên phải đang ở vị trí ~r~ là ~O\left(\sqrt{n \cdot A}\right)~. Tuy nhiên, ta có thể có một nhận xét chặt hơn: số lượng thật sự sẽ là ~O\left(\sqrt{A} + \sqrt{n}\right)~ bởi:
Các truy vấn cập nhật cho giá trị ~a[r]~ không có chung vị trí giữa chúng;
Ở mỗi block, ta chỉ duyệt qua các truy vấn cập nhật có ít nhất một vị trí trong block như đã đề cập ở trên.
Độ Phức Tạp
Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O\left(n\sqrt{A} + (n + q)\sqrt{n}\right)~ bởi:
Độ phức tạp của bước xử lý chính của thuật toán Mo sẽ là ~O\left(n \sqrt{A} + (n + q)\sqrt{n}\right)~ dựa trên phân tích đề cập trong phần trước:
Ta sẽ thay đổi biên trái ~l~ tối đa ~O\left(q \sqrt {n} \right)~ lần khi duyệt hết ~q~ truy vấn và độ phức tạp cho mỗi lần thay đổi là ~O(1)~.
Tổng độ phức tạp cho việc thay đổi biên phải ~r~ sau khi duyệt ~q~ truy vấn là ~O\left(n(\sqrt{A} + \sqrt{n})\right)~ vì ta có ~O(n)~ vị trí cho biên phải và tổng phức tạp cho bước xử lý một vị trí biên phải là ~O\left(\sqrt{A} + \sqrt{n}\right)~ như đã đề cập ở trên.
Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n + q)~ bởi ta có thể chỉ cần lưu thêm các chỉ số của truy vấn với ~O(q)~ phần tử so với subtask 3 để có thể sắp xếp và xử lý theo một thứ tự nhất định.
Code Minh Họa
Khi cài đặt ý tưởng, chúng ta nên cố gắng tránh sử dụng phép chia nhiều nhất có thể bởi phép chia có thể làm chậm chương trình (nếu số chia không phải là một hằng số có thể xác định khi biên dịch chương trình, phép chia có thời gian thực thi chậm hơn đáng kể so với phép cộng, trừ, hoặc nhân).
Code C++ minh họa
#include<bits/stdc++.h>usingnamespacestd;constexprintMAX_N=200'005,MAX_Q=200'005;intn,q,a[MAX_N],l[MAX_Q],r[MAX_Q];namespaceFourthSubtask{constexprintBLOCK_SIZE=447,BLOCK_COUNT=450;longlongresults[MAX_Q],prefixSums[MAX_N],d[MAX_N][2];intqueryIndices[MAX_Q],ranges[MAX_N][3];voidsortQueries(){inti=0,lefts[n+1]{},indices[q+1]{};/** Sort by ascending L **/for(i=1;i<=q;++i)++lefts[l[i]+1];for(i=1;i<=n;++i)lefts[i]+=lefts[i-1];for(i=1;i<=q;++i)queryIndices[++lefts[l[i]]]=i;/** Sort by ascending R **/for(i=1;i<=n;++i)lefts[i]=0;for(i=1;i<=q;++i)++lefts[r[i]+1];for(i=1;i<=n;++i)lefts[i]+=lefts[i-1];for(i=1;i<=q;++i)indices[++lefts[r[queryIndices[i]]]]=queryIndices[i];/** Sort by descending block ID of L **/for(i=1;i<=n;++i)lefts[i]=0;for(i=1;i<=q;++i)++lefts[n-(l[i]-1)/BLOCK_SIZE+1];for(i=1;i<=n;++i)lefts[i]+=lefts[i-1];for(i=1;i<=q;++i)queryIndices[++lefts[n-(l[indices[i]]-1)/BLOCK_SIZE]]=indices[i];}voidsolve(){longlongsum=0,change=0;inti=1;sortQueries();for(;i<=n;++i){prefixSums[i]=prefixSums[i-1]+a[i];ranges[i][0]=ranges[i][2]=1;ranges[i][1]=a[i];}i=1;for(intblockLeft=(n-1)/BLOCK_SIZE*BLOCK_SIZE+1,blockRight=n,start=0,last=0,left=0,delta=0,right=0,t=0,value=0,rangeLeft=0,rangeRight=0,queryLeft=0,queryRight=0;blockLeft>=1&&i<=q;blockRight=blockLeft-1,blockLeft-=BLOCK_SIZE){sum=change=0;start=blockLeft;last=start-1;for(;i<=q;++i){t=queryIndices[i];queryLeft=l[t];if(queryLeft<blockLeft)break;queryRight=r[t];while(queryLeft<start){--start;change+=d[start][1];sum+=d[start][0]+change;}for(;start<queryLeft;++start){sum-=d[start][0]+change;change-=d[start][1];}for(queryRight=r[t];last<queryRight;){++last;left=ranges[last][0];value=a[last];if(left>value)continue;delta=ranges[last][1];right=ranges[last][2];while(true){rangeRight=last-left+1;if(rangeRight<blockLeft)break;rangeLeft=max(last-right,0);if(rangeLeft<blockRight){/** (rangeLeft, rangeRight] **/if(rangeLeft<start&&start<=rangeRight){sum+=delta*(last-start+1);change+=delta;}if(rangeRight<=blockRight){d[rangeRight][0]+=delta*(last-rangeRight);d[rangeRight][1]+=delta;}if(rangeLeft<blockLeft)break;d[rangeLeft][0]-=delta*(last-rangeLeft);d[rangeLeft][1]-=delta;}left=right+1;if(left>value)break;delta=value/left;right=value/delta;}ranges[last][0]=left;ranges[last][1]=delta;ranges[last][2]=right;}results[t]=prefixSums[r[t]]-prefixSums[l[t]-1]-sum;}}for(i=1;i<=q;++i)cout<<results[i]<<'\n';}}voidinput(){cin>>n>>q;for(inti=1;i<=n;++i)cin>>a[i];for(inti=1;i<=q;++i)cin>>l[i]>>r[i];}signedmain(){#ifdef LOCALfreopen("input.INP","r",stdin);#endif // LOCALcin.tie(0)->sync_with_stdio(0);cout.tie(0);input();FourthSubtask::solve();return0;}
Lời giải 2
Subtask 1: ~n, q \le 7000~
Ta chỉ cần làm đúng những gì đề bảo. Với mỗi truy vấn, ta duyệt từ ~l~ đến ~r~, và cộng giá trị ~a_i \bmod (i-l+1)~ vào biến kết quả. Độ phức tạp ~\mathcal{O}(q \cdot n)~.
Nhận xét: ~x \bmod y = x~ nếu ~x < y~.
Đặt ~k = i - l + 1~ là số chia. Với mỗi truy vấn ~[l, r]~, ta chia làm 2 phần:
Với ~k \le 200~ (tương ứng với 200 phần tử đầu tiên của đoạn, tức ~i \in [l, \min(r, l+199)]~), ta tính trực tiếp tổng ~a_i \bmod k~ bằng cách duyệt như subtask 1.
Với ~k > 200~, do ~a_i \le 200~ nên ~a_i < k~, suy ra ~a_i \bmod k = a_i~. Phần này ta có thể tính nhanh bằng prefix sum.
Độ phức tạp: ~\mathcal{O}(q \cdot 200)~. Trong cài đặt mẫu dưới đây, tác giả sử dụng Sparse Table để tìm max đoạn ~[l,r]~ nằm tối ưu thời gian chạy với những test có ~\max a~ nhỏ hơn. Còn trên thực tế, ta duyệt đến ~l+200~ vẫn đủ để qua được subtask này.
Phần tổng ~a_i~ cố định có thể tính bằng Prefix Sum. Lời giải sau đây chỉ quan tâm đến việc tính tổng ở vế sau (~\sum_{i=l}^{n} (i-l+1) \left\lfloor \frac{a_i}{i-l+1} \right\rfloor~).
Nhận xét:
Chỉ có tối đa ~2\sqrt{n}~ giá trị ~\lfloor \frac{n}{c} \rfloor~ phân biệt.
Nếu ~c \le \sqrt{n}~, rõ ràng số lượng giá trị phân biệt tương ứng với số lượng số ~c~, là ~\sqrt{n}~
Nếu ~c > \sqrt{n}~, thì ~\lfloor \frac{n}{c} \rfloor~ chỉ nhận các giá trị nguyên từ ~1~ đến ~\sqrt{n}~.
Tổng lại ta có số lượng giá trị phân biệt tối đa là ~2\sqrt{n}~.
Các giá trị ~c~ có cùng kết quả khi tính ~\lfloor \frac{n}{c} \rfloor~ nằm trên một đoạn liên tiếp của trục số.
Điều này là dễ thấy dựa vào tính chất đơn điệu của ~\lfloor \frac{n}{c} \rfloor~.
Từ các nhận xét trên, ta có thể rút ra một cách làm offline cho subtask này. Thay vì duyệt đoạn ~[l,n]~ để trả lời truy vấn, ta duyệt từng phần tử ~a_i~, và xem nó đóng góp bao nhiêu vào kết quả. Nhận thấy ~a_i~ sẽ đóng góp vào các truy vấn ~[l,n]~ với ~l \le i~.
Xét một phần tử ~a_i~, ta duyệt các giá trị ~k = i-l+1~.
Ta duyệt các đoạn ~[u, v]~ của số chia ~k~ sao cho ~\lfloor \frac{a_i}{k} \rfloor~ có cùng giá trị là ~val~.
Từ nhận xét trên, ta thấy phần này chỉ duyệt qua ~2 \sqrt{a_i}~ giá trị khác nhau.
Ta có thể duyệt ~u~ tăng dần từ ~1~. Với mỗi ~u~, ta chặt nhị phân tìm ~v~ xa nhất sao cho ~\lfloor \frac{a_i}{u} \rfloor = \lfloor \frac{a_i}{v} \rfloor~. Sau khi tính toán xong, gán ~u \leftarrow v+1~.
Tuy nhiên độ phức tạp cho việc trên có thể lên đến ~\mathcal{O}(\sqrt{a_i} \log {a_i})~.
Ta có thể tìm ~v~ trong ~\mathcal{O}(1)~ bằng công thức ~v=\frac{a_i}{val}~. Do nếu ta có ~x~ thoả mãn ~\lfloor \frac{a_i}{x} \rfloor = val~, thì ~x \le \frac{a_i}{val}~, từ đó ta chọn được số lớn nhất mà vẫn thoả mãn điều kiện.
Với ~k \in [u, v]~, ta có ~l = i - k + 1~. Như vậy ~a_i~ sẽ đóng góp vào các truy vấn có ~l \in [i-v+1, i-u+1]~ một lượng:
~(i-l+1) \times val = (i+1) \times val - l \times val~
Như vậy ta cần xử lý các truy vấn: Trừ ~(i+1) \times val~ và cộng ~l \times val~ vào đáp án của các ~l~ trong đoạn. Đây là một bài toán cổ điển, có thể giải bằng Prefix Sum:
Duy trì 2 mảng ~D_1~ dùng để cập nhật lượng hằng số ~(i+1) \times val~, và ~D_2~ dùng để cập nhật hệ số của ~L~ tăng lên một lượng là ~val~.
Với mỗi yêu cầu tăng đoạn ~[L,R]~, ta tăng ~D_1[L]~ và giảm ~D_1[R+1]~ một lượng ~(i+1) \times val~, đồng thời tăng ~D_2[L]~ và giảm ~D_2[R+1]~ một lượng ~val~.
Cuối cùng, cộng dồn hai mảng ~D_1~ và ~D_2~, khi đó đáp án cho truy vấn ~[L,n]~ sẽ là ~D_1[L] - D_2[L] \times L~.
Độ phức tạp: ~\mathcal{O}(n\sqrt{A})~. Cài đặt mẫu:
#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;inta[N];intn,q;int64_tadd_i[N];int64_tsuff[N];int64_tadd_c[N];int64_tans[N];// a[i] += i * val_i + val_cvoidadd(intl,intr,intval_i,int64_tval_c){add_i[l]+=val_i;add_i[r+1]-=val_i;add_c[l]+=val_c;add_c[r+1]-=val_c;}intmain(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>q;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=n;i>=1;i--){suff[i]=suff[i+1]+a[i];}for(inti=1;i<=n;i++){for(intl=1;l<=a[i];){intk=a[i]/l;intr=a[i]/k;intlow=i-r+1,high=i-l+1;low=max(low,1);high=min(high,n);if(low<=high){add(low,high,k,1ll*i*k);}l=r+1;}}for(inti=1;i<=n;i++){add_i[i]+=add_i[i-1];add_c[i]+=add_c[i-1];ans[i]=add_c[i]-1ll*(i-1)*add_i[i];}while(q--){intl,r;cin>>l>>r;cout<<suff[l]-ans[l]<<'\n';}return0;}
Subtask 4: Không có giới hạn gì thêm
Ý tưởng của subtask này vẫn dựa trên việc tính đóng góp của từng phần tử ~a_i~ giống subtask 3, nhưng ~r~ thay đổi qua các truy vấn, nên ta sử dụng kỹ thuật sweepline: duyệt ~r~ từ ~1~ đến ~n~. Khi xét đến ~a_r~, ta cập nhật đóng góp của nó vào các vị trí ~l~, sau đó trả lời các truy vấn kết thúc tại ~r~.
Vì phải trả lời truy vấn online trong khi đang sweepline, ta không thể dùng mảng cộng dồn tĩnh. Thay vào đó, ta cần một cấu trúc dữ liệu hỗ trợ cập nhật điểm và truy vấn tổng tiền tố. Một trong những cấu trúc hỗ trợ là Fenwick Tree.
Cài đặt sử dụng Fenwick Tree, độ phức tạp ~\mathcal{O}(n \sqrt{A} \log n)~:
Tuy nhiên, với giới hạn ~2 \cdot 10^5~ thì thuật toán trên không thể chạy được trong thời gian cho phép. Nhận thấy bài toán có đặc thù là số lượng truy vấn cập nhật rất nhiều (~n\sqrt{A}~), nhưng số truy vấn hỏi lại ít hơn (~q~), nên ta sẽ đổi sang sử dụng một cấu trúc dữ liệu khác, hỗ trợ cập nhật nhanh nhưng truy vấn chậm hơn một chút, đó là sử dụng chia căn:
Chọn một hằng số ~B~, và chia mảng thành ~\frac{n}{B}~ đoạn.
Lưu 2 mảng: ~\text{blk}_i~ thể hiện tổng của các phần tử trong khối thứ ~i~, và ~f_i~ thể hiện giá trị của phần tử thứ ~i~. Lưu ý ta cần duy trì 2 cấu trúc riêng biệt cho ~D_1~ và ~D_2~.
Với mỗi truy vấn tăng một điểm ~i~, ta tăng ~\text{blk}_{\frac{i}{B}}~ và ~f_i~. Độ phức tạp ~\mathcal{O}(1)~.
Với mỗi truy vấn tìm tổng của ~i~ phần tử đầu tiên, ta duyệt trâu từng block theo chỉ số ~b~ tăng dần:
Nếu block hiện tại nằm bên trái ~i~, ta cộng ~\text{blk}_b~ vào kết quả.
Nếu block hiện tại chứa ~i~, ta duyệt trâu từ đầu block (~b \times B~) đến ~i~, và cộng kết quả với ~f_i~. Sau đó dừng duyệt block.
Vậy việc truy vấn mất ~\mathcal{O}(B + \frac{n}{B})~.
Để tối ưu ta chọn ~B \approx \sqrt{n}~. Độ phức tạp cho toàn bài toán chỉ còn ~\mathcal{O}(n \sqrt{A} + q \sqrt{n})~.
Tạp chí Tết: Tổng quan về CPU Hardware Acceleration
Author:
Nguyễn Tấn Minh — Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
Reviewer:
Nguyễn Minh Nhật — Georgia Institute of Technology.
Trần Xuân Bách — University of Chicago.
Nguyễn Minh Hiển — Trường Đại học Công nghệ, ĐHQGHN.
Mở đầu
The things that destroy performance tend to be things that are much easier to type, such as division operations, poor cache usage, bad instruction scheduling (which is a topic by itself), and mispredicted branches.
Trong lập trình thi đấu, đôi lúc chúng ta vẫn thường gặp những trường hợp "chỉ sửa code một chút thôi" nhưng từ một lời giải TLE đã trở thành lời giải AC. Ví dụ như:
Thêm một dòng #pragma gì đó.
Thay đổi thứ tự của một vài dòng for.
Giảm bớt bộ nhớ của các mảng lớn hay khai báo bớt mảng.
Thay (a + b) % MOD thành a + b - (a + b < MOD ? 0 : MOD).
Những "tối ưu" kiểu như vậy thường được các CP-ers gọi vui là ma thuật đen (hay thậm chí là... trick bẩn). Tuy nhiên, bất cứ điều gì xảy ra đều có nguyên nhân, và những trường hợp nêu trên cũng không phải ngoại lệ.
Trong bài viết này, chúng ta sẽ cùng mổ xẻ quá trình thực thi các chương trình xuống cấp độ bộ nhớ máy tính, tìm hiểu xem khi chạy những dòng code, điều gì đang thực sự diễn ra trên phần cứng, và từ đó giúp bạn đọc giải thích vì sao code lại chạy nhanh hay chậm hơn ở các trường hợp khác nhau.
Qua bài viết này, mình hy vọng bạn đọc sẽ có cái nhìn tổng quát hơn về việc phân tích tốc độ xử lý của một chương trình, bên cạnh các phương pháp tính độ phức tạp thông thường. Từ đó, những tối ưu kiểu như trên cũng không còn là những ma thuật đen nữa mà sẽ được chúng ta sử dụng một cách chủ động, hiệu quả và có ý đồ hơn.
Trong thi đấu và đặc biệt là kì thi ICPC, những "tối ưu" kiểu như vậy lại chính là ranh giới giữa việc một đội có thể giải thêm một bài (và leo lên thêm vài chục bậc trên bảng xếp hạng) hay không. Bản thân mình cũng đã trải nghiệm một trường hợp như vậy, và đó cũng chính là một trong những động lực không nhỏ đã giúp mình đưa bài viết này đến với mọi người trong Tạp chí Tết năm nay.
Sơ lược về phần cứng máy tính
Để hiểu hơn những gì đang thực sự diễn ra ở cấp độ bộ nhớ máy tính khi chúng ta chạy những dòng code, mình sẽ dành một phần của bài viết này để giới thiệu sơ lược về phần cứng máy tính cũng như cấu trúc bộ nhớ máy tính.
Phép đo tốc độ trong phần cứng máy tính
Tần số & Chu kỳ
Rõ ràng, với tốc độ xử lý của các thao tác trên máy tính, ta không thể tiến hành đo đạc bằng các loại đồng hồ đo thông thường. Do đó, người ta sử dụng một thiết bị đặc biệt có thể tạo ra dao động với tần số cực kỳ lớn và ổn định; tần số của thiết bị này thường được ghi ngay trên tên của bộ xử lý, ví dụ như 13th Gen Intel(R) Core(TM) i7-1355U (1.70 GHz).
Các lệnh máy sẽ được đo bằng đơn vị chu kỳ, tức thời gian để thiết bị này thực hiện một dao động. Với tần số ~f = 1.70~ GHz, ta có chu kỳ:
Nói cách khác, một chu kỳ chỉ xấp xỉ ~0.588~ nano-giây!
Trong bài viết này, chúng ta sẽ sử dụng chu kỳ làm đơn vị chính cho việc đánh giá các lệnh máy khác nhau.
Độ trễ và thông lượng
Để đánh giá tốc độ của các lệnh máy, ta thường sử dụng hai đại lượng thời gian sau:
Độ trễ (latency): Đo khoảng thời gian giữa lúc bắt đầu đến khi kết thúc lệnh.
Thông lượng (throughput): Đo khoảng thời gian giữa lúc bắt đầu đến khi có thể thực hiện lệnh cùng loại tiếp theo.
Để dễ hình dung, ta xét hai ví dụ như sau, giả sử độ trễ và thông lượng của phép chia lần lượt là ~22~ và ~8~ chu kỳ:
Khi tính ~((x / a) / b) / c~, bắt đầu tại mốc chu kỳ ~0~, do kết quả của phép tính sau phụ thuộc vào phép tính trước nên phép tính sau sẽ được thực hiện ngay sau khi hoàn thành phép tính trước. Ta sẽ thu được kết quả của ~x / a~, ~(x / a) / b~ và ~((x / a) / b) / c~ lần lượt tại chu kỳ thứ ~22, 44, 66~.
Khi tính ~x/a~, ~y/a~ và ~z/a~, bắt đầu tại mốc chu kỳ ~0~, do kết quả của ba phép tính này độc lập với nhau, chúng sẽ được bắt đầu tại chu kỳ thứ ~0, 8, 16~. Ta sẽ thu được kết quả của ~x/a~, ~y/a~ và ~z/a~ lần lượt tại chu kỳ thứ ~22, 30, 38~.
Các loại bộ nhớ cơ bản của máy tính
Việc chúng ta sử dụng nhiều loại bộ nhớ khác nhau trong máy tính đến từ một quy luật rất tự nhiên: Bộ nhớ hỗ trợ truy cập càng nhanh thì cấu trúc vi mạch và chi phí sản xuất của nó càng cao. Do đó, trong một chiếc máy tính, ta thường tích hợp nhiều loại bộ nhớ khác nhau với những vai trò khác nhau. Các loại bộ nhớ có chi phí thấp thường được trang bị nhiều giúp ta lưu trữ được nhiều dữ liệu; các loại bộ nhớ có chi phí cao hơn thường được trang bị ít hơn và được sử dụng khi cần thực hiện tính toán nhanh.
Các loại bộ nhớ thường thấy trong một máy tính theo tốc độ truy cập giảm dần bao gồm:
Register: Là phần bộ nhớ nằm ngay trên CPU, có khả năng thực hiện tính toán nhanh nhất. Một register trong các máy tính hiện nay thường có ~64~ bit; một nhân CPU có nhiều register (khoảng vài chục) cho các mục đích tính toán khác nhau.
Cache (SRAM): Là phần bộ nhớ nằm rất gần CPU, đóng vai trò là phần bộ nhớ trung gian giúp tăng tốc độ truy cập dữ liệu từ main RAM. Khi cần thực hiện phép tính, các ô nhớ được quan tâm sẽ được đưa từ cache vào register, hoặc từ main RAM vào cache rồi vào register. Ta sẽ tìm hiểu cơ chế này ở phần sau.
Main RAM (DRAM): Là phần bộ nhớ chứa các thông tin đang được hệ điều hành xử lý khi chạy các chương trình trên máy tính hay các biến trung gian phát sinh. Giới hạn bộ nhớ của main RAM hiện nay rất đa dạng và tùy thuộc vào từng dòng máy tính, có thể dao động từ ~8~ GB đến hơn ~128~ GB. Khi cần thực hiện phép tính, các ô nhớ cần quan tâm sẽ được đưa từ main RAM vào cache rồi vào register.
Secondary storage: Là phần bộ nhớ chủ yếu được sử dụng để lưu trữ như ổ đĩa cứng, bộ nhớ đám mây,... Khác với 2 loại RAM ở trên, phần bộ nhớ này sẽ không bị mất thông tin khi máy tính không được cung cấp điện. Với cấu trúc vi mạch cực kỳ đơn giản, phần bộ nhớ này có thể lưu trữ lượng thông tin lên đến nhiều TB. Khi một chương trình được khởi động, các ô nhớ tương ứng sẽ được đưa từ Secondary storage vào main RAM.
Để dễ hình dung sự khác biệt về kích thước và tốc độ truy cập của từng loại bộ nhớ, chúng ta sẽ tìm hiểu số liệu dựa trên một máy tính cá nhân qua bảng dưới. Lưu ý rằng thời gian truy cập chỉ mang tính tương đối vì thời gian thực tế phụ thuộc vào rất nhiều yếu tố khác nhau.
Phần bộ nhớ
Giới hạn bộ nhớ trong 1 nhân
Thời gian truy cập (chu kì)
Thời gian truy cập (giây, tần suất 1.7 GHz)
Register
~64~ bit ~\times~ số register
Không đáng kể
Không đáng kể
L1 cache
~80~ KB (performance) / ~96~ KB (efficiency)
~3~ chu kì
~1.76~ nano-giây
L2 cache
~1280~ KB (performance) / ~2048~ KB cho 4 nhân dùng chung (efficiency)
~9~ chu kì
~5.29~ nano-giây
L3 cache
~12~ MB cho tất cả các nhân dùng chung
~43~ chu kì
~25.28~ nano-giây
Main RAM
~8~ đến ~16~ GB
~400~ chu kì
~235.20~ nano-giây
Local Disk (SSD)
~256~ GB đến ~2~ TB
hơn ~3 \cdot 10^5~ chu kì
hơn ~170~ micro-giây
Lưu ý, có hai loại nhân là performance core và efficiency core phục vụ hai mục đích khác nhau. Do đó, cấu trúc bộ nhớ trong hai loại nhân này cũng là khác nhau.
Trong lập trình thi đấu, ta thường sử dụng giới hạn ~10^8~ hay ~2 \cdot 10^8~ như một mức ước lượng "an toàn" về số thao tác tính toán ta có thể thực hiện trong ~1~ giây. Như vậy, ta đang giả sử một phép tính trung bình mất ~5~ đến ~10~ nano-giây -- một con số tương đối phù hợp với các dòng máy hiện hành.
Cache
Có thể thấy từ số liệu trên, tốc độ truy cập và tính toán của register là nhanh hơn rất nhiều (khoảng 300 lần) so với RAM. Nếu việc lấy dữ liệu để tính toán được diễn ra trực tiếp trên RAM, ta có thể thấy đây là một sự lãng phí vô cùng lớn. Cache được tạo ra để giải quyết vấn đề này, khi register yêu cầu một vùng nhớ để thực hiện tính toán, một trong hai điều sau sẽ xảy ra:
Nếu vùng nhớ mà register cần gọi đã có sẵn trong cache, máy tính chỉ việc lấy thông tin từ phần bộ nhớ này. Ta gọi đây là cache hit.
Nếu vùng nhớ mà register cần gọi chưa có trong cache, máy tính quay về main RAM và lấy một Cache Line (tức ~64~ bytes) ghi đè lên một vùng nhớ nào đó trong cache theo một chiến lược nhất định. Ta gọi đây là cache miss.
Trong các máy tính hiện nay, cache thường được chia ra thành nhiều lớp trung gian gọi là L1, L2, L3,... nhằm tối ưu hơn nữa quá trình vận chuyển thông tin từ main RAM sang register.
Đến đây, bạn đọc cũng có thể nhận ra, cụm từ cache-friendly coding chính là việc viết code giúp máy tính hạn chế cache miss một cách tối đa.
Lệnh máy (CPU instruction)
Để thực hiện các phép tính, phép gán, biến đổi,... tất cả các code khi chạy sẽ được biến thành lệnh máy (CPU instruction). Tùy vào mỗi dòng sản phẩm CPU và các lệnh khác nhau, hiệu suất thu được cũng là khác nhau. Để đánh giá các lệnh máy cơ bản trên bộ xử lý 13th Gen Intel(R) Core(TM) i7-1355U (1.70 GHz) (thuộc dòng Alder Lake), ta phân tích hai đại lượng là độ trễ và thông lượng qua bảng sau số liệu sau:
Lệnh
Độ trễ (Alder Lake-P)
Thông lượng (Alder Lake-P)
Độ trễ (Alder Lake-E)
Thông lượng (Alder Lake-E)
Phép cộng cơ bản (VPADDQ)
1
0.33
2
0.67
Phép nhân cơ bản (VMULPD)
4
0.5
6
0.5
Phép truy cập bộ nhớ cơ bản (VMOVDQA)
4; 12
0.5
7; 11
1.0
Phép chia cơ bản (VDIVPD)
13; 22
8.0
30; 33
32.0
Số liệu cụ thể được tham khảo tại đây và được đo theo đơn vị chu kì trên tần số 1.70 GHz.
Lưu ý, một số thao tác có đến hai giá trị cho độ trễ, lý do là vì ta xét tốc độ của thao tác trong các hoàn cảnh khác nhau.
Khi tính toán độ phức tạp, ta xem cả 4 thao tác trên có cùng độ phức tạp ~\mathcal{O}(1)~. Tuy nhiên, không khó để nhận ra rằng với cùng số thao tác, các loại lệnh máy khác nhau có thể cho ra chênh lệch về tốc độ một cách đáng kể.
!Important
Cần nhấn mạnh một điều rằng độ trễ của phép truy cập bộ nhớ và phép chia là tương đối lớn. Đáng nói, thông lượng của phép chia là rất tệ khi so sánh với 3 lệnh còn lại. Khi thực hiện tối ưu hiệu suất của các chương trình, ta cần xác định được đâu là yếu tố đang gây ra sự chậm trễ của chương trình.
Sơ lược về benchmarking
Đối với các code đơn giản như vòng lặp và gán đơn thuần, đôi khi, việc so sánh thời gian sẽ không được diễn ra một cách công bằng do trình biên dịch của C++ sẽ tối ưu bằng cách lược bỏ các dòng code không "hữu ích".
Để "ép" trình biên dịch C++ biên dịch toàn bộ đoạn code cần so sánh để mô phỏng các đoạn code thực tế, ta cần sử dụng một thư viện benchmarking đặc biệt. Trong bài viết này, mình sẽ sử dụng Google Benchmark – một thư viện benchmarking nổi tiếng dành cho C++.
Bạn đọc có thể cài đặt CMake và Google Benchmark theo hướng dẫn tại Github repository của thư viện này. Ngoài ra, bạn đọc cũng có thể tham khảo hướng dẫn sử dụng thư viện nếu muốn tự chạy lại các benchmark trong bài viết này. Do việc cài đặt và setup CMake cũng tương đối phức tạp, bạn đọc có thể tham khảo thêm các nguồn tài liệu sẵn có trên internet.
Ngoài ra, các benchmark trong bài viết này sẽ được chạy bằng bộ xử lý 13th Gen Intel(R) Core(TM) i7-1355U (1.70 GHz) trên máy tính cá nhân. Bạn đọc có thể tham khảo toàn bộ code được sử dụng để benchmark trong bài viết này ở phần Phụ lục ở cuối bài viết.
Cache-friendly coding
Như vậy, qua phần phân tích cấu trúc bộ nhớ máy tính, câu hỏi về việc vì sao cùng một thuật toán, nhưng hai cách cài đặt khác nhau lại có thể cho ra hai thời gian chạy rất khác nhau cũng đã phần nào được giải đáp -- có thể lý giải rằng chương trình chậm hơn đã gây ra nhiều cache miss hơn trong quá trình cài đặt.
Câu hỏi đặt ra bây giờ là: Khi cài đặt, ta cần lưu ý điều gì để code của chúng ta luôn cho ra "chương trình nhanh hơn" trong câu chuyện nêu trên?
Cục bộ hóa
Cục bộ hóa khi duyệt mảng
Tất nhiên, chiến lược caching của máy tính không thể quá cầu kì và phức tạp được. Máy tính sẽ có xu hướng cache một vùng nhớ liên tục trong main RAM. Đây là một lưu ý cực kỳ quan trọng đối với các lập trình viên khi xử lý mảng.
Ta sẽ thử nghiệm hai kiểu duyệt mảng (tuần tự và ngẫu nhiên), sau đó sử dụng Google Benchmark để so sánh hai kiểu duyệt trên các kích thước mảng khác nhau.
Kết quả benchmark cho ~N = 2^k~ với ~k \in [4; 24]~ như sau:
Bạn đọc lưu ý rằng trục ~y~ được thể hiện bằng thang ~\log~ với cơ số ~10~, do đó, độ cao của các cột chỉ mang tính tương đối.
Có thể thấy, kể từ mốc ~N = 2^{16} \approx 7 \cdot 10^4~, tốc độ của cách duyệt tuần tự đã là nhanh gấp 3 lần cách duyệt ngẫu nhiên. Ta có thể lý giải điều này là do cách duyệt ngẫu nhiên gây ra quá nhiều cache miss khi ~N~ đủ lớn; mặt khác, với các kích thước ~N \leq 2^{12}~, ta chưa thấy khác biệt rõ rệt là vì kích thước các cache L1, L2, L3 đủ lớn để gần như chứa cả mảng.
Cục bộ hóa khi khai báo bộ nhớ
Khi tự thiết kế các cấu trúc dữ liệu, hoặc sử dụng các cấu trúc dữ liệu thuộc thư viện chuẩn của C++, chúng ta cùng cần lưu ý đến tính phân mảnh (fragmentation) của bộ nhớ. Nói cách khác, ta cần quan tâm đến việc bộ nhớ của cấu trúc dữ liệu sẽ được lưu trong một dải các ô nhớ liên tiếp trong RAM (phân mảnh thấp) hay những ô nhớ rời rạc xa nhau (phân mảnh cao).
Ví dụ, các cấu trúc dữ liệu sau đây có tính phân mảnh thấp, phù hợp với cache-friendly coding:
Mảng (nhiều chiều) và vector một chiều được lưu trữ dưới dạng một dải bộ nhớ liên tục trong RAM, từ đó, việc caching trên mảng và vector cũng được diễn ra thuận tiện hơn.
Vì cơ chế hoạt động của hàng đợi ưu tiên cho phép đánh số các nút trên cây nhị phân và lưu trữ chúng dưới dạng mảng, container được sử dụng mặc định là vector nên việc tổ chức bộ nhớ cũng cache-friendly tương tự vector.
Bitset là một cấu trúc dữ liệu cực kì cache-friendly vì dữ liệu được tổ chức một cách rất dày đặc (1 phần tử chiếm đúng 1 bit), vector<bool> là một trường hợp đặc biệt của vector và cũng có cơ chế lưu trữ tương tự. Lưu ý rằng bitset và vector<bool> hiệu quả hơn mảng về mặt lưu trữ vì một giá trị bool thông thường chiếm 1 byte (8 bit).
Mặt khác, các cấu trúc dữ liệu sau đây có tính phân mảnh trung bình/cao:
Một vector ~d~ (với ~d \geq 2~) chiều lại được lưu trữ dưới dạng một dải bộ nhớ liên tục, mỗi ô nhớ lại là một con trỏ, trỏ đến một vector ~d - 1~ chiều khác. Ví dụ, nếu chỉ thao tác trên các ô thuộc một dòng của vector 2 chiều, CPU vẫn có thể thực hiện caching hiệu quả; nhưng nếu thao tác trên các dòng khác nhau, tính cục bộ sẽ không còn được đảm bảo do bộ nhớ của các dòng có thể được lưu trữ ở các vị trí rời rạc trên RAM.
Hàng đợi hai đầu có tính phân mảnh trung bình vì dữ liệu được lưu dưới dạng các block rời rạc. Một điều bất ngờ là stack và queue đều sử dụng container mặc định là deque nên điều tương tự cũng xảy ra với 2 cấu trúc dữ liệu này.
Các cấu trúc dữ liệu dựa trên node (node-based data structures) có tính phân mảnh rất cao vì các phần tử được khai báo một cách rời rạc.
Để so sánh tốc độ chạy của một số cấu trúc dữ liệu nêu trên, mình thực hiện benchmark thời gian thực hiện ~10^9~ thao tác duyệt trên mảng, hàng đợi hai đầu và danh sách liên kết đơn. Kết quả như sau:
Có thể thấy, chênh lệch về hiệu suất của mảng/vector so với hàng đợi hai đầu là không quá lớn, do các ô nhớ của hàng đợi hai đầu vốn không quá phân mảnh. Tuy nhiên, danh sách liên kết đơn lại có tốc độ duyệt cực kì chậm khi số phần tử tăng cao, điều này là do các phần tử của danh sách liên kết đơn được lưu trữ rải rác trong RAM, khiến việc cục bộ hóa trở nên khó khăn.
Tất nhiên, những cấu trúc dữ liệu nêu trên, dù cho có cache-friendly hay không, đều có những ưu điểm riêng của nó. Tùy vào nhu cầu sử dụng trong từng trường hợp, ta chọn những cấu trúc dữ liệu khác nhau.
Tối ưu bộ nhớ
Trong rất nhiều trường hợp, khi cố gắng tối ưu bộ nhớ, ta cũng vô tình tối ưu thời gian chạy của thuật toán, dù trên lý thuyết, số thao tác duyệt không thay đổi. Qua số liệu benchmark ở phần trước, ta cũng thấy rằng, cùng là duyệt ~10^9~ thao tác trên cùng một loại cấu trúc dữ liệu, việc tăng/giảm kích thước của cấu trúc dữ liệu đó cũng ảnh hưởng nhiều đến tốc độ cuối cùng.
Điều này có thể được giải thích như sau: khi sử dụng càng ít bộ nhớ, vùng nhớ được đưa vào 1 trong 3 cache sẽ có xu hướng chiếm một phần lớn hơn của vùng nhớ cần thao tác; hơn nữa, khi random-access với vùng nhớ nhỏ, ta sẽ có xác suất truy cập lại vào các vùng nhớ cũ vẫn còn nằm ở trong cache, từ đó tăng số lần cache hit hơn.
Sau đây là một biểu đồ thể hiện số megabytes mà CPU có thể thực hiện random-access trong ~1~ giây trên một mảng gồm ~N = 2^k~ (với ~k \in [2; 22]~) phần tử:
Có thể thấy, tốc độ truy cập khá tương đồng ở nhóm ~N \in [2^3; 2^{11}]~ do toàn bộ dữ liệu đều được đưa vào L1 cache. Ở các kích thước lớn hơn, tỉ lệ cache hit giảm dần kéo theo tốc độ truy cập cũng giảm mạnh.
Khử đệ quy
Trong các tài liệu lập trình nói chung, ta vẫn thường được nghe đến cụm từ "khử đệ quy". Thật vậy, trong những trường hợp có thể thay thế đệ quy thành vòng lặp, chúng ta nên sử dụng vòng lặp vì cơ chế sử dụng bộ nhớ của hai cách cài đặt rất khác nhau và từ đó tạo ra một khác biệt đáng kể về tốc độ và bộ nhớ.
Cơ chế tổ chức bộ nhớ trong hàm đệ quy
Khi dùng hàm đệ quy, với mỗi lần gọi hàm, chương trình sẽ khai báo một stack frame dùng để lưu trữ các tham số, biến trung gian,... Ví dụ, với hàm đệ quy sau:
voiditerate(intnode=1,intdepth=1){// Hàm duyệt cây nhị phânif(depth==3)return;iterate(node*2,depth+1);// duyệt cây con tráiiterate(node*2+1,depth+1);// duyệt cây con phải}
Khi duyệt đến nút số ~6~ ở tầng thứ ~3~, bộ nhớ stack đang phải lưu trữ bộ nhớ của cả ba lần gọi đệ quy chưa hoàn thành là ~\texttt{iterate}(1, 1)~, ~\texttt{iterate}(3, 2)~ và ~\texttt{iterate}(6, 3)~.
Như vậy, lượng bộ nhớ cần dùng là tích của độ sâu đệ quy và kích thước của một stack frame. Mặt khác, khi dùng vòng lặp, độ phức tạp bộ nhớ chỉ sẽ bằng độ phức tạp bộ nhớ của phần nằm bên trong vòng lặp.
Ví dụ, cả hai hàm sau đều có mục đích tương đương, nhưng hàm đệ quy có độ phức tạp bộ nhớ tuyến tính còn hàm sử dụng vòng lặp có độ phức tạp hằng số.
Với cơ chế hoạt động của đệ quy so với vòng lặp, ta có thể thấy một số nguyên nhân khiến đệ quy hoạt động kém hiệu quả hơn như sau:
Gọi hàm nhiều lần: Đối với các hàm thông thường, thời gian được sử dụng cho việc gọi hàm là cực kì ít so với phần còn lại của code. Tuy nhiên, khi phải gọi hàm nhiều lần như khi làm việc với hàm đệ quy, thời gian gọi hàm cũng đóng góp một lượng thời gian đáng kể vào tốc độ chạy của chương trình, bạn đọc có thể tham khảo thêm về cơ chế gọi hàm tại đây.
Cache miss: Từ việc sử dụng nhiều bộ nhớ hơn một cách đáng kể, ta dễ thấy rằng hàm đệ quy dễ gây ra cache miss hơn nhiều so với vòng lặp.
Một lý do khác khiến đệ quy chậm hơn vòng lặp mà ta không đào sâu trong khuôn khổ bài viết này là branching.
Ngoài ra, người ta thường khử đệ quy là vì bộ nhớ của đệ quy được khai báo trên bộ nhớ stack, vùng bộ nhớ này vốn có giới hạn nhỏ.
Tuy nhiên, như đã đề cập, đó là trong những trường hợp ta có thể thay thế đệ quy bằng vòng lặp. Trong lập trình nói chung, đệ quy vẫn là một công cụ cực kỳ mạnh mẽ và hữu ích trong nhiều trường hợp cụ thể.
Ứng dụng trong lập trình thi đấu
Quy hoạch động nhiều chiều
Sử dụng cài đặt bottom-up khi có thể
Khi tìm hiểu Quy hoạch động cơ bản, ta vẫn thường được nghe đến hai cách cài đặt bottom-up và top-down. Tuy cả hai cách trông có vẻ như sẽ cho kết quả giống nhau, nhưng điểm khác biệt lại nằm ở chỗ cách cài đặt bottom-up sử dụng vòng lặp và cách còn lại sử dụng hàm đệ quy.
Do đó, trong những trường hợp mà thứ tự duyệt trạng thái Quy hoạch động đơn giản là duyệt một biến từ bé đến lớn (hoặc ngược lại), cách cài đặt bottom-up sẽ là lựa chọn mang lại hiệu quả về thời gian chạy vượt trội so với cách cài đặt còn lại. Ta chỉ thường sử dụng top-down trong những trường hợp mà việc xác định thứ tự duyệt các trạng thái là phức tạp như DAG, vì bản chất việc sử dụng DFS để xác định thứ tự topo và hàm Quy hoạch động sử dụng đệ quy là tương đương nhau.
Giảm chiều Quy hoạch động
Đối với các dạng Quy hoạch động mà khoảng cách giữa các tham số truy hồi trong cùng một chiều là không quá lớn, ta hoàn toàn có thể rút bớt số chiều Quy hoạch động xuống để tiết kiệm bộ nhớ. Ví dụ, với công thức truy hồi cho bài toán Quy hoạch động cái túi (bỏ qua các trường hợp biên):
Ta thấy rằng để tính bất kì giá trị nào trên dòng ~i~ trên bảng Quy hoạch động, ta chỉ cần xét đến các giá trị trên dòng ngay trên nó (tức dòng ~i - 1~); hơn nữa, kết quả cuối cùng mà ta quan tâm chỉ là các giá trị nằm trên dòng thứ ~n~. Từ đó, ta có thể chỉ duy trì hai dòng liên tiếp của bảng Quy hoạch động. Dòng thứ ~i~ trên công thức định nghĩa bây giờ sẽ được lưu trên dòng thứ ~i \bmod 2~ trên bảng Quy hoạch động, và dòng ~i - 1~ trên công thức ứng với dòng ~(i - 1) \bmod 2~ của bảng.
Thậm chí, với đặc điểm của thuật toán Quy hoạch động cái túi, ta có thể giảm bộ nhớ xuống còn đúng 1 dòng, tức chỉ dùng mảng 1 chiều gồm ~C~ phần tử!
Tổng quát hơn, nếu hàm Quy hoạch động ~\texttt{solve}(i, \dots)~ chỉ truy hồi đến một giá trị ~\texttt{solve}(i - d, \dots)~ nào đó với ~d~ là một hằng số đủ nhỏ, ta hoàn toàn có thể chỉ quan tâm ~d + 1~ dòng liên tiếp của bảng Quy hoạch động.
Lưu ý rằng cách làm trên vẫn giữ nguyên độ phức tạp thời gian của Quy hoạch động cái túi là ~\mathcal{O}(nC)~, tuy nhiên, bộ nhớ bây giờ đã được giảm xuống ~\mathcal{O}(C)~ -- cực kỳ có lợi cho việc caching vùng bộ nhớ được sử dụng cho Quy hoạch động.
So sánh
Để so sánh, mình sẽ giải bài tập Knapsack 1 thuộc AtCoder Educational DP Contest trên nền tảng VNOJ bằng 3 lời giải khác nhau. Kết quả so sánh như sau:
Lưu ý, nền tảng VNOJ chỉ cho phép xem bài nộp của người dùng khác khi bạn đã giải được bài tập đó. Bạn đọc có thể tham khảo bài viết về Quy hoạch động cái túi ở nền tảng VNOI Wiki.
Nhân ma trận
Nhắc lại, phép nhân ma trận ~\mathbf{A} \times \mathbf{B}~ (với kích thước của ~\mathbf{A}, \mathbf{B}~ lần lượt là ~n \times m~ và ~m \times q~) cho ra ma trận ~\mathbf{C}~ có kích thước ~n \times q~ được định nghĩa theo công thức:
Trong bài viết này, ta sẽ xét bài toán nhân ma trận có modulo -- dạng nhân ma trận thường gặp trong lập trình thi đấu. Nói cách khác, ta cần trả về ma trận ~\mathbf{C}~ có giá trị đã được chia lấy dư cho một modulo ~M~ cho trước. Trong các code được dùng trong bài viết này, mình sử dụng ~M = 998 \space 244 \space 353~.
Sử dụng ma trận chuyển vị
Đối với các mảng hai chiều, bộ nhớ thường được trải phẳng theo dòng, nói cách khác, các phần tử thuộc cùng một dòng sẽ được tổ chức thành một đoạn liên tiếp trên mảng trải phẳng. Do đó, trên các ma trận lớn, ta thường ưu tiên duyệt dòng rồi cột hơn là cột rồi dòng trên mảng hai chiều.
Ta thấy rằng khi thực hiện phép tích chập để tính ~\mathbf{C}_{i, j}~, ta đang duyệt các phần tử trên dòng thứ ~i~ của ~\mathbf{A}~ (cache-friendly), nhưng lại duyệt các phần tử trên cột ~j~ của ~\mathbf{B}~ (cache-unfriendly).
Để khắc phục điều này, ta có thể tính trước ma trận ~\mathbf{B}^\intercal~ (với ~\mathbf{B}^\intercal_{i, j} = \mathbf{B}_{j, i}~) để có thể duyệt các phần tử trên dòng thứ ~j~ của ~\mathbf{B}^\intercal~. Công thức nhân ma trận trở thành:
Có thể thấy, phép nhân ma trận thông thường gặp phải 2 vấn đề khiến tốc độ thực hiện trở nên chậm:
Không có tính cục bộ cao nên caching không tốt.
Sử dụng đúng ~n \times m \times q~ thao tác modulo -- một điểm trừ cực kỳ lớn của nhân ma trận có modulo.
Trong phần này, ta sẽ tìm hiểu phương pháp phân khối -- một phương pháp nhân ma trận khắc phục được hai điểm yếu trên tương đối tốt.
Trước tiên, ta dựa vào nhận xét rằng với các ma trận nhỏ, cho dù có duyệt các phần tử theo thứ tự nào, tốc độ nhân ma trận vẫn thường rất nhanh. Ta có thể lý giải đơn giản là kích thước của cả ba ma trận ~\mathbf{A}, \mathbf{B}, \mathbf{C}~ đủ nhỏ để lưu trữ trong L1 cache.
Bây giờ, ta chia nhỏ một phép nhân ma trận vuông ~8 \times 8~ thành các phép nhân ma trận nhỏ ~2 \times 2~. Ví dụ, để tính giá trị của một ma trận con ~2 \times 2~ nằm ở góc trên trái của ~\mathbf{C}~, ta thực hiện 4 bước nhân ma trận ~2 \times 2~ như sau:
Lưu ý, các ô có cùng màu sẽ được thực hiện trong cùng một lần nhân ma trận.
Do kích thước của ba ma trận con ~2 \times 2~ là đủ nhỏ để chứa trong L1 cache và truy cập nhanh, ta xem như chi phí truy cập một phần tử nào đó chỉ bằng lần truy cập đầu tiên trong bước nhân ma trận ~2 \times 2~ tương ứng. Dễ thấy, để thực hiện phép nhân ma trận trên cả ma trận ~8 \times 8~, ta cần thực hiện ~\left( \frac{8}{2} \right)^3 = 64~ bước, mỗi bước thực hiện tốn ~3 \times 2^2 = 12~ lần đưa bộ nhớ vào L1 cache. Như vậy, tổng số lần truy cập bộ nhớ ngoài L1 cache là ~64 \times 12 = 768~, nhỏ hơn tổng số bước truy cập dữ liệu trong nhân ma trận thông thường là ~3 \times 8^3 = 1536~ gấp hai lần.
Tổng quát hơn, nếu kích thước của ma trận con là ~B \times B~ và kích thước của ma trận lớn là ~N \times N~ thì ta cần ~\frac{3N^3}{B}~ lần truy cập bộ nhớ ngoài L1 cache, tức ít hơn gấp ~B~ lần so với tổng số bước truy cập dữ liệu trong nhân ma trận thông thường.
Lưu ý, đây vẫn chỉ là một phép ước lượng khi bỏ qua chi phí truy cập các ô nhớ đã nằm trong L1 cache và bỏ qua những tối ưu khác trong quá trình truy cập dữ liệu của CPU; trên thực tế, cả hai cách tiếp cận đều cần truy cập bộ nhớ đúng ~3N^3~ lần. Nói cách khác, cách làm này không giúp giảm số lần truy cập bộ nhớ mà làm cho mỗi lần truy cập bộ nhớ được tối ưu hơn.
Ta cần chọn một giá trị ~B~ vừa đủ lớn vừa đảm bảo cả ba ma trận con ~B \times B~ đều có thể nằm vừa trong L1 hoặc L2 cache. Trên thực tế, giá trị ~B~ thường dùng cho phương pháp phân khối khi nhân ma trận là ~B = 16~ hay ~B = 32~, đủ để chứa cả ba ma trận con có mỗi phần tử chiếm ~8~ bytes (như long long hay double trong C++) trong một L1 cache thông thường có kích thước ~32~ KB.
Hơn nữa, với ~B = 16~, ta thấy rằng ~M^2 \cdot B < 2^{64}~ vẫn không gây tràn số trên số nguyên ~64~-bit, với các giá trị ~M \approx 10^9~ thường gặp trong lập trình thi đấu. Như vậy, ta chỉ cần thực hiện modulo sau khi đã thực hiện xong mỗi phép tích chập.
Có thể thấy, ta đã xử lý một lúc hai trở ngại thời gian lớn nhất được nêu trên trong phép nhân ma trận.
Ở phần cài đặt (xem phần Phụ lục ở dưới), mình thực hiện thêm một tối ưu nhỏ bằng cách chuyển vị ma trận ~\mathbf{B}~ ngay khi trích xuất ma trận con của nó. Trên nền tảng Library Checker, cách cài đặt của mình thực hiện được phép nhân ma trận ~1024 \times 1024~ trong dưới ~400~ mili-giây.
So sánh
Để so sánh hai cách tối ưu nêu trên, mình sẽ thực hiện benchmark cả 3 cách nhân ma trận trên ma trận vuông có độ dài cạnh ~N \in 2^k~ (với ~k \in [1; 10]~). Lưu ý, ma trận được sử dụng trong phần cài đặt là ma trận đã được trải phẳng thành vector 1 chiều nhằm tối ưu cache.
Bạn đọc lưu ý rằng trục ~y~ được thể hiện bằng thang ~\log~ với cơ số ~10~, do đó, độ cao của các cột chỉ mang tính tương đối.
Ngoài ra, bạn đọc có thể tham khảo animation sau được thực hiện bởi Jukka Suomela, so sánh phương pháp phân khối (bên phải ngoài cùng) với các phương pháp nhân ma trận khác.
Pragma
Một chi tiết được chú ý và bàn luận nhiều trên các nền tảng mạng xã hội về đề thi Học sinh giỏi Quốc gia môn Tin học năm nay (năm học 2025-2026) là dòng ghi chú ở đầu đề bài ở cả hai ngày thi như sau:
Trước khi tìm hiểu lý do dòng ghi chú này lại xuất hiện trong đề thi Học sinh giỏi Quốc gia, ta cùng tìm hiểu sơ lược về định hướng biên dịch chương trình (hay từ khóa pragma) và ứng dụng của nó trong lập trình C++.
Sơ lược về pragma
Từ khóa pragma là những chỉ thị đặc biệt dành cho trình biên dịch nhằm làm thay đổi một số hành vi của chương trình khi biên dịch chương trình. Từ khóa này thường được sử dụng kèm với các chỉ thị như once hay GCC poison hay GCC target và thường đi kèm các từ khóa như O2, unroll-loops, avx2,... tùy vào chỉ thị được dùng. Ta có thể sử dụng một lúc nhiều từ khóa như sau:
#pragma GCC optimize("O3", "unroll-loops")
Nếu muốn sử dụng chỉ thị cho đúng một hàm của chương trình, ta có thể sử dụng thêm từ khóa __attribute__, ví dụ:
Một lưu ý cực kỳ quan trọng khi sử dụng pragma đó là chúng ta cần hiểu những chỉ thị được dùng sẽ hoạt động như thế nào và hoạt động một cách hiệu quả trong những hoàn cảnh nào. Bởi việc sử dụng từ khóa pragma một cách mù quáng sẽ làm cho chương trình không chỉ không thể được tối ưu mà còn bị tệ đi nhiều lần.
Một trong những ví dụ của việc sử dụng pragma một cách mù quáng đó là copy/paste 3 dòng code sau vào đầu của mọi chương trình, đây là một thói quen không được khuyến khích, mặc dù trong phạm vi lập trình thi đấu, chúng rất ít khi làm chương trình tệ đi:
Do đây là bài viết tập trung vào tối ưu tốc độ và bộ nhớ, chúng ta chỉ sẽ tìm hiểu về hai chỉ thị liên quan đến tối ưu là:
#pragma GCC optimize(...)#pramge GCC target(...)
Chỉ thị #pragma GCC optimize
Đúng như cái tên, chỉ thị này sẽ ra lệnh cho trình biên dịch thay đổi một vài chi tiết trong quá trình biên dịch nhằm thực hiện các tối ưu phần cứng cho chương trình cuối cùng. Một số từ khóa thường dùng với chỉ thị GCC optimize là:
Từ khóa
Công dụng
Lưu ý
O2
Thực hiện tất cả các loại tối ưu "an toàn" -- tức sẽ không phản tác dụng trong mọi trường hợp. Ví dụ: sắp xếp các lệnh độc lập để hạn chế thời gian CPU không làm gì, loại bỏ các phép tính trung gian trùng lặp,...
Đã được tích hợp trong máy chấm Themis, VNOJ, Codeforces và đa số các Online Judges nên thường không cần dùng trong code.
O3
Bao gồm các tối ưu thuộc nhóm O2 và các tối ưu khác như tự động vector hóa các phép tính độc lập với SIMD, sử dụng nhiều hàm nội tuyến hơn, gộp một nhóm các thao tác liên tiếp trong vòng lặp để giảm số lần kiểm tra điều kiện lặp (loop unroll),...
Trong khuôn khổ lập trình thi đấu, từ khóa O3 không mạo hiểm vì các code thường có độ dài không lớn hơn kích thước instruction cache.
Ofast
Bao gồm các tối ưu thuộc nhóm O3 và các tối ưu có phần mạo hiểm hơn, như bỏ qua tiêu chuẩn của ngôn ngữ lập trình về xử lý số thực, nguyên tắc quản lý con trỏ,... Việc sử dụng từ khóa Ofast làm chương trình mất đi sự chính xác khi thao tác với số thực, khó caching và debug hơn.
Từ khóa Ofast vẫn luôn là từ khóa gây tranh cãi vì bất lợi mà nó đem lại là không nhỏ. Đặc biệt khi làm việc với số thực, ta thường chấp nhận bỏ qua Ofast để chương trình được thực hiện một cách chặt chẽ hơn.
unroll-loops
Trình biên dịch sẽ gộp một nhóm các thao tác liên tiếp trong lặp để giảm số lần kiểm tra điều kiện lặp.
Chỉ thị #pragma GCC target
Các chỉ thị GCC target giúp chúng ta thực hiện các chỉ thị liên quan để tập lệnh máy, ví dụ như sử dụng SIMD để thực hiện các lệnh liên tiếp không phụ thuộc vào nhau một cách song song. Một số từ khóa thường dùng với chỉ thị GCC target là:
Từ khóa
Công dụng
Lưu ý
avx, avx2
Chỉ định CPU sử dụng SIMD cho các lệnh có thể thực hiện song song (vectorization) nếu có.
Sử dụng cùng optimize("O3") hay optimize("unroll-loops")
popcnt, lzcnt
Làm cho tốc độ của __builtin_popcount() và __builtin_clz() nhanh hơn
Lưu ý, độ phức tạp thời gian của hai hàm trên vẫn là ~\mathcal{O}(1)~ bất kể có sử dụng pragma hay không.
abm, bmi, bmi2
Các tối ưu nhắm vào các thao tác trên bit nói chung.
fma
Thực hiện các phép tính nhân rồi cộng ~d = a \cdot b + c~ trong một lần (fused multiply-add).
omit-frame-pointer
Giúp tăng kích thước register có thể sử dụng để tính toán, tiện lợi hơn cho việc caching.
Đã được tích hợp vào chỉ thị optimize("O2").
Đây là một bài nộp trên nền tảng oj.uz đã có tận dụng tối đa các chỉ thị pragma để làm cho một thuật toán trâu có thể chạy vừa giới hạn thời gian. Tuy nhiên, đây là một bài tập có giới hạn khá lỏng để thí sinh sử dụng nhiều thuật toán khác nhau (chia căn, đường quét, chia để trị CDQ,...) và bản thân máy chấm của nền tảng này là tương đối mạnh.
Vì sao không nên sử dụng pragma trong thi cử?
Các chỉ thị pragma, ngoại trừ optimize("O2") đã được tích hợp trong máy chấm, nhìn chung là những tối ưu tạo ra nhiều biến số khi thực thi chương trình trên từng máy tính khác nhau; như đã đề cập, đôi khi việc sử dụng pragma một cách mù quáng không chỉ không thể tối ưu mà còn làm chậm tốc độ chương trình; chỉ thị Ofast thậm chí dẫn đến sai số tính toán và các hành vi không được kiểm soát (undefined behaviour).
Hơn nữa, trong môi trường lập trình thi đấu, việc xây dựng tư duy để thiết kế các thuật toán tối ưu được chú trọng hơn rất nhiều so với việc sử dụng những tối ưu không đáng kể để cố gắng ép các chương trình chưa tối ưu có thể vượt qua giới hạn thời gian.
Vì vậy, không chỉ tại kì thi Học sinh giỏi Quốc gia, nhiều kì thi lập trình thi đấu nói chung thường không cho phép sử dụng pragma để các thí sinh có thể tập trung vào các mặt tư duy, thiết kế thuật toán và cài đặt hơn là tối ưu phần cứng -- những bước tối ưu chỉ nên thực hiện sau khi đã có thuật toán tốt. Ngay ở những kì thi cho phép sử dụng pragma như ICPC hay IEEExtreme, các bài tập cũng được thiết kế sao cho thí sinh hoàn toàn có thể giải quyết mà không sử dụng từ khóa này.
Đây là một bài tập thú vị nhất thuộc vòng loại kì thi Forethought Future Cup, nếu xem các lời giải hiện đã nhận Accepted trên Codeforces, ta thấy các lời giải hầu hết rơi vào 1 trong 2 trường hợp sau:
Có thời gian chạy dưới 200ms.
Có thời gian chạy trên 950ms.
Nguyên nhân là do giới hạn của bài tập này là tương đối lỏng, hơn nữa, ta có thể tận dụng các nhận xét về tối ưu phần cứng để làm lời giải "vét cạn" trở nên nhanh hơn 1 giây. Trước tiên, ta cùng nghiên cứu đề bài.
Đề bài
Cho một dãy ~A~ gồm ~N~ phần tử và ~Q~ thao tác có dạng:
Cho hai số nguyên ~s_j, x_j~ với ~s_j \in \{<, >\}~ và ~x_j~ là một số nguyên bất kỳ. Với mọi ~1 \leq i \leq N~, ta đổi dấu ~A_i~ nếu bất đẳng thức ~A_is_jx_j~ đúng.
Yêu cầu in ra mảng ~A~ sau khi thực hiện ~Q~ thao tác.
Giới hạn:
~1 \leq N \leq 10^5~
~-10^5 \leq A_i, x_j \leq 10^5~.
Thời gian: ~1~ giây.
Bộ nhớ: ~256~ MB.
Phân tích
Mình cực kì khuyến khích các bạn tự giải quyết bài toán bằng lời giải chuẩn trước khi đọc tiếp phần này.
Trong bài viết này, chúng ta sẽ không bàn luận về lời giải chuẩn của bài toán, mà sẽ phân tích các lời giải có thời gian chạy hơn 950ms -- một lời giải vét cạn vừa đủ giới hạn thời gian.
Có thể thấy, với các thao tác trong lời giải vét cạn (so sánh, gán, và truy cập mảng), thao tác truy cập mảng là nguyên nhân chính cho tốc độ chậm của thuật toán. Đây sẽ là cơ sở để ta thực hiện tối ưu phần cứng.
Trong lời giải ~\mathcal{O}(NQ)~, ta duyệt các thao tác từ ~1~ đến ~Q~ rồi duyệt mảng từ ~1~ đến ~N~ (hoặc ngược lại, duyệt mảng rồi duyệt thao tác). Khi này, thời gian truy cập mảng ~A~ là vô cùng lớn, vì phải cách ~N~ lần truy cập mảng thì ta mới truy cập lại một ô nhớ cũ. Điều này làm cache miss diễn ra rất nhiều nếu kích thước mảng lớn hơn sức chứa của các cache L1, L2, L3.
Thay vào đó, sử dụng một ý tưởng tương tự phương pháp phân khối trong nhân ma trận, ta chỉ giải bài toán cho một phần nhỏ của mảng ~A~ đủ để chứa trong L1 cache. Sau đó, lặp lại ý tưởng với phần còn lại của mảng. Nói cách khác, ta sẽ chia mảng ~A~ thành các nhóm gồm ~B~ phần tử rồi áp dụng lời giải vét cạn lên từng nhóm. Ta chọn ~B = 1024~ để mọi phần tử thuộc cùng một nhóm có thể nằm trọn trong L1 cache.
Dĩ nhiên, số thao tác truy cập phần tử vẫn là ~NQ~, tuy nhiên, khác biệt nằm ở thứ tự truy cập. Có thể thấy, ở cách ban đầu, thứ tự truy cập là như sau:
Tuy nhiên, ở cách chia nhóm, ta tận dụng rất triệt để việc các phần tử đã được đưa vào L1 cache sau thao tác đầu tiên:
Lưu ý, màu sắc của mỗi phần tử dùng để ước lượng tốc độ truy cập chỉ mang tính tương đối, tốc độ truy cập các phần tử phụ thuộc vào rất nhiều yếu tố khác nhau đang diễn ra trong bộ nhớ máy tính.
Nếu kết hợp ý tưởng trên với chỉ định sử dụng SIMD (avx và avx2), chỉ định gộp phép nhân và phép cộng (fma), tối ưu Ofast, unroll-loops và input/output nhanh (sử dụng scanf), ta đã có thể giải quyết bài toán với lời giải "vét cạn".
Lời kết
Việc hiểu được cơ chế hoạt động của máy tính ở cấp độ bộ nhớ phần nào cũng sẽ giúp các lập trình viên có được cho mình những thói quen cài đặt hiệu quả hơn. Tuy nhiên, theo quan điểm cá nhân, mình nghĩ rằng nền tảng lớn nhất của một chương trình tốt vẫn luôn nằm ở ý tưởng thuật toán khôn ngoan, ở một độ phức tạp thời gian/bộ nhớ đủ tốt; chỉ khi đó, những tối ưu phần cứng như trên mới thực sự có ý nghĩa và tạo ra được một chương trình tối ưu.
Cảm ơn các bạn đã theo dõi bài viết. Xin chúc tất cả các bạn đọc của Tạp chí VNOI một mùa Tết thật ấm no, đầy đủ và hạnh phúc cùng gia đình, người thân và bạn bè!
Phụ lục
Code benchmark và vẽ biểu đồ
Bạn đọc có thể tham khảo các code đã được sử dụng để benchmark trong bài viết này:
Bên cạnh đó, ta còn có dạng bài toán kết hợp ý tưởng quy hoạch động cái túi lên cấu trúc cây, cho ra đời lớp bài toán quy hoạch động cái túi trên cây. Đây tưởng chừng như một dạng bài tập rất hóc búa và đòi hỏi các thuật toán phức tạp. Tuy nhiên, chỉ với một vài lập luận tương đối đơn giản thì ta đã thấy được rằng, chỉ cần duyệt cây một cách khéo léo, ta đã có thể giải quyết bài toán quy hoạch động cái túi trên cây đơn giản hơn nhiều.
Trong mục Kỹ thuật thú vị của Tạp chí VNOI lần này, chúng ta sẽ cùng điểm qua các phân tích liên quan đến lớp bài toán quy hoạch động cái túi này.
Cho cây gồm ~n~ đỉnh (~1 \leq n \leq 10^4~), ~n - 1~ cạnh có trọng số cho biết thời gian di chuyển qua cạnh đó, và hai số nguyên ~k, x~. Tìm lộ trình tốn ít thời gian nhất để di chuyển từ ~x~ qua ~k~ đỉnh khác nhau kể cả ~x~ (kết thúc tại đỉnh bất kỳ).
Phân tích bài toán
Để đơn giản hóa bài toán, ta tạm thời biến đổi ràng buộc bài toán thành lộ trình xuất phát từ ~x~ phải quay về đỉnh ~x~.
Đặt gốc cây tại ~x~. Ta thấy rằng với mỗi cây con ~v_{x, i}~ của ~x~, ta cần thăm ~s_{x, i}~ đỉnh sao cho ~s_{x, 1} + s_{x, 2} + \dots + s_{x, t} = k - 1~. Hơn nữa, tập các đỉnh được thăm tạo thành một thành phần liên thông.
Từ đó, ta có ý tưởng đặt trạng thái quy hoạch động ~\texttt{dp}(u, j)~ là tổng thời gian để thăm ~j~ đỉnh của cây con gốc ~u~ và quay lại đỉnh ~u~. Dễ thấy ~j \leq \texttt{sz}[u]~ với ~\texttt{sz}[u]~ là kích thước của cây con gốc ~u~. Gọi ~v_1, v_2, \dots, v_t~ và ~w_1, w_2, \dots, w_t~ lần lượt là các đỉnh con của ~u~ và trọng số các cạnh nối tới chúng. Khi đó, ta có công thức truy hồi:
Nếu xem một cây con ~v_i~ là "một loại món đồ" và cây con ~u~ là "cái túi", ta có thể biến đổi chúng thành một bài toán quy hoạch động cái túi: Với mỗi loại món đồ, ta có thể chọn ~s_i~ cái với chi phí ~\texttt{dp}(v_i, s_i) + [s_i \geq 1] \cdot 2w_i~, cần chọn các món đồ sao cho tổng số lượng được chọn là ~j - 1~. Ở đây ~[X]~ là ký hiệu của Inverson bracket, mang giá trị ~1~ khi mệnh đề ~X~ đúng và ~0~ nếu ngược lại.
Để xử lý bài toán con trên, ta gọi ~\texttt{knap}(i, j)~ là tổng chi phí tối thiểu nếu chọn ~j~ món đồ ở ~i~ loại món đồ đầu tiên. Ta có công thức truy hồi
$$
\texttt{knap}(i, j) = \min_{0 \leq c \leq \texttt{sz}[v_i]} (\texttt{knap}(i - 1, j - c) + \texttt{dp}(v_i, c) + [c \geq 1] \cdot 2w_i)
$$
Để tính mọi trạng thái ~(i, j)~, độ phức tạp của hàm quy hoạch động cái túi này là ~\mathcal{O}(\texttt{sz}[u]^2)~, dẫn đến độ phức tạp chung của bài toán lên đến ~\mathcal{O}(n^3)~. Tuy nhiên, nếu chỉ duyệt những trạng thái "có nghĩa" một cách khéo léo, độ phức tạp của thuật toán đã có thể giảm xuống ~\mathcal{O}(n^2)~!
Cải tiến & Phân tích độ phức tạp
Để ý rằng khi duyệt đến ~i~ cây con đầu tiên, ~v_1, v_2, v_3, \dots, v_i~, chỉ có các trạng thái ~\texttt{knap}(i, j)~ thỏa ~j \leq \texttt{sz}[v_1] + \texttt{sz}[v_2] + \dots + \texttt{sz}[v_i]~ mới có giá trị xác định, còn lại là các giá trị vô cực, không đóng góp vào công thức truy hồi. Do đó, để tiết kiệm tối đa số lần duyệt, ta có thể cài đặt quy hoạch động trên cây như sau:
intknap[2020],dp[2020][2020];voiddfs(intu,intp){// khởi tạo mảng knap[...]// ...intknapSize=0;for(intv:adj[u]){if(v==p)continue;dfs(v,u);for(intpreTake=knapSize;preTake>=0;preTake--)for(intcurTake=0;curTake<=sz[v];curTake++)// tính knap[preTake + curTake] dựa trên// knap[preTake] và dp[v][take]knapSize+=sz[v];}sz[u]=1+knapSize;// cập nhật dp[u][...] dựa trên knap[...]// ...}
Để phân tích độ phức tạp, ta có thể mô hình hóa quá trình duyệt các cặp ~(\texttt{preTake}, \texttt{curTake})~ thành duyệt các cặp đỉnh ~(s_1, s_2)~ với ~s_1~ thuộc một trong các cây con trước đó ~v_1, v_2, \dots, v_{i-1}~ hoặc ~s_1 = u~, và ~s_2~ thuộc cây con hiện tại ~v_i~. Đặc biệt, các cặp ~(s_1, v_i)~ sẽ được tính 2 lần.
Cả hai mô hình duyệt đều có đúng ~(\texttt{knapSize} + 1) \cdot (\texttt{sz}[v] + 1)~ bước duyệt.
Ví dụ, ở hình trên, tại bước duyệt cây con ~v_i~, ta có thể hình dung việc duyệt các cặp ~(\texttt{preTake}, \texttt{curTake})~ giống như việc duyệt các cặp ~(s_1, s_2)~ sao cho ~s_1~ thuộc nhóm màu xanh/tím và ~s_2~ thuộc nhóm màu đỏ.
Một nhận xét quan trọng là hai đỉnh ~s_1, s_2~ chỉ sẽ được bắt cặp tại lượt DFS của đỉnh ~u~ thỏa ~\texttt{lca}(s_1, s_2) = u~. Do đó, với hai đỉnh ~z_1 < z_2~, dễ thấy tổng số lần duyệt của cặp ~(z_1, z_2)~ và ~(z_2, z_1)~ chỉ là tối đa ~2~ lần.
Tổng kết lại, số lần duyệt tối đa của cách cài đặt quy hoạch động như trên là:
Có thể thấy, số lần duyệt tối đa thậm chí còn chưa đến ~n^2~!
Thuật toán
Quay lại bài toán ban đầu, ta gọi ~\texttt{dp}_0(u, j)~ và ~\texttt{dp}_1(u, j)~ lần lượt là tổng thời gian để thăm ~j~ đỉnh thuộc cây con ~u~ rồi quay về ~u~ (trạng thái 0) hoặc kết thúc ở một đỉnh bất kỳ là con của ~u~ (trạng thái 1). Khi đó, ta điều chỉnh công thức truy hồi thành:
Nói cách khác, với ~\texttt{dp}_0(u, j)~, mọi cây con sẽ được thăm rồi quay về ~u~. Với ~\texttt{dp}_1(u, j)~, ta chọn một cây con để kết thúc hành trình, các cây con còn lại sẽ được thăm rồi quay về ~u~. Việc thực hiện quy hoạch động cái túi sẽ diễn ra tương tự phần phân tích như trên. Như vậy, ta có lời giải quy hoạch động trong ~\mathcal{O}(n^2)~.
Code tham khảo
#include<bits/stdc++.h>usingnamespacestd;usingpii=pair<int,int>;constintmn=1e4+1;intdp[2][mn][mn],knap[2][mn],sz[mn],n,k,x;vector<pii>adj[mn];voiddfs(intu,intp){// gọi DFS và tính kích thước cây con (sz[u])sz[u]=1;for(auto[v,w]:adj[u])if(v!=p)dfs(v,u),sz[u]+=sz[v];// khởi tảo mảng knap[...]knap[0][0]=knap[1][0]=0;for(inti=1;i<=sz[u];i++)knap[0][i]=knap[1][i]=INT_MAX;// chạy DP Knapsack trên các cây con v[1], v[2], v[3],..., v[t]intknapSize=0;for(auto[v,w]:adj[u]){if(v==p)continue;for(intpreTake=knapSize;preTake>=0;preTake--){for(intcurTake=1;curTake<=sz[v];curTake++){intsum=preTake+curTake;knap[0][sum]=min(knap[0][sum],knap[0][preTake]+dp[0][v][curTake]+2*w);knap[1][sum]=min(knap[1][sum],knap[0][preTake]+dp[1][v][curTake]+w);knap[1][sum]=min(knap[1][sum],knap[1][preTake]+dp[0][v][curTake]+2*w);}}knapSize+=sz[v];}// trả các giá trị từ hàm knap[...] sang dp[...]for(inti=0;i<sz[u];i++)dp[0][u][i+1]=knap[0][i],dp[1][u][i+1]=knap[1][i];}intmain(){ios::sync_with_stdio(0);cin.tie(0);intn,k,x;cin>>n>>k>>x;for(inti=1;i<n;i++){inta,b,c;cin>>a>>b>>c;adj[a].emplace_back(b,c);adj[b].emplace_back(a,c);}dfs(x,-1);cout<<dp[1][x][k]<<"\n";return0;}
Cho cây gồm ~n~ đỉnh (~1 \leq n \leq 10^5~) và một số nguyên ~k~ (~1 \leq k \leq 200~). Các đỉnh trên cây được gán một trọng số được cho bởi dãy ~a_1, a_2, a_3, \dots, a_n~ (~-10^9 \leq a_i \leq 10^9~).
Tìm một thành phần liên thông gồm đúng ~k~ đỉnh trên cây sao cho tổng trọng số của các đỉnh thuộc thành phần liên thông đó là lớn nhất.
Phân tích bài toán
Tương tự với bài toán ở trên, ta cũng định nghĩa hàm quy hoạch động ~\texttt{dp}(u, j)~ là tổng trọng số tối đa của thành phần liên thông gồm đỉnh ~u~ và các nút con của ~u~. Công thức truy hồi của quy hoạch động là:
Thoạt nhìn như thuật toán có độ phức tạp ~\mathcal{O}(nk^2)~ hay ~\mathcal{O}(n^2)~. Nhưng cũng tương tự trường hợp như trên, nếu duyệt một cách khéo léo, ta có thể giảm độ phức tạp xuống ~\mathcal{O}(nk)~!
Cải tiến & Giảm độ phức tạp
Khi duyệt để tính hàm ~\texttt{knap}(i, j)~, ta giới hạn các giá trị ~\texttt{preTake}~ bởi ~\min(\texttt{knapSize}, k)~ và các giá trị ~\texttt{curTake}~ bởi ~\min(\texttt{sz}[v_i], k - \texttt{preTake})~. Nói cách khác, ta có thể cài đặt quy hoạch động như sau:
longlongknap[202],dp[100'002][202];intk;voiddfs(intu,intp){// khởi tạo mảng knap[...]// ...intknapSize=0;for(intv:adj[u]){if(v==p)continue;dfs(v,u);for(intpreTake=min(knapSize,k);preTake>=0;preTake--)for(intcurTake=0;curTake<=min(sz[v],preTake);curTake++)// tính knap[preTake + curTake] dựa trên// knap[preTake] và dp[v][take]knapSize+=sz[v];}sz[u]=1+knapSize;// cập nhật dp[u][...] dựa trên knap[...]// ...}
Để phân tích độ phức tạp, ta lại sử dụng ý tưởng biến đổi mô hình for như trên thành duyệt các cặp đỉnh ~(s_1, s_2)~ có ~\texttt{lca}(s_1, s_2) = u~. Tuy nhiên, trong trường hợp số lượng đỉnh có thể chọn làm ~s_1~ hoặc ~s_2~ là nhiều hơn ~k + 1~, ta sẽ ưu tiên chọn ~s_1~ có thứ tự thăm DFS muộn nhất và ~s_2~ có thứ tự thăm DFS sớm nhất. Tương tự với phân tích ở phần trước, nếu đã chọn đủ ~\texttt{sz}[v_i]~ đỉnh làm ~s_2~, ta quay về chọn ~v_i~ làm đỉnh thứ ~\texttt{sz}[v_i] + 1~.
Ví dụ, với trường hợp trên, khi duyệt đến ~u = 1~ và ~v_i = 9~, với ~k = 2~, ta chỉ chọn các đỉnh ~6, 7, 8~ làm ~s_1~ và ~9, 10, 11~ làm ~s_2~. Để dễ phân tích, các đỉnh đã được đánh số theo thứ tự DFS.
Một nhận xét vô cùng quan trọng đó là khoảng cách của ~s_1, s_2~ trên dãy thứ tự DFS với cách chọn này sẽ là không quá ~2k + 1~. Trên thực tế, với điều kiện ~\texttt{preTake} + \texttt{curTake} \leq k~, ta còn có thể kết luận rằng khoảng cách thực sự là không quá ~k~.
Từ đó, ta cũng lập luận được rằng một cặp ~(s_1, s_2)~ xuất hiện không quá ~2~ lần, cộng với việc khoảng cách của ~s_1, s_2~ trên dãy thứ tự DFS là không quá ~k~, ta có thể kết luận rằng với mọi ~s_1~, ta chỉ có tối đa ~2k~ đỉnh có thể chọn làm ~s_2~.
Nói cách khác, số lần duyệt tối đa trong hàm quy hoạch động như trên là:
$$
2nk = \mathcal{O}(nk)
$$
Code tham khảo
#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingld=longdouble;usingpl=pair<ll,ll>;usingpii=pair<int,int>;usingtpl=tuple<int,int,int>;#define all(a) a.begin(), a.end()#define filter(a) a.erase(unique(all(a)), a.end())constintmn=1e5+5;llknap[202],dp[mn][202];inta[mn],sz[mn],n,k;vector<int>adj[mn];voiddfs(intu,intp){// tiền xử lý và khởi tạo mảng knap[...]sz[u]=1;for(intv:adj[u])if(v!=p)dfs(v,u),sz[u]+=sz[v];for(inti=1;i<=min(sz[u],k);i++)knap[i]=LLONG_MIN;knap[0]=0;// thực hiện QHĐ cái túi trên các cây con của uintknapSize=0;for(intv:adj[u]){if(v==p)continue;for(intpreTake=min(k,knapSize);preTake>=0;preTake--)for(intcurTake=0;curTake<=min(k-preTake,sz[v]);curTake++)knap[preTake+curTake]=max(knap[preTake+curTake],knap[preTake]+dp[v][curTake]);knapSize+=sz[v];}// cập nhật dp[u][...] dựa trên knap[...]for(inti=0;i<min(sz[u],k);i++)dp[u][i+1]=a[u]+knap[i];}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>k;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<n;i++){inta,b;cin>>a>>b;adj[a].push_back(b);adj[b].push_back(a);}dfs(1,-1);llans=LLONG_MIN;for(inti=1;i<=n;i++)if(sz[i]>=k)ans=max(ans,dp[i][k]);cout<<ans<<"\n";return0;}
Công thức biến thể
Bên cạnh đó, nếu công thức quy hoạch động cái túi có dạng:
Ta cũng có thể thực hiện quy hoạch động trong ~\mathcal{O}(n^2)~ (không có cận trên cố định) và ~\mathcal{O}(nk)~ (có cận trên ~k~ cố định). Phần chứng minh có thể được tìm thấy tại đây và tại đây.
📌 Các bạn cũng có thể đóng góp bằng cách gửi bài viết và câu hỏi cho VNOI qua: Form
📌 Phần thưởng dành cho những đóng góp xuất sắc từ cộng đồng: lựa chọn một bộ merch độc quyền của VNOI gồm sổ, bút và sticker, hoặc nhận tiền nhuận bút. Ngoài ra, các bạn có nhiều đóng góp sẽ được nhận thêm áo VNOI.
đã đăng vào 15, Tháng 5, 2026, 13:00
- Đồ thị được dựng từ sample ~2~
