Блог пользователя nik1996

Автор nik1996, история, 5 дней назад, По-английски,

Given 2 strings of parenthesis. You need to make another string using these 2 strings such that in the resulting string, all the parenthesis are balanced. Ordering of parenthesis must not change, e.g. if u take 2 characters/parenthesis from 1st string, then order of these parenthesis must not change in resulting string. You need to tell number of balanced strings you can make. Examples: )) (( ans:2, you can make ()() and (())

Could anyone tell how this problem can be solved ?

 
 
 
 
  • Проголосовать: нравится  
  • -2
  • Проголосовать: не нравится  

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by nik1996 (previous revision, new revision, compare).

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Length of a string ?

»
5 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nxn dp

»
4 дня назад, # |
Rev. 19   Проголосовать: нравится -8 Проголосовать: не нравится

The following user-defined C++ data structure parentheses_string_t may be helpful.

The constructor translates a parentheses-string argument s of length n to a base object vector< int >. As the ASCII code of the ( and ) characters are 40 and 41, the expression x = 81 - 2 * c translates c to 1 and -1, respectively.

The necessary and sufficient conditions for s to be balanced are:

  1. The sum of any sub-vector [1, k], where 1 ≤ k ≤ n, is positive.

  2. The total sum of the vector is zero.

#include <bits/stdc++.h>

using namespace std;

struct parentheses_string_t: vector< int > 
{
    bool balanced; int sum;
    
    parentheses_string_t( const string &s ) : balanced( true ), sum( 0 )
    {  
        for( auto c: s ) 
        {
            int x = 81 - 2 * c; push_back( x ), sum += x;
            
            if ( sum < 0 )
                balanced = false; 
        }
        
        if ( balanced and sum > 0 )
            balanced = false; 
    }
};

int main()
{
    ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );
            
    string s; cin >> s; parentheses_string_t p( s ); 
    
    if ( p.balanced )
        cout << "Yes";
    else
        cout << "No";
}

Let us assume that s1 and s2 are the input strings with lengths n1 and n2, respectively, and that p1 and p2 are constructed parentheses strings. Let the parentheses string q of length n = n1 + n2 be among the parentheses strings formed from p1 and p2. Let us define the selection function h(i), where 1 ≤ i ≤ n, such that h(i) = 1 implies that the parenthesis q(i) is selected from p1, and h(i) = 2 implies that q(i) is selected from p2. Let us define the selected sub-vectors [1, g1(i)] and [1, g2(i)] of p1 and p2, respectively, to form the sub-vector [1, i] in q, where g1(i) and g2(i) can be expressed as

g1(i) = g1(i - 1) + 1 - (h(i) - 1)

g2(i) = g2(i - 1) + (h(i) - 1) = i - g1(i)

and g1(0) = g2(0) = 0.

It follows that

q(i) = ph(i)(gh(i)(i))

The necessary and sufficient conditions for the balance of q are

  1. the sum of any sub-vector [1, k] of q for all 1 ≤ k ≤ n is positive.

  2. the total sum of items in q is zero.

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the help. But how will you find count of all such balanced strings through this algo?

    • »
      »
      »
      4 дня назад, # ^ |
      Rev. 19   Проголосовать: нравится -8 Проголосовать: не нравится

      The upper bound on the number of distinct balanced strings should be equal to the binomial coefficient n1-out-of-n as "h(1) - 1, ...., h(n) - 1" can be considered as an n-item bit-string that should contain n1 zeros and n2 ones whose exact positions vary over all possible balanced strings. Such bit-string can be considered as an input to an n-variable binary function whose value indicates whether or not the input bit-string corresponds to a balanced string. The previous comment hints about the balanced strings that satisfy the balance conditions, and about how a possible balanced string q may be generated from p1 and p2.

      Note that if g1(k - 1) = n1, then h(i) = 2 for all k ≤ i ≤ n. Similarly, if g2(k - 1) = n2, then h(i) = 1 for all k ≤ i ≤ n.

»
4 дня назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

just take every 2nd symbol to achieve a perfect balance

»
4 дня назад, # |
Rev. 11   Проголосовать: нравится -9 Проголосовать: не нравится

The following is a simple program to count the number of distinct balanced strings based on the suggested data structure. It is assumed that the length of any balanced parentheses string constructed from s1 and s2 is n = n1 + n2, i.e. a possibly empty balanced parentheses string whose length is less than n is not counted. The program can be slightly updated to consider the latter requirement.


int main() { ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr ); struct parentheses_strings_pair_t { int n1, n2, balanced, sum; parentheses_string_t *p1, *p2; void count_aux( int g1, int g2, int x ) { if ( x > 0 or sum > 0 ) sum += x, count( g1, g2 ), sum -= x; } void count( int g1, int g2 ) { if ( g1 == n1 and g2 == n2 ) balanced++; else { if ( g1 < n1 ) count_aux( g1 + 1, g2, p1->at( g1 ) ); if ( g2 < n2 ) count_aux( g1, g2 + 1, p2->at( g2 ) ); } } parentheses_strings_pair_t() : balanced( 0 ), sum( 0 ) { string s1, s2; cin >> s1 >> s2, n1 = s1.length(), n2 = s2.length(), p1 = new parentheses_string_t( s1 ), p2 = new parentheses_string_t( s2 ); if ( ( p1->sum + p2->sum ) == 0 ) count( 0, 0 ); } } x; cout << x.balanced; }
  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's just a recursion. TLE for:()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Sure, it is a simple recursive solution that works for small n. No claim was made in the previous post about its computational complexity for large n.