Can anyone solve this problem not using brute force? I'm so happy if somebody can help me.
A beautiful bit string is a string which can be described as a right bracket string, and lexicography order not larger than all of its bracket-circle-permutation. For example: 111000 -> ((())) is a beautiful string (110001 -> (()))( is not a right permutation), but 101 -> ()( is not, and 110010 is also not, because 110010 > 101100 and 101100 -> ()(()) is a bracket-circle-permutation of 110010.
(I have changed the problem set, this is my original problem, I realize that the last one I wrote is not enough to solve my original one.)
Count the number of beautiful strings with n bit. And let a n-bit beautiful string, count the number of beautiful strings which have lexicography order smaller than this. Of course, n is even.
Looks like it's some kind of dp problem.
Looks like the number of beautiful strings with n bit is equal to the number of binary necklaces of length n. link
Sorry for my bad English.
Thank you! My original problem is harder than this one. A beautiful bit string is a string which can be described as a right bracket string, and lexicography order not larger than all of its bracket-circle-permutation. For example: 111000 -> ((())) is a beautiful string, but 101 -> ()( is not. Of course, n is even. I still find it so hard to solve.
"A beautiful bit string is a string which can be described as a right bracket string"
You didn't tell us about this in your above statement. Please update your post to prevent misunderstanding.
Solution of NuM didn't resolved the second requirement of the statement, it is much harder than the first.
My solution for your original problem: Complexity: O(n^4)
This problem is equivalent to counting the number of necklaces of length n with the same number of white and black beads. So it can be solved using similar techniques.
upd: number of such necklaces of length 2*n is equal to
Every necklace have right cyclic shift?
Every necklace have at least one correct cyclic shift.
Nice property!
How did you get that formula?
I used Burnside lemma. Permutation corresponding to shift by 2*i positions consist of 2*gcd(n,i) cycles of the same length, half of which should consist of black beads, while the other half of the whites. In case of odd shift there will be an odd number of cycles, so they can be ignored.
Uhm, thanks again! ^^
If there is a restriction on the degree, then the answer is something like this:
.
Terms for which 2n·gcd(i, j) isn't divisible by i are ignored.
f(l, k) — number of correct bracket sequences (having correct degree) of length l, consisting of k parts. For example: (())() consist of two parts (()) and (), (()()) consist of one part. This value can be calculated using dp.
The idea is to consider parts of a sequence as beads and then apply Burnside lemma.