[ABCTF] The Big Kahuna — 120

Team IA
Team IA
Aug 28, 2017 · 2 min read

Đề 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 –

Team IA

cTf Team

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade