#3 - Cắn test để làm gì?

Đầu tiên, bạn sẽ ngồi từ 3 đến 10 phút để đọc và hiểu đề, đôi khi có thể là 15 phút nếu bạn dùng google dịch.

Hiểu đề rồi sẽ đến giai đoạn ngấm đề. Bạn lọc ra những dữ kiện và yêu cầu chính của đề bài, loại bỏ những yếu tố không cần thiết.

Sau đó bạn đi tìm hướng giải quyết. Nhiều bài tập yêu cầu một số bước tiền xử lí để các điều kiện cho trước trở nên minh bạch hơn. Khi mọi thứ đã đủ minh bạch, bạn sẽ thử các thuật toán có khả năng giải quyết vấn đề. Có người thử tham lam trước, có người thử quy hoạch động trước, v.v... tùy theo thói quen. Có người dùng nháp, có người không dùng nháp, cũng tùy vào thói quen (tuy vậy dùng nháp kết hợp với nghĩ vẫn sẽ cho bạn nhiều lợi thế hơn, đặc biệt là về độ chính xác). Bước này quan trọng nhất và tiêu tốn nhiều thời gian của bạn nhất, thường là 30 phút trở lên với một bài khó.

Nhưng rồi 1-2 tiếng trôi qua mà bạn vẫn chưa tìm ra được giải pháp hoàn hảo.

Đó là lúc mà bạn bắt đầu đi "cắn" test.

"Cắn" test, gọi một cách lịch sự hơn là "giải quyết các trường hợp riêng biệt", là một phương pháp được sử dụng để kiếm một phần điểm của bài tập khi bạn không có lời giải hoàn chỉnh cho toàn bộ test, hoặc dùng để kiểm tra độ mạnh của bộ test. Cắn test là một thứ luôn đi liền với bữa ăn, giấc ngủ hàng ngày của bạn. Bạn bè của bạn khoe cắn test, thầy cô của bạn dạy nhặt test, bản thân bạn cũng dặn lòng mình phải ăn được thật nhiều test... Trong các cuộc thi lập trình thi đấu có tính điểm, cắn test là một kĩ năng mà bạn càng biết dùng càng có lợi. Bạn có thể thấy trong kì thi học sinh giỏi quốc gia THPT, điểm được làm tròn đến 2 chữ số phần thập phân lí do cũng là từ cắn test.

Tuỳ vào từng hoàn cảnh, các phương pháp cắn test khác nhau sẽ bộc lộ những ưu điểm, nhược điểm khác nhau. Kí ức thuật toán số 3 sẽ liệt kê một số phương pháp hiệu quả và hay được sử dụng nhất trong các bài tập.

1, Bảo gì làm nấy:

Đúng như tên gọi, nếu bạn không nghĩ ra được thuật toán nào nhanh hơn, thì hãy chạy trâu theo cách nhanh nhất. Chẳng hạn như cho một dãy ngoặc và các truy vấn (l,r), tìm xâu ngoặc đúng dài nhất trong đoạn từ l đến r, nếu bạn không nghĩ ra cách tốt hơn

(hay thậm chí là ), thì tốt nhất là cứ cài thuật toán để kiếm điểm. Trong phòng thi khi thời gian suy nghĩ hoặc code là không đủ, thì đây được coi là một giải pháp an toàn. Cách làm này thường kiếm được từ 30% đến 40% điểm của bài tập.

2, Duyệt nhánh cận:

(Chi tiết về duyệt nhánh cận bạn có thể tìm đọc sách "Giải thuật và lập trình" của thầy Lê Minh Hoàng, bản ebook khá phổ biến trên mạng.)

Duyệt nhánh cận bằng đệ quy là một kiến thức cơ bản mà bạn bắt buộc phải hiểu và thành thạo. Khi bạn gặp một bài có giới hạn nhỏ như 10 hay 20, điều đầu tiên mà bạn nên nghĩ đến là duyệt hoặc duyệt có đặt cận, vì nó cho phép bạn quét qua tất cả các trường hợp có thể. Với những bài có giới hạn vừa hoặc lớn, duyệt đặt cận cũng có thể mang lại một lượng điểm, nhiều hay ít tùy vào việc bạn "cài khéo" đến đâu.

Lại nói đến "cài khéo", đây là một thứ hết sức mơ hồ. Cài khéo có thể hiểu là dùng những cấu trúc dữ liệu chạy nhanh hơn. Cài khéo cũng có thể hiểu là tìm những thuật toán đơn giản hơn để giảm độ phức tạp đi 2, 3 lần… Sau khi đã mất nhiều thời gian làm một bài mà vẫn chưa đạt yêu cầu, nếu bạn nghe được lời giải từ ai đó là một thuật không khác gì cái bạn đã làm, chỉ khác là "cài khéo" hơn, tôi tin chắc rằng bạn sẽ sẵn sàng đấm cho người kia một phát. Đùa thôi, đừng làm thật nhé!

Codeforces từng có một bài quay lui bắt "cài khéo" và chặt thời gian mà tôi khá ghét. Bạn có thể thử để xem mình "khéo" đến đâu:

"Dạng đuôi của một số là số tạo bởi các chữ số khác 0 của nó, sắp xếp theo thứ tự tăng dần. Chẳng hạn số 57040 có dạng đuôi là 457. Cho 2 số nguyên L, R

, tính số dạng đuôi phân biệt của các số nguyên từ L đến R."

Link bài gốc: http://codeforces.com/problemset/problem/833/C

Cách làm này kiếm được khoảng 20% đến 30% số điểm, tùy thuộc vào giới hạn của đề bài.

3, Duyệt kết hợp tham lam:

Bạn chưa hài lòng với con số 20%? Tất nhiên rồi, tôi cũng chưa hài lòng với con số 20%? Quá ít! Tại sao chúng ta không thử vận may cho toàn bài? Thêm tham lam vào chẳng hạn.

Tham lam cũng phổ biến không khác gì duyệt đặt cận trong sự nghiệp cắn test. Nó khác duyệt đặt cận ở chỗ nó thường không chạy quá thời gian, nhưng lại gặp vấn đề về độ chính xác. Có những lúc giải thuật tham lam nhìn là thấy sai nhưng bạn vẫn phải cắn răng cài, vì bạn hy vọng rằng test yếu, vì bạn hy vọng rằng mình sẽ nhặt nhạnh được thêm một vài điểm... Việc làm này là hoàn toàn có cơ sở, bởi không phải lúc nào người ra đề cũng quét được hết những trường hợp thí sinh tham lam sai để sinh test giết.

Duyệt kết hợp tham lam có nhiều kiểu:

- Duyệt khoảng 1s để tìm những cấu hình tiềm năng, rồi sau đó tham lam xây dựng tiếp kết quả dựa trên những cấu hình đó.

- Duyệt và tham lam riêng biệt, sau đó chọn kết quả tốt hơn.

- Duyệt với test nhỏ, tham lam với test lớn.

…

Sử dụng chiến lược nào vào hoàn cảnh nào, là tùy vào bạn.

4, Duyệt trường hợp nhỏ để kiểm tra kiểu hình:

Đây vẫn được coi là một cách cắn test, mặc dù mục đích của nó là đưa người ta đến với 100% số điểm, bởi vì không phải lúc nào kiểu hình mà bạn nhìn thấy cũng đúng với các test lớn. Có không ít bài nhìn rối như tơ vò nhưng cuối cùng kết quả lại là những dãy số vô cùng quen thuộc.

"Cho một dãy N ≤ 200000 số nguyên dương không quá

. Lần lượt đặt xen kẽ các dấu + và - vào giữa các con số và thực hiện các phép tính giữa 2 số cạnh nhau để tạo ra N-1 số mới. Tiếp tục làm như vậy cho đến khi chỉ còn 1 số. In ra con số đó modulo

Ví dụ 1:

Ví dụ 2:

Link bài gốc: http://codeforces.com/contest/815/problem/B

Chúng ta có thể áp dụng cách cắn test số 1, "Bảo gì làm nấy" vào đây, bằng cách tính dần dần từng dãy một. Độ phức tạp hiển nhiên là .

Để hướng đến mục tiêu full điểm, bạn cần tìm xem mỗi số sẽ được cộng lên bao nhiêu lần trong suốt quá trình để tạo ra kết quả cuối cùng, từ đó tính ra kết quả trong thời gian O(N). Nếu không tự tin vào khả năng toán học của mình, bạn có duyệt trâu thử với N nhỏ để xác định kiểu hình. Khi duyệt đến khoảng N = 13, bạn sẽ nhận ra quy luật khi N chia 4 dư 0, 1, 2 hoặc 3.

5, Mảng hằng:

Một phương pháp truyền thống để giải quyết các bài có giới hạn nhỏ nhưng duyệt nhánh cận lại chạy không đủ nhanh. Ở đây dùng từ "không đủ nhanh" chứ không phải là "quá lâu" vì trong trường hợp này duyệt nhánh cận cho bạn kết quả chính xác và thời gian để chạy mỗi test là khoảng vài phút, chứ không phải "nhiều hơn số nguyên tử trong vũ trụ".

"Tính

(N≤1000) với ít bước nhất bắt đầu từ . 2 thao tác hợp lệ là nhân và chia.

Ví dụ để tính , bạn mất ít nhất 6 bước. Một cách làm là:

Link bài gốc: http://www.spoj.com/problems/YOKOF

Cận quan trọng nhất của bài tập này là với một số N, số bước ít nhất sẽ không quá (số bit của N) + (số bit 1 của N) - 2, bởi vì đây là cách chỉ sử dụng phép nhân. Tôi nhớ hồi xưa để xin lời giải của một đứa bạn cho một bài tập khác, tôi đã phải lấy cái cận này ra làm vật trao đổi với nó, vì tôi là người duy nhất trong đội tuyển làm được bài tập này. Nói thế chứ thực ra đây cũng chỉ là một khoảnh khắc vui đùa thôi. Trong đội tuyển những ai làm được bài đều không ngần ngại giảng giải từng chút một cho những người không làm được, vì vậy nên anh em mới chơi thân với nhau và cùng nhau tiến bộ. Còn những ai khinh khỉnh chẳng bao giờ giảng bài cho mọi người, thì về lâu về dài sẽ gặp rất nhiều bất lợi.

Quay lại bài tập kia, khi duyệt ta đặt thêm cận dừng sớm nếu số bước vượt quá số bước ít nhất hiện tại, hoặc số mũ lớn nhất có thể tạo được nhỏ hơn N.

Tuy vậy 2.5s là không đủ với N lớn. Ta viết code chứa mảng hằng kết quả với mỗi N từ 1 đến 1000. Đừng lo, 1000 dòng code nhỏ không làm máy chấm lăn ra chết đâu. Còn nếu máy chấm đơ thật thì, đó cũng không phải là lỗi của bạn :D

6, Tham lam theo nhiều kiểu và chọn đáp án tốt nhất:

Cũng như tên gọi, bạn cài nhiều thuật toán tham lam và chọn kết quả tốt nhất trong số chúng. Thuật nào càng khó tìm test giết thì càng nên cài, vì biết đâu đấy, đó lại là thuật toán chuẩn.

7, Leo đồi (Hill climbing):

Nhắc tới Kiên là phải nhắc đến thuyết năng lượng, leo đồi và khử nhân ma trận. Đây là 3 tuyệt kĩ mà đội tuyển trường Tổng Hợp đã được Kiên truyền thụ lại trong giai đoạn từ năm 2014 đến cuối năm 2015. Hai tuyệt kĩ đầu và cuối xin được đề cập trong các bài viết sau, còn về tuyệt kĩ leo đồi, bạn có thể tìm hiểu chi tiết tại: https://sites.google.com/site/kc97ble/skill/ki-thuat-leo-doi

Mục tiêu của leo đồi là tìm ra các điểm cực trị của hàm số. Mỗi lần thả dù, bạn sẽ nhảy qua lại một số lần để leo lên được đỉnh đồi.

Trong bài viết của Kiên đã có một số ví dụ khá cụ thể sử dụng leo đồi. Ở đây tôi xin được lấy một ví dụ nữa từ VNOI:

"Có n cái hộp xếp theo vòng tròn đánh số 1..n (1 ≤ n ≤ 1000) theo chiều kim đồng hồ. Mỗi hộp chứa một số quả bóng, tổng số quả bóng không quá n.

Cần dịch chuyển các quả bóng sao cho mỗi hộp không chứa quá 1 quả. Mỗi bước, ta có thể di chuyển một quả bóng từ một hộp sang một trong hai hộp bên cạnh.

Tính số bước di chuyển ít nhất."

Link bài gốc: http://vn.spoj.com/problems/BOXES

Một giải thuật không khó nhận thấy. Nếu ta coi hộp k (1 ≤ k ≤ N) là hộp đầu tiên của dãy, thì ta sắp xếp lại các hộp, lấy hộp k làm hộp đầu. Gọi f[i][j] là tổng số bước di chuyển ít nhất để đặt j quả bóng đầu tiên vào i hộp đầu tiên sao cho mỗi hộp từ 1 đến i có không quá 1 quả bóng. Hàm f có thể tính được trong

với mỗi k, kết quả là

f[N][tổng số bóng]. Như vậy tổng độ phức tạp là .

Leo đồi là một cách để giảm độ phức tạp cho bài này. Ta cần biết những k nào cho ta kết quả tối ưu. Ta đặt bán kính leo đồi R = 32 và thả dù ở các điểm k = i*N/10 (1≤ i ≤ 10), sau đó di chuyển leo đồi (trong trường hợp này phải gọi là "xuống đồi" mới đúng, vì kết quả cần tìm là nhỏ nhất). Độ phức tạp còn lại O(số lần thả dù * số bước di chuyển *

) =

= , một con số chấp nhận được.

Leo đồi không đảm bảo lúc nào cũng đúng, nhưng trong trường hợp hàm trơn và liên tục, nó cho thấy hiệu quả rất tốt.

8, Chặt tam phân (Ternary search):

Tôi tin tưởng chắc chắn rằng không có ai hưởng lợi từ thuật toán này nhiều hơn tôi. Đối với tôi, đây là giải thuật điên rồ nhất. Có thể bạn không tin, nhưng chặt tam phân sử dụng được cả với hàm số chỉ nhận 2 giá trị 0/1, nếu bạn đủ tinh quái. Sinh test giết một thuật cắn test bằng chặt tam phân cũng không phải đơn giản, cần rất nhiều sự tỉ mỉ khéo léo.

Về bản chất, chặt tam phân được dùng để tìm đỉnh của một hàm lồi. Không giống leo đồi, chặt tam phân chỉ đúng khi hàm có chính xác 1 cực trị. Chặt tam phân được sử dụng nhiều trong quy hoạch động để giảm độ phức tạp từ N xuống logN. Hãy xem xét ví dụ sau đây:

"Cho một dãy N (N ≤ 100000) số nguyên không âm không quá 10000. Bạn phải chia dãy đã cho thành k+1 (k ≤ min(N-1,200)) dãy các phần tử liên tiếp, bằng cách thực hiện k bước chia, mỗi bước lấy một dãy có nhiều hơn 1 phần tử và chia nó ra làm 2 dãy. Chi phí thực hiện một bước là tích của tổng các phần tử trong mỗi dãy. Hãy tìm cách chia để tổng chi phí thực hiện là ít nhất."

Link đề gốc: http://apio-olympiad.org/2014/apio2014_problemset.pdf

Bạn có thể chứng minh được rằng tổng chi phí sẽ bằng tổng của tích của tổng mỗi phần và tổng các số không thuộc phần đó, tất cả chia đôi.

Từ đó gọi f[i][j] là tổng chi phí nhỏ nhất để chia các phần tử từ 1 đến i thành j dãy.

f[0][0] = 0, f[0][j>0] = f[i>0][0] = ∞,

f[i][j] = min( f[t][j-1] + (s[i] - s[t])*s[t] )

= min( s[t]*s[i] + f[t][j-1] - s[t]2) với 0 ≤ t <i.

Ở đây s[i] = a[1] + a[2] + ... + a[i]. Kết quả cuối cùng là f[N][k+1].

Tới đây nếu bạn không biết cài quy hoạch động bao lồi, bạn có thể dùng chặt tam phân để chọn giá trị t tốt nhất cho f[i][j]. Nhớ đừng quên điều chỉnh một giá trị α phù hợp để khi r-l ≤ α thì chương trình dừng chặt tam phân và thử với tất cả các giá trị t mà l ≤ t ≤ r, từ đó chọn ra t tối ưu.

Giống như leo đồi, chặt tam phân không đảm bảo lúc nào cũng đúng. Tuy nhiên nó lại có ưu điểm rất dễ cài và độ chính xác cao, một lựa chọn cực kì xứng đáng khi bạn không tìm được thuật chuẩn hoặc không có đủ thời gian hoặc bộ nhớ để cài thuật chuẩn.

Với sự giúp đỡ của chặt tam phân, bạn có thể làm đúng 5 subtask đầu của bài tập vừa rồi và lấy bỏ túi 70%. Tin tôi đi, tôi không gạt bạn đâu.

9, Giải thuật mô phỏng luyện kim (Simulated Annealing)

"Cho một dãy N số (N ≤ 50), mỗi số nằm trong khoảng từ 1 đến 50. Bạn được quyền chọn một dãy con (subsequence) và đảo ngược vị trí các số trong dãy con đó, sao cho dãy số mới chứa dãy con không giảm dài nhất là dài nhất có thể.

Ví dụ dãy 9 số: 1 2 3 9 5 6 8 7 4, bạn chọn dãy con gồm các số được gạch chân để đảo vị trí. Dãy mới tạo thành là 1 2 3 4 5 6 7 8 9, có dãy con không giảm dài nhất độ dài 9. Đây cũng là cách làm tối ưu."

Link bài gốc: http://usaco.org/index.php?page=viewproblem2&cpid=698

Gọi f[x][y][i][j] là độ dài dãy…

Ơ, cậu là ai, có phải cắn test không, nếu không phải thì đi ra đi!

Thuật toán mà tôi sắp đề cập dưới đây có thể xa lạ với nhiều người. Bản thân tôi cũng mới nghe thấy nó lần đầu khi hỏi một tình nguyện viên khác về kĩ thuật cắn test. Nó dựa theo "giải thuật mô phỏng luyện kim" (simulated annealing, chi tiết xem tại: https://en.wikipedia.org/wiki/Simulated_annealing), một giải thuật sử dụng phương pháp xác suất.

"Đặt s = một dãy bit có N bit, bit thứ i bằng 1 nghĩa là phần tử thứ i nằm trong dãy con được đảo vị trí.

E(s) = dãy con không giảm dài nhất sau khi đảo vị trí các phần tử có bit bằng 1.

Gọi t0 là nhiệt độ ban đầu.

Khi nhiệt độ T giảm dần dần, ta tạo ra các dãy bit mới s' từ s bằng cách flip một số lượng bit. Nhiệt độ càng cao flip càng nhiều bit. (*)

Ta lựa chọn có cập nhật s = s' hay không dựa theo hàm xác suất P(E(s),E(s'),T). Trong đó:

P(E(s),E(s'),T) = 1 nếu E(s') > E(s)

P(E(s),E(s'),T) = nếu E(s') ≤ E(s)

Luyện kim cho đến khi gần hết time limit thì thôi. Lấy E(s) của dãy s cuối cùng làm kết quả."

Chi tiết về lời giải này xem ở: https://pastebin.com/gBShL4MC

Giải thuật luyện kim trên là một phiên bản tối ưu hơn của leo đồi. Trong khi leo đồi không đảm bảo độ chính xác khi hàm có nhiều cực trị, giải thuật luyện kim cho phép chấp nhận lời giải tệ hơn nhằm tìm ra những cực trị tốt hơn, tránh việc giậm chân tại chỗ. Nếu được chạy trong thời gian đủ lâu, xác suất tìm được cực trị toàn cục của lời giải này là rất lớn.

Ở bước (*), nếu bạn chỉ flip 1 bit với mỗi T, bạn đã có thể lấy được 60-70% số điểm. Còn nếu flip số bit tỉ lệ thuận với T, bạn thậm chí có thể giành trọn vẹn số điểm.

-----------------------------------

Mặc dù cắn test có rất nhiều ưu điểm, là cứu cánh trong rất nhiều trường hợp bế tắc, nhưng nó cũng tồn tại nhiều hạn chế không thể phủ nhận. Hạn chế thứ nhất là tất nhiên, nó không mang lại cho bạn lời giải hoàn chỉnh cho vấn đề, bạn sẽ không giành được toàn bộ số điểm của bài tập. Thứ hai, quá lạm dụng cắn test sẽ làm loãng tư duy. Cắn test chỉ nên là giải pháp thứ yếu khi bạn đã suy nghĩ đủ lâu cho một lời giải chuẩn và bất lực. Nếu bạn chịu khó kiên trì nghĩ lời giải, trình độ của bạn sẽ tiến bộ lên rất nhiều so với việc cắn bừa vài test rồi bỏ đấy.

Về phần mình, khi gặp một bài tập trước hết tôi đặt giới hạn độ phức tạp có thể kiếm trọn vẹn điểm, sau đó tìm một thuật toán sơ khai có tiềm năng tối ưu được về độ phức tạp đã giới hạn. Tiềm năng của thuật toán tốt tới đâu tùy vào cảm giác của bạn. Nhiều trường hợp sau khi tối ưu hết cỡ thuật toán sơ khai mà vẫn chưa đạt được độ phức tạp mong muốn, tôi phải chuyển hướng sang một suy nghĩ khác. Cũng có những lúc cảm giác không đúng khiến cho mình dừng lại khi thuật toán sắp được tối ưu hoàn chỉnh, để tránh điều này cách duy nhất chỉ có luyện tập và luyện tập mà thôi.

Kì thi học sinh giỏi quốc gia THPT sắp đến gần, đừng quên chuẩn bị một hàm răng chắc khỏe. Và cũng đừng quên theo dõi {Kí ức thuật toán}, số tiếp theo đặc biệt dành riêng cho bạn. Hẹn gặp lại!

TĨNH LẶNG

Số tiếp theo: {Kí ức thuật toán #4} Thi quốc gia - bạn đã sẵn sàng chưa?

Page updated

Google Sites

Report abuse