Show all threads Hide all threads Show all messages Hide all messages | Page 2 | Time limit exceeded on test 9 | Andrei Rezus | 1183. Brackets Sequence | 2 Dec 2020 20:14 | 1 | 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; } | If you are having trouble | urmat | 1183. Brackets Sequence | 26 Oct 2020 22:19 | 1 | 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 | Python3: memory recurcion accepted 0.15 [Hint] | KostyaRychkov | 1183. Brackets Sequence | 26 Jun 2020 19:51 | 1 | 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 | 3 times wa | abid1729 | 1183. Brackets Sequence | 20 Apr 2020 00:59 | 1 | firstly i get wa on 8, then 9,then 13 And finally AC on .001 | problem | Misha | 1183. Brackets Sequence | 25 Oct 2019 18:17 | 1 | hello, can u sentme the right code of this programm? thank you very much coloteroritata@gmail.com | yet one more dp solution explanation | imaginary friend | 1183. Brackets Sequence | 16 Oct 2018 03:50 | 1 | 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. | If you've got WA#13,here is why | PredaBoss | 1183. Brackets Sequence | 8 Feb 2022 11:23 | 2 | Test 13 is an empty sequence :))) | test 8 | Ehsan Goharshady | 1183. Brackets Sequence | 18 Aug 2014 17:49 | 1 | test 8 Ehsan Goharshady 18 Aug 2014 17:49 Can anyone give me test 8 please? I don't what's wrong with my code. Thanks | Page 1 | WA#12 | dukhno | 1183. Brackets Sequence | 4 Dec 2018 00:51 | 3 | WA#12 dukhno 21 Jul 2014 09:04 thank you very much. It's just like the test of the compiler. try ()() | What is Test 8? | karan | 1183. Brackets Sequence | 28 Sep 2013 06:44 | 1 | Can anybody tell what is Test 8. Getting WA. | some hints | hliu20 | 1183. Brackets Sequence | 16 Oct 2018 03:54 | 3 | 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 :) 3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j]) i<=k<=(j-1) > f[i][j] = min(f[i][k], f[k+1][j] You determine f(k) on f(k + 1) in main cycle. But f(k + 1) is undefine for a while. It's a good hint, but something is wrong. actually it's correct. he is going by the increasing of the first parameter. it's like he is splitting the string, trying to get answer for a bigger string based on the smaller substrings | Hint Needed | A.06 | 1183. Brackets Sequence | 5 Apr 2013 20:26 | 1 | Can anyone please give me a hint to solve this problem. Please dont give the recurrence. Thank you. | why WA9??? | Elmi Ahmadov | 1183. Brackets Sequence | 6 Mar 2012 17:22 | 1 | 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. | Solution | askhatik | 1183. Brackets Sequence | 26 Feb 2012 05:41 | 1 | 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 :) | test for WA#8 | hoan | 1183. Brackets Sequence | 29 Jan 2017 06:37 | 7 | input: ))(())(( output: ()()(())()() i hope it can help you. sorry for my poor english. GOOD LUCK!!! Hi, The output of my application for your test is the same. But the judge tell me WA#8 :S. try this input : [][] output : [][] hello,I get the same output as you said but yet i get WA#8.Any suggestions?! Try this (][)) .... answer should be ([][])() or (([][])) Thanks, man, that helped me :) | DP solution | MSDN | 1183. Brackets Sequence | 26 Nov 2010 00:00 | 3 | S - it is a line Create a matrix F[i][j] is a decision with i on j a symbol If S[i] it is a closing bracket, F[i][j] =1 + F[i+1][j] If S[i] a closing bracket that is two cases: 1) We add a closing bracket - 1 + min(F[i+1][k] + F[k+1][j]), where i<k<=j 2) Is in line closing - min(F[i+1][k-1], F[k+1][j]), where S[k] = S[i] and i<k<=j Interesting... But what you output? Please explain to me > 1) We add a closing bracket - 1 + min(F[i+1][k] + F[k+1][j]), where i<k<=j if we want to add a bracket we can add it in (i+1)position. and dont necessary too check all the kind. sorry for my poor english. GOOD LUCK!!! | I have WA#9. Who knows where is my fault? | ¥@§@® Δδδ@$☺√ | 1183. Brackets Sequence | 27 Nov 2007 19:04 | 2 | If who knows please tell me where is my mistake? {PASCAL CODE HERE} var t,st:string; i:integer; procedure init; begin readln(st); i:=0; t:=st; end; procedure solve1; begin repeat inc(i); if st[i]='(' then begin if ((pos(')',st)<>0) and (pos(')',st)>=i)) then begin st[i]:=' '; st[pos(')',st)]:=' '; end; end else if st[i]=')' then begin if ((pos('(',st)<>0) and (pos('(',st)<=i)) then begin st[i]:=' '; st[pos('(',st)]:=' '; end; end else if st[i]='[' then begin if ((pos(']',st)<>0) and (pos(']',st)>=i)) then begin st[i]:=' '; st[pos(']',st)]:=' '; end; end else if st[i]=']' then begin if ((pos('[',st)<>0) and (pos('[',st)<=i)) then begin st[i]:=' '; st[pos('[',st)]:=' '; end; end; until i=length(st); end; procedure solve2; begin i:=0; repeat inc(i); if st[i]='(' then begin insert(')',t,i+1); insert(' ',st,i+1); inc(i); end; if st[i]=')' then begin insert('(',t,i); insert(' ',st,i+1); inc(i); end; if st[i]='[' then begin insert(']',t,i+1); insert(' ',st,i+1); inc(i); end; if st[i]=']' then begin insert('[',t,i); insert(' ',st,i+1); inc(i); end; until i=length(st); end; procedure print; begin writeln(t); end; begin init; solve1; solve2; print; end. sorry, but your approach is incorrect use dp Edited by author 27.11.2007 19:05 | Help! WA at #13, Why? | liangyaxiong | 1183. Brackets Sequence | 1 Jun 2007 12:34 | 2 | I use memoization to solve the promblem, but WA#13. I have no idea about it(although I've been debugging for 2 days). Can you help me? Here's the code: #include <iostream> #include <fstream> #include <string> #include <cassert> using namespace std; ifstream fin("bracket.in"); ofstream fout("bracket.out"); string S; inline bool isregular(int i,int j) { if(j<i) return true; else if(j==i) return false; char stack[100]; int p=0; for(int k=i;k<=j;k++) { if(p==0) { if(S[k]=='('||S[k]=='[') stack[p++]=S[k]; else return false; } else{ if(( stack[p-1]=='('&&S[k]==')' )||( stack[p-1]=='['&&S[k]==']' )) p--; else if(S[k]==')'||S[k]==']') return false; else stack[p++]=S[k]; } } return (p==0); } string s[100][100]; string memo(int i, int j) { if(s[i][j]!="") return s[i][j]; if(isregular(i,j)) { s[i][j].assign(S,i,j-i+1); return s[i][j]; } if(i==j) { if(S[i]=='('||S[i]==')') s[i][j]="()"; else if(S[i]=='['||S[i]==']') s[i][j]="[]"; else assert(0); return s[i][j]; } string ans,tmp,tmp2; unsigned size=UINT_MAX; if(( S[i]=='('&&S[j]==')' )||( S[i]=='['&&S[j]==']' )) { ans=S[i]+memo(i+1,j-1)+S[j]; size=ans.size(); } else if(( S[i]=='('&&S[j]!=')' )||( S[i]=='['&&S[j]!=']' )) { ans=S[i]+memo(i+1,j); if(S[i]=='(') ans=ans+')'; else if(S[i]=='[') ans=ans+']'; else assert(0); size=ans.size(); } else if(( S[i]!='('&&S[j]==')' )||( S[i]!='['&&S[j]==']' )) { ans=memo(i,j-1)+S[j]; if(S[j]==')') ans='('+ans; else if(S[j]==']') ans='['+ans; else assert(0); size=ans.size(); } for(int k=i;k<j;k++) if(size>memo(i,k).size()+memo(k+1,j).size()) { ans=memo(i,k)+memo(k+1,j); size=memo(i,k).size()+memo(k+1,j).size(); } return (s[i][j]=ans); } int main() { cin >> S; cout << memo(0,S.size()-1) << endl; return 0; } Edited by author 23.05.2007 16:19 Problem found. This program crashes when the input string is empty. ----author | Hint (if you have WA #9) | elmariachi1414 (TNU) | 1183. Brackets Sequence | 29 Dec 2011 00:12 | 5 | Try tests []][] (answer length = 6) [(][)](][([(] (answer length = 20) Sorry, answer is 16 for second case Could you please publish the answer with length = 16? My program gives len=20 and I'm also unable to find such answer manually. Maybe that's why I'm experiencing WA9 Edited by author 19.07.2007 15:35 Hm, my AC program gives this answer [()][()]()[][()[]()] (length = 20) Maybe I was confused during solving this problem, so previous posts maybe wrong :( My AC prog. give answer: [()][()]([][([()])]) lenght == 20 =) | I have WA#11. please help me! | {AESC USU} Evgeny Kurpilyanskij | 1183. Brackets Sequence | 17 Mar 2015 21:35 | 4 | I think I have correct solution.(DP) but i got WA#11. pls give some tests. Edited by author 29.01.2007 21:21 [((((((((((((((((((((()))))))))]))))))))))))](((((((((((((((((((((((((((]))))))))))))))))))))))))))) AC answer [((((((((((((((((((((()))))))))[]))))))))))))]((((((((((((((((((((((((((([]))))))))))))))))))))))))))) Edited by author 30.01.2007 00:46 Thank you, Anton! Your test allows to debug and avoid WA as well as TLE. |
|
|