toilanvd_HUST's blog

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.

Full text and comments »

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

By toilanvd_HUST, 10 years ago, In English
  • When solving this problem: http://www.codechef.com/problems/MARCHA6, I got an issue, that is: Let 2 binary strings A and B. With every index i of string A, calculate the max matching of string starting from i and string B. For example:
  • A= 1 0 1 1 0 0 1 1 1 0
  • B= 0 1 1 1 0 1
  • with i= 1 -> max matching= 0
  • i= 2 -> max matching= 3 (it is '0 1 1')
  • i= 3 -> max matching= 0
  • i= 4 -> max matching= 0
  • i= 5 -> max matching= 1 (it is '0')
  • Could anyone tell me how to solve it in O(n)?
  • Thank you! Sorry for my poor English.

Full text and comments »

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