JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Algorithm Discussions General Algorithm Discussions Re: Turkish Informatics Olympiad problem Revision History (1 edit)
 Re: Turkish Informatics Olympiad problem (response to post by wongiseng) I have a technique that found a result with length f(n) = f(n-1) + n!.It seems that your greedy also achieve same results.. anyway I don't know whether it's optimalEDIT: My technique is briefly as follows. It is based on chinese postman problem. We can construct a graph, such that the result is the minimum edge needs to add to make the graph eulerian, plus current number of edges. With these given strings, we can always reduce the problem to count minimum number of edges to add, as a sub-problem with size n-1. Anyway, that's an upper-bound..
 Re: Turkish Informatics Olympiad problem (response to post by wongiseng) I have a technique that found a result with length f(n) = f(n-1) + n!.It seems that your greedy also achieve same results.. anyway I don't know whether it's optimal