Test 13 is an empty sequence :)))

Hi! This is my code for 1183,can someone help me to solve it? I have time limit exceeded on test 9,please help!
#include <stdio.h>
#include <string.h>
//#include <limits.h>
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
int L,memo[100][100];
char S[101];
/*int min(int x,int y)
{
    if(x<y)
        return x;
    else
        return y;
}*/
int rezolva(int s, int e)
{
    if(s>e)
        return 0;
    int ret = memo[s][e];
    if(ret==-1){
        ret = 1+rezolva(s+1,e);
        if(S[s]=='(' || S[s]=='[')
            {
            for(int i = s+1;i<=e;i++)
                if((S[s]=='(' && S[i]==')') || (S[s]=='[' && S[i]==']'))
                    ret = MIN(ret,rezolva(s+1,i-1)+rezolva(i+1,e));
        }
    }
    return ret;
}
void print(int s, int e)
{
    if(s>e) return;
    int best = rezolva(s,e);
    if(1+rezolva(s+1,e)==best)
    {
        if(S[s]=='(' || S[s]==')')
            {
            putchar('(');
            putchar(')');
        }
        else
            {
            putchar('[');
            putchar(']');
        }
        print(s+1,e);
        return 0;
    }
    for(int i = s+1;i<=e;++i)
        {
        if(((S[s]=='(' && S[i]==')') || (S[s]=='[' && S[i]==']')) && best==rezolva(s+1,i-1)+rezolva(i+1,e)){
            if(S[s]=='(')
                {
                putchar('(');
                print(s+1,i-1);
                putchar(')');
                print(i+1,e);
            }
            else
            {
                putchar('[');
                print(s+1,i-1);
                putchar(']');
                print(i+1,e);
            }
            return 0;
        }
    }
}
int main()
{
    scanf("%s",S);
    L = strlen(S);
    memset(memo,-1,sizeof(memo));
    print(0,L-1);
    putchar('\n');
    return 0;
}

dp[N][N] - minimum number of added brackets, ok[l][r] - is [l, r] already solved, vector<pair<char, int>> add[N][N] - what and where brackets should be added to [l][r], to make it balanced.
make calc(l, r) function, if ok[l][r] then return dp[l][r],
if(l == r) then add[l][r] = {{reversed(s[l]), l}} dp[l][r] = 1
if(l + 1 == r and s[l] matches s[r]) then dp[l][r] = 0
if(s[l] == s[r]) you update dp[l][r] with dp[l + 1][r - 1]
or with dp[l][k] + dp[k + 1][r],
take care of already balanced strings

Hint:
We must find pair for the first character or create it.
If S[0] is ']' or ')', then we must add '[' or '(' in begin.
If S[0] is '[' or '(', then we can find pair in S or add ']' or ')' after S[0].

Edited by author 26.06.2020 19:51

firstly i get wa on 8, then 9,then 13
And finally AC on .001

hello, can u sentme the right code of this programm? thank you very much
coloteroritata@gmail.com

Please give me test 12.

1. DP,  f[i][j] represents when solving the substring from index i to j the minimum brackets should add. Then we have
    1) i <= j
    2) if i == j, then f[i][j] = 1. (you can add a bracket to match the one)
    3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j])   i<=k<=(j-1)
    4) that's not the end.... a case when s[i] == s[j], get f[i+1][j-1]. should compare this value to above values in (3), and get the maximum.
 2. how to show the results
    when calculate f[i][j], you can use an array like ans[i][j] to record the way to get f[i][j]. for example, when f[i][j] get maximum when k = k1. so you can record k1 to ans[i][j]. Or f[i+1][j-1] get the maximum , you can record -1 to ans[i][j], or in the case i==j you get the maximum, set ans[i][j] to 0......
    Then you can get result by DFS.

hope it helps :)

as other participants i used dp. there are different explanations of dp approach, but somehow i find them pretty blurry. when calculating the min number of brackets to be added for the substring, i think there should be done only 2 simple steps:

1) check whether the substring is already correct - can be done using stack in linear time. if this happens to be true, than no sense going to step 2
2) if s is substring and d[i][j] is used for storing dynamic for substring of i length starting at j, then solution is:
d[i][j] = min(d[i - 2][j + 1] if s[j] == s[i + j], min(d[k][j] + d[i - k][j + k]) for 1 <= k < i))

why the 2nd step has that condition? that goes from the the problem definition itself. we can form regular sequence either from wrapping it in brackets, eg '(  (....)  )' or with concatenating two regular sequences, eg '( ...)    [ ... ]'.

hope this explanation brings some clarity on the approach.

Who got AC, please, send your code to 'my_trashbox@mail.ru'

input:
))(())((

output:
()()(())()()
i hope it can help you.
sorry for my poor english.
GOOD LUCK!!!

I think I have correct solution.(DP)
but i got WA#11. pls give some tests.

Edited by author 29.01.2007 21:21

Can anyone give me test 8 please?
I don't what's wrong with my code.
Thanks

Can anybody tell what is Test 8. Getting WA.

Did anybody get WA on test 9? May be, it's judge error?

Can anyone please give me a hint to solve this problem. Please dont give the recurrence.

Thank you.

Problem statement.
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.


I've used scanf("%s",str) and got WA#13 many times!
Then I dicided to read input by character and got Accepted!

I check some tests where I get from forum, but my program got WA9.

it is my code :

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

#define For(i , n) for (int i = 0; i < n; i++)
#define FOR(i , n) for (int i = n - 1; i >= 0; i--)

using namespace std;

struct Char
{
  char ch;
  int used;
  Char(char c,int u) { ch = c; used = u; }
};

string seq;
vector<Char> stck;

void insert(int i)
{
   if (stck[i].ch == '(') stck.insert(stck.begin() + i + 1, Char(')', 1));
   else if (stck[i].ch == ')')
    {
     stck.erase(stck.begin() + i);
     stck.insert(stck.begin() + i , Char('(' , 1));
     stck.insert(stck.begin() + i + 1 , Char(')' , 1));
    }
   else if (stck[i].ch == '[') stck.insert(stck.begin() + i + 1, Char(']', 1));
   else if (stck[i].ch == ']')
    {
     stck.erase(stck.begin() + i);
     stck.insert(stck.begin() + i , Char('[' , 1));
     stck.insert(stck.begin() + i + 1 , Char(']' , 1));
    }
}

void search(char ch,int from)
{
  int res = 0 , pos = from;
  bool ok = true;
  FOR(i , from)
   if (stck[i].ch == ch && !stck[i].used) {
      stck[i].used = 1;
      pos = i,
      ok = false;
      break;
    }
  for (int i = from - 1; i > pos; i--)
   if (!stck[i].used)
    {
     stck[i].used = 1; ok = false;
     insert(i);
    }
   if (ok) stck[from - 1].used = 1 , insert(from - 1);
}

int main()
{
 cin>>seq;
 stck.clear();
 For(i , seq.length())
  {
    stck.push_back(Char(seq[i],0));
    if (stck.back().ch == ')') stck.back().used = 1 , search('(' , stck.size());
    else if (stck.back().ch == ']') stck.back().used = 1 , search('[' , stck.size());
  }
 For(i , stck.size())
  {
   if (!stck[i].used)
    {
     stck[i].used = 1;
     insert(i);
    }
  }
 For(i , stck.size())
  cout<<stck[i].ch;
 cout<<endl;

 return 0;
}

sorry for my english.

the solution is dp:)
dp[i][j] - contains min number of brackets of type '(', '[' for interval from i to j, that is necessary to paste in order to sequence become correct.
if i'th symbol is opened bracket and jth is corresponding closing, then we can improve anser for this interval: dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 2);
if there are different brackets, then we can improve in such way:
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 2;
and finally we can improve by other bracket in the middle:
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + 2);
here, k is the position of all indices that is corresponding closing bracket for i-th;
for example if(s[i] == '(') then k is the index of all
k where, s[k] = ')';
here simple code:
for(int i = 2; i < n; ++i) {
         for(int j = 0; j + i < n; ++j) {
             if(isOpened(s[j]) && s[j] == get(s[j + i])){
//get(c) returns corresponding closing bracket for bracket c;
                  d[j][j + i] = d[j + 1][j + i - 1] + 2;

             }
             else{
                 if(d[j + 1][j + i] < d[j][j + i - 1]) {
                      d[j][j + i] = d[j + 1][j + i] + 2;

                  }
                  else{
                       d[j][j + i] = d[j][j + i - 1] + 2;

                  }
             }
             if(isOpened(s[j]))
                 for(int k = j; k < j + i; ++k)
                       if(get(s[j]) == s[k]){
                            if(d[j + 1][k - 1] + 2 + d[k + 1][j + i] < d[j][j + i]) {
                                 d[j][j + i] = d[j + 1][k - 1] + 2 + d[k + 1][j + i];

                            }
                       }
         }
    }

don't forget to precount for length 1 and 2 :)
good luck to everybody :)

Try tests

[]][]
(answer length = 6)

[(][)](][([(]
(answer length = 20)