1204 - Fun Game
Posted: Thu Jul 31, 2014 11:45 am
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?
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?