Interesting DP problem from NOI PH 2018 Preselection

Правка en3, от sadbubbles, 2020-08-10 21:36:10

A few days ago I found a problem called Weird Keyboard in the Progvar problemsets under the category of DP classics with twists (Progvar is now down sadly, but the problem is still accessible).

I couldn't manage to solve it on my own, and I didn't find any solutions online either, but a friend of mine provided a solution using DP with Trie, which he got AC with. I cannot explain his solution too well, since I haven't learnt any string algorithms/structures yet, but in case anyone is interested, you can see his code here (excuse the long template).

Can anyone think of a solution to this problem that doesn't make use of any string algorithms/structures? Or any alternative solution at all?

Thanks!

TLDR version of the problem statement: Given a string $$$T$$$, and $$$k$$$ strings $$$S_1 .. S_k$$$, find a way to concatenate strings $$$s_i$$$ in any order (repetitions are allowed, you may also not use some strings) such that it minimizes the edit distance with string $$$t$$$. You only need to output the minimum edit distance. It's not necessary to construct the actual string. $$$|T| <= 4000$$$ , $$$k <= 4000$$$ and $$$|S_1| + ... + |S_k| <= 4000$$$

Теги #dp, #strings

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский sadbubbles 2020-08-10 21:36:10 430 Tiny change: '_1| + ... |S_k| <= ' -> '_1| + ... + |S_k| <= '
en2 Английский sadbubbles 2020-08-10 21:18:03 0 (published)
en1 Английский sadbubbles 2020-08-10 21:17:29 944 Initial revision (saved to drafts)