Đề bai như sau:
What’s the smallest amount of steps (additions, deletions, and replacing) it would take to make the string “massivegargantuanhugeepicginormous” into “tinysmallmicroscopicinvisible”? Don’t guess too many times or we will disqualify you. Remember to wrap your answer in abctf{}.
Hint:
Dynamic programming. It’s a thing that exists. Example: “Cat” to “That” would take 2 steps, as you replace the “C” with an “h” an add a “T” to the front.
Đầu tiên, đọc vào đề bài mình thấy rất quen. Bắt đầu lục lọi trí nhớ thì có nhớ ra là hồi cấp 3 đã từng làm những bài kiểu như này rồi. Nhưng vì lười nên tạm thời bỏ qua và đi làm bài khác.
Cho tới sáng một hôm học môn Front-end Programming, chán quá lại lôi bài này ra và quăng đề bài này cho một đứa bạn cấp 3, thằng đó cũng chả nhớ gì nhưng nó có nói với mình là “hình như là Quy hoạch động rồi”. Chính xác rồi chính là nó rồi. Ngày xưa mình có được học những bài kiểu như này được gọi là Quy hoạch động.
Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure). Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953.
Quy hoạch động — Wikipedia tiếng Việt
https://vi.wikipedia.org/wiki/Quy_hoạch_động
Bắt đầu vào làm, những bài quy hoạch động thì thường sẽ có những công thức được sinh ra. Ngồi nghĩ thử nếu muốn biến đổi 1 xâu A có i ký tự thành xâu B có j ký tự thì được gọi là C[i,j] và có 2 trường hợp xảy ra :
+ A[i] = B[j] thì số phép biển đổi sẽ là C[i,j] = C[i-1,j-1].
+ [i] != B[j] thì chúng ta có thể dùng 1 trong 3 phép biển đổi vậy nên công thức sẽ là => C[i,j] = min(C[i-1,j], C[i,j-1], C[i-1,j-1]) +1;
Vậy là xong, nhưng còn giá trị khởi tạo thì sao nhỉ?
Nếu xâu A không có ký tự nào mà xâu B có j ký tự thì C[0,j] = j ngược lại
xâu A có i ký tự và xâu B không có ký tự nào thì sẽ là C[i,0] = i, với mọi i,j
Chạy code ra được là 28
Flag là ABCTF{28}
– totop –
