# Help Mars, ppc+osint
It was a programming challenge, in which we had to find the shortest set of database strings (of which therewere a few millions), that concatenated together would give target string (that we had to find on the internetas osint part of the challenge). The strings weren't very long; around 100 characters each, and the target stringwas two orders of magnitude longer. Simple brute force wouldn't work.
Instead, we opted for dynamic programming solution: for each substring of the target, we calculated the minimalsolution by brute forcing first division point and fetching subproblem solution from memoized array. This gaveus runtime of `O(N*N*M)`, where `N` is length of the target, and `M` - maximum length of database strings (withpossibly some logarithmic overhead from Python data structures). Full code attached.