JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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: 3
output: 312313213

Thanks 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: 3
output: 312313213

output 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" : 9

1234 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 : 1
2 Length : 3
3 Length : 9
4 Length : 33
5 Length : 153
6 Length : 873
7 Length : 5913
8 Length : 46233
9 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 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 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 = 4
1234 --> edge from 123 to 234
1243 --> edge from 124 to 243

It 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.
RSS