JOIN
 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 | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions General Algorithm Discussions Turkish Informatics Olympiad problem
 Turkish Informatics Olympiad problem | Reply Hi,The problem is from Turkish Informatics Olympiad '98. Any hints on the problem are heavily appreciated =):Given n(n<10) find the shortest string that contains all permutations of n.example:input: 3output: 312313213Thanks in advance
 Re: Turkish Informatics Olympiad problem (response to post by kolistivra) | Reply i thought they were simply exaggerating about the difficulty of the problem. apparently either no one cares or no one knows how to solve. but if you know though, please give me an idea. thanks
 Re: Turkish Informatics Olympiad problem (response to post by kolistivra) | Reply What do you mean by all permutations of n? do you mean permutations of alphabet of size n or what?I think De Bruijn Sequences might be useful for you.
 Re: Turkish Informatics Olympiad problem (response to post by TurboGears) | Reply De Bruijn Sequences contain repeated symbols which is not correct.
 Re: Turkish Informatics Olympiad problem (response to post by sclo) | Reply consider example input,input: 3output: 312313213output contains 123,132,213,231,312,321, which are all permutations of 1,2,3. for 4, it must include 1234,1243.....,4321
 Re: Turkish Informatics Olympiad problem (response to post by kolistivra) | Reply Without actually doing anything too clever, try solving the problem for N=4.What you want to do is to find the shortest Hamiltonian path in a graph where vertices correspond to the permutations 1234, ..., 4321 and the length of an edge corresponds to the smallest number of digits we need to add. E.g., the edge 1234 -> 3421 has length 2.This can be done in any n-vertex graph in O(2^n * poly(n)) -- the state can be represented by the set of visited vertices and the vertex where we are.For n=24 this should run reasonably fast. And in the answer for N=4 you may be able to find some pattern that can be generalized.
 Re: Turkish Informatics Olympiad problem (response to post by misof) | Reply Memory is still quite big in this N=4 (n=24) case, 2^24 * 24. Will greedy provide optimal solution to this problem ? For example in case of N=3,4 Greedy found these results :`123 231 312 213 132 321 -> "123121321" : 91234 2341 3412 4123 2314 3142 1423 4231 3124 1243 2431 4312 2134 1342 3421 4213 1324 3241 2413 4132 3214 2143 1432 4321 -> "123412314231243121342132413214321" : 33 `Edit: Rearrange to better see the pattern used for greedy.
 Re: Turkish Informatics Olympiad problem (response to post by wongiseng) | Reply I coded the problem for N=4 based on misof's hints and after 5 minutes it spit out the same solution as yours. (it can be easily done in roughly 600-800 MB)Of course there might be potential bugs there.Code in the edit.
 Re: Turkish Informatics Olympiad problem (response to post by rlblaster) | Reply A bit promising to see similar result :)) Any proof why the greedy works ? (if it works :P) Here's the lengths found by my greedy algorithms:`1 Length : 12 Length : 33 Length : 94 Length : 335 Length : 1536 Length : 8737 Length : 59138 Length : 462339 Length : 409113 ` Code on edit: has a bug, not in determining the order, but on combining the result. ```res.append(perm.substring(0,i-1)); ```Should have been :```res.append(next.substring(N-i+1)); ```
 Re: Turkish Informatics Olympiad problem (response to post by wongiseng) | Reply 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 ardiankp) | Reply Can you explain your method a bit more? How exactly you construct the graph, for instance?
 Re: Turkish Informatics Olympiad problem (response to post by kolistivra) | Reply Let each permutation be an edge, an the vertex is its prefix and suffix.For example, for N = 41234 --> edge from 123 to 2341243 --> edge from 124 to 243It is clear that the result is minimum number of edges needed to add, such that there is Euler path in the graph. However, the added edge is weighted, according to number of matching suffix/prefix of the vertex.All permutations of size N will transform to a graph with N! edges, with (N-1)! cycle, each of size N. Hence, the problem is to "connect" the cycles. // Here is my probably wrong assumption.If we consider only edges with weight 1, the problem to connect the cycles is identical to the original problem of size N-1, hence the recurrence relation. You can check it by drawing for small N. So this technique may be wrong if we need to use edges with weight > 1.
 Re: Turkish Informatics Olympiad problem (response to post by ardiankp) | Reply thanks for your interest. your approach(along with misof and wongiseng) broadened my algorithmic view. unfortunately, i can't validate any of the approaches because the testcases are missing :\ thanks anyways.
 Re: Turkish Informatics Olympiad problem (response to post by sclo) | Reply Please stop minusing sclo and follow the link instead. He is right, this problem is indeed different from finding a de Bruijn cycle.Edit: An approach related to de Bruijn's might be helpful, but nevertheless sclo's statement is true.