JOIN
Get Time
forums  Revision History
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 optimal


EDIT: 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