toilanvd_HUST's blog

A hard problem with string
By toilanvd_HUST, 10 years ago, In English

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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Looks like it's some kind of dp problem.

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      "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.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      My solution for your original problem: Complexity: O(n^4)

      #include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define long long long
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)

#define N 102
bool GG[N][N]; long G[N][N];
bool FF[N][N][N][2]; long F[N][N][N][2];

long g(int n, int Level) {
	if (n<=0 || Level<=0) return n==0 && Level==0;
	if (GG[n][Level]++) return G[n][Level];
	return G[n][Level] = g(n-1, Level+1) + g(n-1, Level-1);
}

#define C n][k][Level][ForceDown
long f(int n, int k, int Level, bool ForceDown){
	if (Level<=0 || n<=0) return Level==0 && n==0;
	if (FF[C]++) return F[C];
	long Sum = f(n-k, k, Level-1, false);
	if (!ForceDown) Sum += f(n-k, k, Level+1, 0);
	if (k!=1) for (int i=1; i<=n-1; i++)
	Sum += f(n-i, k-1, Level, true) * g(i-1, Level+1);
	return F[C]=Sum;
}

main(){
	long Sum=0; int n;
	scanf("%d", &n);
	f1(i,n) Sum += f(n-i, i, 1, false);
	cout << Sum << endl;
}
      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Every necklace have right cyclic shift?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Every necklace have at least one correct cyclic shift.

          → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How did you get that formula?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            Uhm, thanks again! ^^

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              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.

              → Reply