1204 - Fun Game

[flashion]

Hello guys,

I've been thinking about this problem lately and I came up with some solution. I wanna share it with you and ask you to tell me if it makes sense.

1) I grab the longest paper and check if it contains all of children by checking if other papers are substring of it (with cycle).
2) If yes, I print solution.
3) If not, I remove all papers that are substrings of other papers (they don't contain any information for solution)
4) I create a graph G(V,E) where v c V are papers and cost of the edge: (v1, v2) c E is: length(v2) - longest prefix-suffix of string: "v2#v1", that means how much letter i need to add to v1 string to get v1v2 string.
5) On this graph I run TSP algorithm in O(2^n * n^2) which seems feasible.
6) The solution is the shortest path found by algorithm.

What do you think?

[brianfry713]

Code it and see if it works.